堆排序的下限？
众所周知，堆排序的最坏情况运行时是Ω（n lg
n），但我很难理解为什么会这样。特别地，堆排序的第一步（产生最大堆）花费时间Θ（n）。然后是n个堆删除。我明白为什么每次删除堆都需要时间O（lg n）;
重新平衡堆涉及气泡减少操作，该操作需要在堆高度上花费时间O（h），并且h = O（lg n）。但是，我没有看到的是为什么第二步应该取Ω（n lg
n）。似乎任何单独的堆出队都不一定会导致移动到顶部的节点一直沿树向下冒泡。
我的问题是-有人知道堆排序的最佳情况下的良好下界证明吗？
问题答案：
所以我做了一些自我挖掘，看来这个结果实际上是最近的！我能找到的第一个下界证明是从1992年开始的，尽管heapsort本身是在1964年发明的。
正式的下界证明是基于Schaffer和Sedgewick的“ The Heapsort分析”论文。这是略微释义的版本，省略了一些技术细节。
首先，假设对于某些k，n = 2 k -1，这保证了我们有完整的二进制堆。稍后我将展示如何单独处理这种情况。因为我们有2 k
-1个元素，所以堆排序的第一遍将在Θ（n）中建立一个高度为k的堆。现在，请考虑此堆中出队的前半部分，这将删除2
k-1堆中的节点。第一个关键的观察结果是，如果您使用起始堆，然后在此处标记实际上最终出队的所有节点，它们将构成堆的子树（即，每个被出队的节点都有一个父节点也被出队）。您可以看到这是因为，如果不是这种情况，那么即使某个节点本身已经出队，也可能会有某个节点的（较大）父节点没有出队，这意味着值是乱序的。
现在，考虑该树的节点如何在整个堆中分布。如果您将堆的级别标记为0、1、2，…，k-1，那么在级别0、1、2，…，k-2中将有一定数量的这些节点（即，除了树的底层以外的所有内容）。为了使这些节点从堆中出队，必须将它们交换到根，并且一次只能交换一个级别。这意味着降低堆排序运行时间的一种方法是计算使所有这些值都达到根所必需的交换次数。实际上，这正是我们要做的。
我们需要回答的第一个问题是-最大的2 k-1个节点中有多少个不在堆的最底层？我们可以证明，这不大于2 k-2。假设堆最低层中至少有2 k-2
+1个最大节点。然后，这些节点的每个父节点也必须是k-2级的大节点。即使在最佳情况下，这也意味着k-2级必须至少有2 k-3 +
1个大节点。在k-3级中至少会有2 k-4 +1个大节点，依此类推。总结所有这些节点，我们得出有2 k-2 + 2 k-3 + 2 k-4 + …
+ 20 + k个大节点。但是此值严格大于2 k-1，这与我们在这里仅使用2 k-1个节点的事实相矛盾。
好的…我们现在知道在底层最多有2 k-2个大节点。这意味着在前k-2层中必须至少有2 k-2个大节点。现在我们问-
在所有这些节点上，从该节点到根的距离的总和是多少？那么，如果我们有2 K-2节点的地方放置在一个完整的堆，然后最多2 K-3人可在第一个K -
3个级别，因此至少有2 K-2 - 2 K-在级别k-2中3 = 2 k-3个重节点。因此，需要执行的交换总数至少为（k-2）2 k-3。由于n = 2
k-1，k =Θ（lg n），因此根据需要该值为Θ（nlg n）。
-
本文向大家介绍堆排序，包括了堆排序的使用技巧和注意事项，需要的朋友参考一下 堆排序是在堆数据结构上执行的。我们知道堆是一个完整的二叉树。堆树可以有两种类型。最小堆或最大堆。对于最小堆，根元素最小，对于最大堆，根元素最大。形成堆之后，我们可以从根中删除一个元素并将最后一个元素发送到根。完成这些交换过程后，我们需要重新堆放整个数组。通过从根目录删除元素，我们可以对整个数组进行排序。 堆排序技术的复杂性
-
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法： 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列； 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列； 堆排序的
-
我在[17,98,89,42,67,54,89,25,38]中有一个数字列表，从左到右插入到一个空堆中。生成的堆是什么？
-
我只是想看看我是否理解教授和在线资源所说的话。 对于heapSort算法，第一个元素的索引从0开始。 对于最大堆，如果子堆大于父堆，则percolate down应将最大子堆与其父堆交换，例如（这是用于赋值，因此我尝试发布尽可能少的代码）： 所以最后，最大元素应该在索引0处。 如果这是正确的，我不理解的是heapSort实现： 最大堆中的渗滤层不应该将最大的元素放在索引0处吗？在这种情况下，为什么
-
基数排序 from typing import List def radix_sort(arr: List) -> List: """ 基础排序 核心思想: 一共有0-9为数字的桶，一共10个，一共循环数组中最大数的位数次（如最大数是1000则是4次个十百千位分别循环）， 每一次循环依次从数中取出个、十、百、千、万...位数上的数值放到对应的桶中，如果该位上没有
-
本文向大家介绍C#排序算法之堆排序，包括了C#排序算法之堆排序的使用技巧和注意事项，需要的朋友参考一下 本文实例为大家分享了C#实现堆排序的具体代码，供大家参考，具体内容如下 代码： 以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持呐喊教程。
-
主要内容：src/runoob/heap/HeapSort.java 文件代码：上一节的堆排序，我们开辟了额外的空间进行构造堆和对堆进行排序。这一小节，我们进行优化，使用原地堆排序。 对于一个最大堆，首先将开始位置数据和数组末尾数值进行交换，那么数组末尾就是最大元素，然后再对W元素进行 shift down 操作，重新生成最大堆，然后将新生成的最大数和整个数组倒数第二位置进行交换，此时到处第二位置就是倒数第二大数据，这个过程以此类推。 整个过程可以用如下图表示： Java 实
-
主要内容：src/runoob/heap/Heapify.java 文件代码：一、概念及其介绍 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。 堆是一个近似 完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。 二、适用说明 我们之前构造堆的过程是一个个数据调用 insert 方法使用 shift up 逐个插入到堆中，这个算法的时候时间复杂度是 O(nlogn)，本小节介绍的一种构造堆排序的过程，称为 Hea