Korrekte Heap-Implementierung in einer Prioritätswarteschlange

Question

Mein Problem ist eher semantisch als funktional, da der Code die Funktionen deQueue und enQueue korrekt zu implementieren scheint.

Die reheapDown und reheapUp Funktionen falsch verwendet werden, und ich glaube, das Problem in meinem Haufen Funktion eine einfache Prioritätswarteschlange System neu zu ordnen, um, wenn ein Patient Objekt entfernt wird,

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; 
} 
} 

Die Idee ist, liegt ReheapUp oder Runter neu geordnet die Warteschlange, die der Code nicht erreicht. Sollte ich auch den Priority Queue-Code angeben, oder ist das schon zu lang?

Ich benutze NetBeans IDE 6.0.1, wenn das hilft.

Answer 1

Nicht genau Ihre Frage zu beantworten, aber mit Java können Sie in die integrierten Collection-Klassen schauen. Sie können das Verhalten der Prioritätswarteschlange erhalten, aber ein TreeSet (eine Art von Ordered-Set) verwenden und einen benutzerdefinierten Comparator für Patienteninstanzen implementieren. Je nachdem, was Sie erreichen möchten, ist dies möglicherweise vorzuziehen. Es würde wie folgt aussehen:

In Patient.java ...

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

Dann an der Stelle Sie die Warteschlange

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

Answer 2

Je nach Nutzungsanforderungen verwenden möchten, ist die Antwort in Bezug auf TreeSets wird wahrscheinlich tun, was Sie wollen.

Wenn Sie jedoch wirklich brauchen eine Warteschlange, im Gegensatz zu einer sortierten Sammlung, dann die eingebaute PriorityQueue kann von Nutzen sein.

Answer 3

Hier ist eine einfache Implementierung eines PriorityHeap. Ich habe es ziemlich schnell programmiert, so dass es einige Fehler haben kann, aber ich habe die pushUp() und pushDown() Logik implementiert.

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..."); 
    } 
}