我是否正确地实现了基于堆的优先级队列？下堆是必要的吗？

Question

我相信我刚刚正确完成了以下作业：

Implement a heap based priority queue class using the vector representation, containing characters.

我的程序可以编译，并且在为剩余的作业实施时，我实现了所有期望的输出。我的问题是我是否真的正确地实现了堆。我的老师确定了基于堆的队列的三个关键方法：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);
            }
    }

但是，我觉得我的 downheap 函数只是搭载了 upheap，实际上完全没有必要。我有功能：

public static void add(char c)
{
    heap.add(c);
    upheap(heap.size() - 1);
}

（其中堆是一个 ArrayList）并且自动确保每个新条目都遵循堆顺序属性。我实际上从来没有最终使用 downheap 对任何东西进行排序——所以将它保留在 class 中有什么意义吗？我什么时候使用它？

如果有人想查看 class 中的其余方法，我会 post

Answer 1

实际上，您可以在 downheap() 方法中删除对 upheap() 的调用。如您所知，优先级队列堆中的根是最高优先级元素。 downheap 方法仅在删除最高优先级元素时才会出现，即根元素与最后一个元素交换。在你的例子中是 extractRoot() 方法。一旦你 extractRoot() 堆中的所有其他元素都会满足堆属性除了根上的那个。此外，当您向下移动根元素时，您正在交换较小的值，即 swap(j, smallerIndex)。因此，在 downheap() 的情况下，永远不会出现需要将元素向上移动堆的情况。

回答你的问题，当你调用 add() downHeap() 是没有用的，但是当你调用 extractMin() downheap() 是必要的。

Heap Image

我是否正确地实现了基于堆的优先级队列？下堆是必要的吗？

Am I implementing a heap-based priority queue correctly? Is downheap necessary?

java

heap

semantics