Корректная реализация кучи в очереди с приоритетами

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 или down правильно переставлял очередь, чего не выполняет код. Должен ли я также включить приоритетный код очереди, или он уже слишком длинный?

Я использую IDE NetBeans 6.0.1, если это поможет.

Answer 1

В зависимости от ваших требований к использованию, ответ относительно TreeSets, скорее всего, будет делать то, что вы хотите.

Однако если вам действительно нужна очередь, а не отсортированная коллекция, тогда может пригодиться встроенная PriorityQueue .

Answer 2

Вот простая реализация 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...");
    }
}

Answer 3

Не совсем отвечаю на ваш вопрос, но с Java вы можете захотеть взглянуть на встроенные классы Collection. Вы можете получить приоритетное поведение очереди, но используя TreeSet (тип упорядоченного набора) и реализуя собственный экземпляр Comparator for Patient. В зависимости от того, чего вы пытаетесь достичь, это может быть предпочтительнее. Это будет выглядеть примерно так:

In 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();
}