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

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 来对任何东西进行排序 - 那么将它保留在类中还有什么意义吗？我什么时候使用它？

如果有人想查看类中的其余方法，我将发布

Answer 1

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

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

Heap Image