우선 순위 큐에서 올바른 힙 구현

Question

내 문제는 기능보다 의미가 있습니다. 코드가 deQueue 및 enQueue 함수를 올바르게 구현 한 것처럼 보입니다.

reheapDown 및 reheapUp 기능을 잘못 사용하고있다, 그리고 나는 문제가 내 힙 기능

아이디어는 환자 개체가 제거 될 때 그렇게 간단한 우선 순위 큐 시스템을 재배치하는 것입니다

package priqueue; 

public class Hosheap{ 
    private Patient[] elements; 
    private int numElements; 

    public Hosheap(int maxSize) 
    { 
    elements= new Patient[maxSize]; 
    numElements=maxSize; 
    } 

    public void ReheapDown(int root,int bottom) 
    { 
    int maxChild; 
    int rightChild; 
    int leftChild; 
    leftChild=root*2+1; 
    rightChild=root*2+2; 

    if (leftChild<=bottom) 
    { 
     if(leftChild==bottom) 
     maxChild=leftChild; 
     else 
     { 
     if(elements[leftChild].getPriority() <= elements[rightChild].getPriority()) 
      maxChild=rightChild; 
     else 
      maxChild=leftChild; 
     } 
     if(elements[root].getPriority()<elements[maxChild].getPriority()) 
     { 
     Swap(root,maxChild); 
     ReheapDown(maxChild,bottom); 
     } 
    } 
    } 

    public void ReheapUp(int root,int bottom) 
    { 
    int parent; 
    if(bottom>root) 
    { 
     parent=(bottom-1)/2; 
     if(elements[parent].getPriority()<elements[bottom].getPriority()) 
     { 
     Swap(parent,bottom); 
     ReheapUp(root,parent); 
     } 
    } 
    } 

public void Swap(int Pos1, int Pos2) 
{ 
    Patient temp; 
    temp = elements[Pos1]; 
    elements[Pos1]=elements[Pos2]; 
    elements[Pos2]=temp; 
} 

public Patient getElement(int e) 
{ 
    return elements[e]; 
} 

public void setElement(Patient p, int n) 
{ 
    elements[n]=p; 
} 
} 

, ReheapUp에있다 생각 또는 아래로 올바르게 코드를 수행하지 않는 큐를 재정렬합니다. 우선 순위 큐 코드를 포함해야합니까, 아니면 이미 너무 길습니까?

NetBeans IDE 6.0.1을 사용하고 있습니다.

Answer 1

정확하게 대답하지는 않지만 Java를 사용하면 기본 제공 컬렉션 클래스를 조사 할 수 있습니다. 우선 순위 큐 동작을 얻을 수 있지만 TreeSet (정렬 집합의 한 유형)을 사용하고 Patient 인스턴스에 대해 사용자 지정 Comparator를 구현합니다. 당신이 달성하고자하는 것에 따라, 이것이 바람직 할 수 있습니다. 그것은이 같은 보일 것이다 :

class Patient implements Comparator { 
... 
public int compareTo(Patient other) { 
    return getPriority() > other.getPriority() ? 1 : 0; 
} 

이 그런 자리에 당신이 당신의 사용 요구에 따라 큐

Set<Patient> queue = new TreeSet<Patient>(); 
queue.add(p1); 
queue.add(p2); 
//traverse in order of priority 
for(Patient p : queue) { 
    doStuff(); 
} 

Answer 2

를 사용하려면 ... Patient.java에서

을, 대답 TreeSets와 관련된 것은 아마도 당신이 원하는 것을 할 것입니다.

실제로 정렬 된 컬렉션이 아닌 큐가 필요한 경우에는 PriorityQueue이 유용 할 수 있습니다.

Answer 3

다음은 PriorityHeap의 간단한 구현 방법입니다. 꽤 빨리 코딩되어 일부 결함이있을 수 있지만 pushUp() 및 pushDown() 로직을 구현했습니다.

import java.util.Random; 

public class Heap { 

    private Double[] data; 
    private int lastItem; 

    public Heap(int initialSize) { 
     // to simplify child/parent math leave the first index empty 
     // and use a lastItem that gives us the size 
     data = new Double[initialSize]; 
     lastItem = 0; 
    } 

    public void insert(Double d) { 
     // double size if needed 
     // should have a matching shrink but this is example code 
     if (lastItem + 1 >= data.length) { 
      Double[] doubled = new Double[data.length * 2]; 
      System.arraycopy(data, 0, doubled, 0, data.length); 
      data = doubled; 
     } 
     data[lastItem + 1] = d; 
     lastItem++; 
     pushUp(lastItem); 
    } 

    public void pushDown(int index) { 

     if (lastItem > 1) { 

      int leftChildIndex = index * 2; 
      int rightChildIndex = leftChildIndex + 1; 

      // assume that neither child will dominate (in priority) 
      // the item at index 
      int indexToPromote = index; 
      // there may not be a left child 
      if (leftChildIndex <= lastItem) { 

       Double leftChild = data[leftChildIndex]; 
       Double tmp = data[index]; 
       if (tmp.compareTo(leftChild) < 0) { 
        indexToPromote = leftChildIndex; 
       } 

       // there might not be a right child 
       if (rightChildIndex <= lastItem) { 
        Double rightChild = data[rightChildIndex]; 
        tmp = data[indexToPromote]; 
        if (tmp.compareTo(rightChild) < 0) { 
         indexToPromote = rightChildIndex; 
        } 
       } 
      } 

      // did either child dominate the item at index 
      // if so swap and push down again 
      if (indexToPromote != index) { 
       swap(index, indexToPromote); 
       pushDown(indexToPromote); 
      } 
     } 
    } 

    public void pushUp(int index) { 
     if (index > 1) { 
      // equivalent to floor((double)index/2.0d); 
      // if item at index is greater than its parent 
      // push the item up to until if finds a home 
      int parentIndex = index >>> 1; 
      Double parent = data[parentIndex]; 
      Double item = data[index]; 
      if (item.compareTo(parent) > 0) { 
       swap(parentIndex, index); 
       pushUp(parentIndex); 
      } 
     } 
    } 

    public Double removeTop() { 
     // assume size is zero then examine other cases 
     Double top = null; 
     if (lastItem > 1) { 
      // save the top item and take the bottom item and place it 
      // at the top the push the new top item down until it 
      // finds a home 
      top = data[1]; 
      Double bottom = data[lastItem]; 
      lastItem--; 
      data[1] = bottom; 
      pushDown(1); 
     } else if (lastItem == 1) { 
      top = data[1]; 
      lastItem--; 
     } 
     return top; 
    } 

    public int size() { 
     return lastItem; 
    } 

    private void swap(int index1, int index2) { 
     Double temp = data[index1]; 
     data[index1] = data[index2]; 
     data[index2] = temp; 
    } 

    public static void main(String[] args) { 
     Heap heap = new Heap(4); 
     Random r = new Random(); 
     for (int i = 0; i < 100000; i++) { 
      Double d = Double.valueOf(r.nextDouble() * 100.0d); 
      heap.insert(d); 
     } 
     double max = Double.MAX_VALUE; 
     while (heap.size() > 0) { 
      Double top = heap.removeTop(); 
      if (top.doubleValue() > max) { 
       System.out.println("bad ordering..."); 
      } 
      max = top.doubleValue(); 
      System.out.println(max); 
     } 
     System.out.println("done..."); 
    } 
}