当我们构建堆时，数组中的元素按照特定的顺序排列(升序或降序)，这取决于它是最大堆还是最小堆。那么，当构建堆本身以较低的时间复杂度排序元素时，堆排序有什么用呢?
void build_heap (int Arr[ ])
{
for(int i = N/2-1 ; i >= 0; i-- )
{
down_heapify (Arr, i, N);
}
}
void heap_sort(int Arr[], int N)
{
build_heap(Arr);
for(int i = N-1; i >= 1; i--)
{
swap(Arr[i], Arr[0]);
down_heapify(Arr, 0, i+1);
}
}
堆排序汇总
堆分类是一种算法，可分为两步:
- 将输入数组转换为堆;
- 将堆转换为排序数组。
堆本身是而不是一个已排序的数组。
让我们看一个例子:
[9, 7, 3, 5, 4, 2, 0, 6, 8, 1] # unsorted array
convert into heap
[9, 8, 3, 7, 4, 2, 0, 6, 5, 1] # array representing a max-heap
sort
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] # sorted array
如果你仔细观察，你会注意到我的例子中的第二个数组，它表示一个堆，并没有完全排序。元素的顺序看起来比原始未排序数组中的随机程度低;它们看起来几乎是按降序排列的;但它们并没有完全排序。数组中3在7之前，0在6之前
堆是什么?
什么是堆?
注意，在上一节中，我区分了"堆"one_answers"堆"。以及"表示堆"的数组。让我们先讨论一下什么是堆，然后再讨论什么是表示堆的数组。
最大堆是一个结点上都有值的二叉树，它满足以下两个性质:
- 子节点上的值总是小于父节点上的值;
- 树是几乎完整的，即树的所有分支长度几乎相同，最长和最短的分支之间的差异不超过1;此外，最长的分支必须在左边，最短的分支必须在右边。
在我给出的例子中，堆是这样构造的:
9
/
8 3
/ /
7 4 2 0
/ / / /
6 5 1
你可以检查这个二叉树满足堆的两个属性:每个子树的值都比父树的值低，所有分支的长度几乎相同，每个分支总是有4或3个值，最长的分支在左边，最短的分支在右边。
什么是代表堆的数组?
将二叉树存储到数组中通常非常不方便，二叉树通常使用指针实现，有点像链表。然而，堆是一个非常特殊的二叉树，它的"几乎是完全的"。属性对于将其实现为数组非常有用。
我们所要做的就是从左到右逐行读取值。在上面的堆中，我们有四行:
9
8 3
7 4 2 0
6 5 1
只需将这些值按顺序存储在数组中:
[9, 8, 3, 7, 4, 2, 0, 6, 5, 1]
请注意，这正是在我的文章开头的堆排序第一步之后的数组。
在这个数组表示中，我们可以使用位置来确定哪个节点是哪个节点的子节点:位置i的节点有两个子节点，分别位于位置2*i+1和2*i+2。
这个数组是不是一个已排序的数组。但它代表一个堆，我们可以很容易地使用它来生成一个排序数组，在n log(n)操作中，通过重复提取最大元素。
如果堆排序是用外部二叉树实现的，那么我们可以使用最大堆或最小堆，并通过重复选择最大元素或最小元素来对数组进行排序。但是，如果您尝试就地实现堆排序，将堆作为数组存储在正在排序的数组中，您会注意到使用最大堆比最小堆方便得多，通过重复选择最大元素并将其移动到数组末尾，以便按递增顺序对元素进行排序。
">那么，堆排序在构建堆本身时又有什么用呢?"似乎你混淆了Heap Sort算法和heap数据结构的目的。让我们这样来说明:
heap是一个数据结构，它允许我们在不断变化的集合中重复查找列表的最小值或最大值。我们可以使用基于sink()的方法在O(n)中从头创建heap。然后每个操作的复杂度为O(logn)。然而，heap不为您提供一个排序的数组，它只是根据您的实现给出最大值或最小值。
另一方面，Heap Sort算法使用heap数据结构为您提供排序的数组/集合。首先，它在O(n)时间复杂度中构建heap。然后它从底部开始，逐个返回max/min到实际数组。在每次迭代中，你必须heapify你的heap正确地获得下一个max/min，这总共给O(n*logn)时间复杂度。
void heap_sort(int Arr[], int N)
{
build_heap(Arr); // O(n) time complexity
for(int i = N-1; i >= 1; i--) // n iteration
{
swap(Arr[i], Arr[0]);
down_heapify(Arr, 0, i+1); //O(logn) time complexity
}
// in total O(n) + O(n*logn) = O(n*logn)
}