Java 우선 순위 큐

Question

Java에 내장 된 우선 순위 큐를 사용하여 그래프의 정점을 읽고 정렬하여 궁극적으로 각 반복마다 최소 에지를 제거하는 방법은 무엇입니까?

class MinHeapComparator implements Comparator<Integer> { 
    @Override 
    public int compare(Integer one, Integer two) { 
    return mDistances[one] - mDistances[two];//... 
    } 
    } 

이 I 쓴 최단 경로 알고리즘에서이다

Answer 1

우선 순위 큐를 생성하는 비교기. mDistances는 소스에서 정점까지의 거리입니다. 원하는대로 비교하도록 비교기를 수정할 수 있습니다.

비교기에 대한 설명 : "순서에 대한 두 개의 인수를 비교합니다. 첫 번째 인수가 두 번째 인수보다 작거나 같거나 같거나 큰 양의 정수를 반환합니다." 여기

전체 문서 : http://download.oracle.com/javase/1.5.0/docs/api/java/util/Comparator.html

둘째, 우선 순위 큐에 항목을 추가 할 수 있습니다. 일반적으로 각 꼭지점 목록을 포함하는 각 객체는 꼭지점 객체가 포함 된 배열로 그래프를 작성합니다. 그래서 제 경우에는 우선 순위 대기열에 인덱스를 추가하여 정점을 나타냅니다. 그런 다음 비교기에는 정점에 관계없이 수행 할 논리가 포함될 수 있습니다. PriorityQueue.add()는 항목을 추가합니다.

셋째, 비교와 우선 순위 큐를 인스턴스화 :

PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(numberItems, new MinHeapComparator()); 

넷째, 힙에 맨 위 항목을 추출 PriorityQueue.poll()를 호출합니다. 비교기는 힙의 맨 위에있는 항목을 결정하는 데 사용됩니다.