-1

My issue is more semantic than functional, As the code does seem to implement the deQueue and enQueue functions correctly.

The reheapDown and reheapUp functions are being used incorrectly, And i believe the issue lies in my heap function

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

The idea is to rearrange a simple priority queue system so when a patient object is removed, ReheapUp or down correctly rearranges the queue, Which the code does not accomplish. Should i also include the priority queue code, Or is this already too lengthy?

I am using NetBeans IDE 6.0.1, If that helps.

4

3 回答 3

1

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

然而，如果你真的需要一个队列，而不是一个排序的集合，那么内置的PriorityQueue可能会很有用。

于 2009-03-16T12:44:39.313 回答
0

不完全回答您的问题，但对于 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();
}
于 2009-03-16T12:40:09.200 回答
0

这是一个 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...");
    }
}
于 2011-05-19T20:01:22.867 回答