优先级队列中正确的堆实现

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 正确地重新排列队列，代码执行此操作没有完成。 我还应该包括优先级队列代码，还是这已经太长了？

我正在使用 NetBeans IDE 6.0.1，如果有帮助的话。

Answer 1

根据您的使用要求，与 TreeSets 相关的答案很可能会满足您的要求。

但是，如果您确实需要一个队列，而不是排序的集合，那么内置的PriorityQueue 可能有用。

Answer 2

不完全回答你的问题，但对于 Java，你可能想研究一下内置的 Collection 类。 您可以获得优先级队列行为，但使用 TreeSet（一种有序集）并为 Patient 实例实现自定义比较器。 根据您想要实现的目标，这可能更可取。 它看起来像这样：

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