Java 우선 순위 대기열은 어떻게 작동합니까?

단편 소설, 그래프를 구현 중입니다. 이제 Kruskal에서 작업 중입니다. 우선 순위 대기열이 필요합니다. 우선 순위 대기열에 대한 나의 정의는 가장 작은 키를 가진 요소가 먼저 올 것입니까? 잘못인가? 왜냐하면 큐에 가중치있는 에지 (또는 숫자)를 삽입 할 때 정렬되지 않기 때문입니다.Java 우선 순위 대기열은 어떻게 작동합니까?

PriorityQueue<Integer> tja = new PriorityQueue<Integer>(); 
tja.add(55); 
tja.add(99); 
tja.add(1); 
tja.add(102); 
tja.add(54); 
tja.add(51); 
System.out.println(tja);

이렇게 표시됩니다. [1, 54, 51, 102, 99, 55]. 이것은 내가 원하는 것처럼 정렬되지 않습니다! 그리고 예. 가장자리 객체에서 숫자를 추출하고 해당 int를 기반으로 비교하는 우선 순위 대기열로가는 comperator를 만들었습니다. 이렇게하면 효과가 있습니까? 아니면이 데이터 구조가 어떻게 작동하는지 전체 개념을 완전히 오해 한 것입니까?

출처

2009-11-25 Algific

정렬 된 레이아웃을 얻으려면 'while (! tja.isEmpty()) { System.out.println (tja.poll());을 사용해야합니다. }' – serhii

System.out.println이 iterator를 사용하고있는 toString() 메서드를 호출하고 있습니다.이 메서드는 자연 순서 붙일 것을 배려하지 않습니다. docs : "iterator() 메서드에서 제공되는 Iterator가 특정 순서로 우선 순위 큐의 요소를 탐색하지 않을 수 있습니다."

출처

2009-11-25 09:02:19 omerkudat

우선 순위 큐를 인쇄 할 가능성이 있습니까? –

절대 신경 쓰지 마세요, 그렇게 할 방법이 없습니다 ... 당신이 나를 보내 주시면 답변을 업데이트하겠습니다. –

나는 자바 PriorityQueue와 아무 경험이 있지만, 우선 순위 일 (iterator()를 사용하는) iterator() 또는 toString()에 통합되지 않은 것 같습니다.

당신이 할 경우

while (tja.size()>0) 
     System.out.println(tja.remove());

당신은 올바른 결과를 얻을 수 있습니다.

출처

2009-11-25 09:00:46

완벽하므로 제거를 실행할 때까지 구조가 올바르게 정렬되지 않습니다. – Algific

아니요, 구조가 항상 올바르게 정렬됩니다. 반복 할 때가 아닙니다. 그러나 poll(), peek() 또는 remove()를 호출하면 올바른 순서로 요소를 가져옵니다. – omerkudat

@data_hepp 번호 삭제는 구조를 정렬하지 않습니다. 구조체는 이미 정렬되었지만 내부적으로 사용하는 toString() 또는 iterator()가 순회를 보장하지는 않습니다. – Varun

바이너리 힙 기능에 익숙합니까? 그렇지 않으면 최소 힙 및 최대 힙 구조를 살펴보십시오. PriorityQueue는 힙에 구현됩니다. PriorityQueue는 항목을 증가하는 순서로 정렬하지 않지만 힙 정렬은 수행합니다.

은 링크를 통해 이동 당신이 얻을 Priority Queue

출력은 정확합니다.

출처

2015-03-18 11:30:03

Java 우선 순위 대기열은 어떻게 작동합니까?

답변

관련 문제