Правильная реализация кучи в очереди приоритетов

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 вы можете захотеть изучить встроенные классы Collection. Вы можете получить поведение очереди приоритетов, но используя TreeSet (тип упорядоченного набора) и реализацию пользовательских экземпляров Comparator для пациентов. В зависимости от того, чего вы пытаетесь достичь, это может быть предпочтительным. Это будет выглядеть примерно так:

В Patient.java ...

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

В зависимости от ваших требований использования, ответ относящиеся к 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..."); 
    } 
}