堆排序的目的是什么？
What is the purpose of having heap sort?
当我们构建堆时，数组中的元素会根据它是最大堆还是最小堆以特定顺序（升序或降序）排列。那么堆排序有什么用呢，自己建一个堆，把元素按顺序排列，时间复杂度更小？
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);
}
}
"那建堆的时候堆排序有什么用呢 自己把元素排好序"
看来你混淆了Heap Sort算法和heap数据结构的目的。让我们这样澄清：
heap 是一个 数据结构 ，它允许我们在不断变化的集合中重复查找列表的最小值或最大值。我们可以使用基于 sink() 的方法在 O(n) 中从头开始创建 heap。然后每个操作都需要 O(logn) 复杂度。但是，heap 不会为您提供 排序的 数组，它只会根据您的实现提供最大值或最小值。
另一方面，Heap Sort 算法使用 heap 数据结构为您提供排序的 array/collection。首先，它以 O(n) 的时间复杂度构建一个 heap。然后从底部开始，returns 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)
}
总之，构建堆本身并不能为您提供排序数组。
堆排序总结
堆排序是一个算法，可以总结为两步：
- 将输入数组转换为堆；
- 将堆转换为排序数组。
堆本身不是排序数组。
我们来看一个例子：
[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之前。
那么什么是堆？
什么是堆？
请注意，在上一节中，我区分了“堆”和“表示堆的数组”。先说什么是堆，再说什么是代表堆的数组
最大堆是在节点上具有值的二叉树，它满足以下两个属性：
- 子节点上的值总是低于其父节点上的值；
- 这棵树几乎是完整的，从这个意义上说，树的所有分支的长度几乎相同，最长和最短的分支之间最多相差 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]
注意，这正是我post开头的第一步堆排序后的数组。
在这个数组表示中，我们可以使用位置来确定哪个节点是哪个节点的子节点：位置i的节点有两个子节点，分别位于位置2*i+1和2*i+2.
此数组不是排序数组。但它代表一个堆，我们可以很容易地使用它来生成一个排序数组，在 n log(n) 操作中，通过重复提取最大元素。
如果堆排序是用外部二叉树实现的，那么我们可以使用最大堆或最小堆，通过重复选择最大元素或最小元素来对数组进行排序。但是，如果您尝试就地实现堆排序，将堆作为数组存储在正在排序的数组中，您会注意到使用最大堆比使用最小堆更方便，在order 通过重复选择最大元素并将其移动到数组末尾来按升序对元素进行排序。
当我们构建堆时，数组中的元素会根据它是最大堆还是最小堆以特定顺序（升序或降序）排列。那么堆排序有什么用呢，自己建一个堆，把元素按顺序排列，时间复杂度更小？
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);
}
}
"那建堆的时候堆排序有什么用呢 自己把元素排好序"
看来你混淆了Heap Sort算法和heap数据结构的目的。让我们这样澄清：
heap 是一个 数据结构 ，它允许我们在不断变化的集合中重复查找列表的最小值或最大值。我们可以使用基于 sink() 的方法在 O(n) 中从头开始创建 heap。然后每个操作都需要 O(logn) 复杂度。但是，heap 不会为您提供 排序的 数组，它只会根据您的实现提供最大值或最小值。
另一方面，Heap Sort 算法使用 heap 数据结构为您提供排序的 array/collection。首先，它以 O(n) 的时间复杂度构建一个 heap。然后从底部开始，returns 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)
}
总之，构建堆本身并不能为您提供排序数组。
堆排序总结
堆排序是一个算法，可以总结为两步：
- 将输入数组转换为堆；
- 将堆转换为排序数组。
堆本身不是排序数组。
我们来看一个例子：
[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之前。
那么什么是堆？
什么是堆？
请注意，在上一节中，我区分了“堆”和“表示堆的数组”。先说什么是堆，再说什么是代表堆的数组
最大堆是在节点上具有值的二叉树，它满足以下两个属性：
- 子节点上的值总是低于其父节点上的值；
- 这棵树几乎是完整的，从这个意义上说，树的所有分支的长度几乎相同，最长和最短的分支之间最多相差 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]
注意，这正是我post开头的第一步堆排序后的数组。
在这个数组表示中，我们可以使用位置来确定哪个节点是哪个节点的子节点：位置i的节点有两个子节点，分别位于位置2*i+1和2*i+2.
此数组不是排序数组。但它代表一个堆，我们可以很容易地使用它来生成一个排序数组，在 n log(n) 操作中，通过重复提取最大元素。
如果堆排序是用外部二叉树实现的，那么我们可以使用最大堆或最小堆，通过重复选择最大元素或最小元素来对数组进行排序。但是，如果您尝试就地实现堆排序，将堆作为数组存储在正在排序的数组中，您会注意到使用最大堆比使用最小堆更方便，在order 通过重复选择最大元素并将其移动到数组末尾来按升序对元素进行排序。