实际完成排序时堆排序算法的说明

Question

我对堆排序以及其中涉及的堆有一些疑问。

当你从一个数组构建 meax 堆时，实际上你构建了那个堆一个独立的对象，或者你只是安排数组以允许遵循算法来构建堆来构建一个最大堆？
按照表示最大堆的顺序重新排列数组后，您希望对该数组进行排序或生成另一个根据该数组的元素排序的数组。

执行此操作的算法是：

A -- 是一个数组示例：{5, 3, 17, 10, 19,84, 6, 22, 9}

堆排序(A)

1 BUILD-MAX-HEAP(A) 
// here you rearrange the array to represent a max heap or
 you actually construct a maxheap from that?

//a max heap array representation will be:
 {84, 22, 17, 10, 19, 5, 6, 3, 9}

 2 for i = A.length downto 2{
 3   exchange A[1] with A[i];
 4   A.heap-size = A.heap-size - 1; -- what this do in fact?
 5  MAX-HEAPIFY(A, 1);
}

从我的角度来看，它似乎实际上创建了一个数组 A 大小的堆（实际上是一个最大堆）。然后实际上迭代完成了什么，显然是在数组和 MAX-HEAPIFY 上——现在不知何故在一个尖叫的堆上。

你能一步步给我讲清楚吗？

Answer 1

之后，花了一些时间搜索我发现为什么有一个堆大小，还有一个array.length（数组实际上是表示堆的对象）。如果您实际上不希望在数组尾部有更多空闲点，并且当您在堆中添加一个元素时，您将仅增加 1 个点来增加数组大小，那么您实际上不需要堆大小，因为它们将始终相同，即 array.length.

但是，如果您这样做，那将是对数组堆的简单实现，因为每次添加或 delete/extract 一个元素 to/from heap/array该操作的成本将为 O(n)，因为您将被迫将旧数组的值复制到新数组中。

但是当我们 remove/extract 一个节点时，我们实际上并没有收缩数组，删除操作将花费我们 max/min 堆 O(log n)，为什么？

当我们从堆中删除 item/node - 实际上是根 - 我们只需执行以下操作：（为了简化我们将使用 int）

1 store the root in auxiliary variable: int returnObj = array[0]; cost O(1)
2 put the value from the last element of the heap(why not array because only the heap-size 
will decrease, the array length is the same) into the first 
heap/array element array[0]=array[heap-size-1]; heap-size at the beginning == array.length
2.1 right now we have have last element ==first element, 
and we need to shrink the heap represented on the array somehow. 
Now comes the reason to have a heap-size variable independent of array.length if we don't 
want to actually shrink the array because that operation will cost us O(n-1) time 
- instead of doing that we will use an auxiliary variable heap-size, 
as i mentioned above-to mark the end of the heap, to be able to ignore tail elements of the 
array that actually are not part of the heap any-more.
2.2 because right now the first element of the array and also is the first element of 
the heap is actually one of the smallest - i am saying is one of the smallest because 
it is not mandatory that the last element to be the smallest to satisfy  the heap property, 
example {84, 22, 17, 10, 19, 5, 6, 3, 9} is a max-heap - 
we need to call max-hipify over array[0] ... to ... array[heap-size] to recreate the max-heap 
again. That will cost us O(log n) in the worst case, much less than O(n).

3 return returnObj;

实际完成排序时堆排序算法的说明

heapsort algorithm clarifications when sorting is actually done

arrays

sorting

algorithm

heapsort