我相信我刚刚正确完成了以下任务：
使用包含字符的矢量表示实现基于堆的优先级队列类。
我的程序经过编译，在执行剩余的任务时，我实现了所有期望的输出。我的问题是我实际上是否正确实现了堆。我的老师为基于堆的队列确定了三种关键方法：downheap，upheap和extractMin。
public static void upheap(int j)
{
int p = parent(j);
if(heap.get(j) < heap.get(p)) { swap(j,p); }
if (j == 0) return;
upheap(p);
}
public static char extractRoot()
{
if (heap.size() == 0)
return 0;
char root = heap.get(0);
heap.set(0,heap.get(heap.size() - 1));
heap.remove(heap.size() - 1);
downheap(0);
return root;
}
public static void downheap(int j)
{
if(hasLeft(j))
{
int smallerIndex = left(j);
if(hasRight(j) && heap.get(right(j)) < heap.get(left(j)))
smallerIndex = right(j);
if(heap.get(j) > heap.get(smallerIndex))
{
swap(j, smallerIndex);
}
upheap(j);
downheap(smallerIndex);
}
}
但是，我感觉我的降级功能只是从升级中piggy带而来，实际上完全没有必要。我有功能：
public static void add(char c)
{
heap.add(c);
upheap(heap.size() - 1);
}
（其中heap是一个ArrayList），并自动确保每个新条目都遵循heap-order属性。我从来没有真正使用过堆来对任何东西进行排序-所以有什么要保留在课堂上的东西了吗？我什么时候使用它？
如果有人想在该类中查看其余方法，我将发布
最佳答案
实际上，您可以在downheap（）方法中删除对upheap（）的调用。
如您所知，优先级队列堆中的根是最高优先级元素。
仅当优先级最高的元素被删除（即根元素与最后一个元素交换）时，downheap方法才会出现。在您的情况下，extractRoot（）方法。一旦您提取了Root（），堆中的所有其他元素将满足除了根属性之外的所有堆属性。
同样，当您向下移动根元素时，您将交换较小的值，即swap（j，较小的索引）。因此，在出现downheap（）的情况下，永远不会需要将元素向上移动到堆中。
要回答您的问题，当您调用add（）时，downHeap（）是没有用的，但是当您调用extractMin（）时，downheap（）是必需的。
Heap Image