在哈布雷（Habré）上进行堆排序（这也是金字塔式排序）已经用一个或两次以上的好词记住了，但这一直是众所周知的信息。每个人都知道通常的二进制堆，但是算法理论也有：n堆；一堆基于莱昂纳多数的堆； Deramide（堆和二叉搜索树的混合体）；迷你锦标赛镜像（反向）堆；弱桩荣的堆二项式桩上帝知道其他什么东西……而不同年份中最聪明的计算机科学代表提出了使用这些金字塔结构的排序算法。谁在乎他们的工作-对于那些人，我们正在开始一连串的文章，专门讨论如何使用这些结构进行排序。堆的世界是多种多样的-希望您会感兴趣。
本文是在EDISON的支持下编写的。
我们从事移动应用程序的开发，并提供软件测试服务。
我们喜欢算法理论！;-)
有这样一类算法-按选择排序。总体思路是，减少数组的无序部分，因为它会搜索从数组重新排列成递增排序区域的最大元素。排序通常的选择是蛮力的。如果为求最大值而线性遍历数组很简单，则这种算法的时间复杂度不能超过O（n 2）。一堆
处理数组最高点的最有效方法是将数据组织成一个特殊的树结构，称为堆。这是一棵树，其中所有父节点不少于子节点。堆的其他名称- 金字塔，排序树。让我们看一下如何轻松，几乎免费地以树的形式呈现数组。取数组的第一个元素，并认为这是树的根-第一层的节点。接下来的2个元素是第二级的节点，即根元素的左右后代。接下来的4个元素是第3层的节点，即数组的第二个/第三个元素的右/左后代。接下来的8个元素是第4层的节点，是第3层的元素的后代。等等。在此图中，二叉树的节点严格位于数组中相应元素的严格下方：虽然，在这种扫描中更经常地描绘图中的树：如果您从这个角度看，那么很清楚为什么将一堆排序称为金字塔排序。不过，这与您将象棋大象称为军官，白嘴鸦称为图拉，女王/王后称为女王/王后一样。第i个元素的后代的索引由elementary确定（如果数组的第一个元素的索引被视为等于0，这在大多数编程语言中都是习惯的）：
2× i + 1的左后代，
右子级：2× i + 2 （我在图表上在动画中，传统上，数组的索引以1开头，其公式略有不同：左子元素：2× i和右子元素：2× i + 1，但是这些已经是很小的算术差异了。如果从这些公式得到的后代索引超出数组，则表示第i个项没有子项。第i个元素也可能是左后代（落在数组的最后一个元素（其中元素为奇数个）上），但是没有右元素。因此，任何数组都可以轻松地以树的形式表示，但是，这还不是堆，因为在数组中，某些子元素可能大于其父元素。为了使基于数组创建的树成为堆，需要对其进行适当的筛选。筛分
整理一堆的灵魂正在筛选。对元素的筛选是，如果它小于不可分割链中组合的子孙，则必须将该元素尽可能低地移动，并且将大子孙提升1级。该图显示了物料的筛选路径。蓝色表示要进行筛选的元素。绿色-分支中较大的后代。因为它们的尺寸比制作屏幕的蓝色结大，所以它们将被提升一级。来自最高蓝色节点的元素本身将移至绿色链中最低后代的位置。为了使分类树从普通树中脱颖而出并进一步支持该树处于此（分类）状态，需要进行筛选。在此图像中，重新分配了数组的元素，以便已将其布置在堆中。尽管该数组已分解为排序树，但尚未对其进行排序（升序或降序），尽管树中的所有后代均小于其父节点。但是，排序树中最大的元素始终位于主根中，这一点非常重要。堆排序::堆排序
该算法实际上很简单：- 阶段1.我们从整个数组中形成一个排序树。为此，我们从右向左传递元素（从最后到第一个），如果元素具有后代，则对其进行筛选。
- 2. . , . ( ) . , .. . , — . , .
经典金字塔排序实现的Python代码：
def HeapSort(data):
for start in range((len(data) - 2) / 2, -1, -1):
HeapSift(data, start, len(data) - 1)
for end in range(len(data) - 1, 0, -1):
data[end], data[0] = data[0], data[end]
HeapSift(data, 0, end - 1)
return data
def HeapSift(data, start, end):
root = start
while True:
child = root * 2 + 1
if child > end: break
if child + 1 <= end and data[child] < data[child + 1]:
child += 1
if data[root] < data[child]:
data[root], data[child] = data[child], data[root]
root = child
else:
break
算法复杂度
为什么简单堆是好的-与其他类型的树不同，它不需要单独存储（例如，必须在使用前创建基于数组的二进制搜索树）。任何数组都已经是一棵树，您可以在其中随时随地识别父级和后代。额外内存的复杂度为O（1），一切都会立即发生。至于时间的复杂性，这取决于筛分。O（log n）中绕过了一次筛分。首先，我们对n个元素进行筛选，以便从数组中构建初始堆-此步骤需要O（n log n）。在第二阶段，当我们取出n当前堆中的最大值，我们对剩余的未排序部分进行一次筛分，即 这一阶段也使我们付出O（n log n）的代价。总时间复杂度：O（n log n）+ O（n log n）= O（n log n）。而且，金字塔分类既没有退化也没有更好的情况。任何阵列都将以适当的速度处理，但不会降级或记录。平均而言，堆排序比快速排序要慢一些。但是对于quicksort，您可以选择一个计算机挂在其上的Killer阵列，但是对于heapsort，则不是。:: Ternary heapsort
让我们看一下三元堆。您不会从二进制中相信它，它的不同之处仅在于父节点的最大值不是两个，而是三个后代。在为第i个元素编码的三元堆中，对三个后代进行类似计算（如果第一个元素索引= 0）：左后代3× i + 1中间后代3× i + 2右后代3× i + 3（如果索引以1开头，如本文中的动画所示，然后在这些公式中您只需要减去1）。排序过程：一方面，与二进制堆相比，树中的级别数显着减少，这意味着筛选期间平均将减少交换。另一方面，要找到最小后代，则需要进行更多比较-因为现在的后代不再是两个，而是每个三个。总的来说，就时间复杂度而言-我们发现了某个地方，我们失去了某个地方，但总的来说是一样的。三元堆中的数据排序比二进制中的数据快一点，但是这种加速非常小。在金字塔式分类的所有变体中，算法的开发人员都倾向于采用二进制选项，因为三元算法据说更难以实现（尽管在算法中添加两三行额外的“困难”），并且速度增益很小。按n堆大小排序:: N-narny堆排序
当然，您不能止步于此，而是根据一堆串后代对任意数量的后代进行排序。也许如果您继续增加后代的数量，可以大大提高进程的速度？对于数组索引的第i个元素（如果计数为零），其N个后代的计算非常简单：第一个后代：N × i + 1第二个后代：N × i + 2第三个后代：N × i + 3...N个后代：N × i + N用于按N堆排序的Python代码：
def NHeapSort(data):
n = 3
for start in range(len(data), -1, -1):
NHeapSift(data, n, start, len(data) - 1)
for end in range(len(data) - 1, 0, -1):
data[end], data[0] = data[0], data[end]
NHeapSift(data, n, 0, end - 1)
return data
def NHeapSift(data, n, start, end):
root = start
while True:
child = root * n + 1
if child > end:
break
max = child
for k in range(2, n + 1):
current = root * n + k
if current > end:
break
if data[current] > data[max]:
max = current
if data[root] < data[max]:
data[root], data[max] = data[max], data[root]
root = max
else:
break
但是，更多并不意味着更好。如果将情况带到极限，并为N个元素的数组获取N个后代，则按一堆排序将退化为按通常选择进行排序。而且，这也会成为按选择排序的更差版本，因为将执行无意义的手势：筛选将首先将最大值放在数组的第一位，然后将最大值发送到末尾（在选择排序中，最大值将立即发送到末尾）。如果三元堆最小地超过了二进制，则四元组已经丢失。在几个中找到最大后代变得太昂贵了。下一个系列预告片
因此，二元/三元/ n堆的主要缺点是无法跳转，其复杂度高于O（n log n）。摆脱僵局的方法是在排序中使用更复杂的堆品种。一周之内，我们将了解Edsger Dijkstra对此的看法。单击动画以转到带有以下排序的文章参考文献
堆 / 金字塔系列文章：
AlgoLab应用程序添加了按n堆排序。要选择后代数，请在此类单元格的注释中，为n指定一个数字。可能值的范围是2到5（不再有意义，因为对于n> = 6，不能保证在正常比例下具有三个嵌套级别的动画适合屏幕）。