优化堆排序的堆结构 [英] Optimizing heap structure for heapsort

问题描述

我正在使用堆来实现堆排序.为此，将插入每个要排序的值.插入方法调用heapifyUp()(又名siftUp)，因此这意味着每次插入另一个值时都会调用heapifyUp.这是最有效的方法吗?

I'm implementing heapsort using a heap. To do this each value to be sorted is inserted. The insertion method calls heapifyUp() (aka siftUp) so this means each time another value is inserted heapifyUp is called. Is this the most efficient way?

另一个想法是插入所有元素，然后调用heapifyUp.我猜必须在每个堆上调用heapifyUp?这样做得更好吗?

Another idea would be to insert all elements, and then call heapifyUp. I guess heapifyUp would have to be called on each one? Is doing it like this better?

推荐答案

插入每个元素将在O(n log n)时间内构建堆.如果将所有元素添加到数组中，然后重复调用heapifyUp()，则同样.

Inserting each element will build the heap in O(n log n) time. Same thing if you add all the elements to an array and then repeatedly call heapifyUp().

弗洛伊德算法可在O(n)时间内自底向上构建堆.这个想法是，您采用任意顺序的数组，并从中间开始，将每个项目 down 筛选到适当位置.该算法是:

Floyd's Algorithm builds the heap bottom-up in O(n) time. The idea is that you take an array that's in any order and, starting in the middle, sift each item down to its proper place. The algorithm is:

for i = array.length/2 downto 0
{
    siftDown(i)
}

您从中间开始，因为数组中最后的length/2个项是叶子.他们不能被筛选.通过从中间开始工作，可以减少必须移动的项目数.

You start in the middle because the last length/2 items in the array are leaves. They can't be sifted down. By working your way from the middle, up, you reduce the number of items that have to be moved.

下面的示例将一个由7个项目组成的数组变成一个堆，显示了已完成工作量的差异.

The example below, turning an array of 7 items into a heap, shows the difference in the amount of work done.

heapifyUp()方法

[7,5,6,1,2,3,4]  (starting state)

从末尾开始，然后将项目向上泡.

Start at the end and bubble items up.

将4移动到正确的位置

[7,5,4,1,2,3,6]
[4,5,7,1,2,3,6]

将3移到其位置

[4,5,3,1,2,7,6]
[3,5,4,1,2,7,6]

将2移动到其位置

[3,2,4,1,5,7,6]
[2,3,4,1,5,7,6]

将1移动到其位置

[2,1,4,3,5,7,6]
[1,2,4,3,5,7,6]

现在堆已经整理好了.进行了8次交换，您仍然需要检查4、2和1.

The heap is now in order. It took 8 swaps, and you still have to check 4, 2, and 1.

弗洛伊德算法

[7,5,6,1,2,3,4]  (starting state)

从中点开始并向下过滤.在从0开始的7项数组中，中点是3.

Start at the halfway point and sift down. In a 0-based array of 7 items, the halfway point is 3.

将1移动到其位置

[7,5,6,1,2,3,4]  (no change. Remember, we're sifting down)

将6移到其位置

[7,5,3,1,2,6,4]

将5移动到其位置

[7,1,3,5,2,6,4]
[7,1,3,4,2,6,5]

将7移动到其位置

[1,7,3,5,2,6,4]
[1,2,3,5,7,6,4]

我们完成了.进行了5次交换，没有其他可检查的内容.

And we're done. It took 5 swaps and there's nothing else to check.

这篇关于优化堆排序的堆结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！