堆是通过数组来实现的，其中的元素从 0 开始计数，对于所有的 k 都有 a[k] <= a[2*k+1] 且 a[k] <= a[2*k+2]。 为了便于比较，不存在的元素被视为无穷大。 堆最有趣的特性在于 a[0] 总是其中最小的元素。
上面的特殊不变量是用来作为一场锦标赛的高效内存表示。 下面的数字是 k 而不是 a[k]:
0
1 2
3 4 5 6
7 8 9 10 11 12 13 14
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
在上面的树中，每个 k 单元都位于 2*k+1 和 2*k+2 之上。 体育运动中我们经常见到二元锦标赛模式，每个胜者单元都位于另两个单元之上，并且我们可以沿着树形图向下追溯胜者所遇到的所有对手。 但是，在许多采用这种锦标赛模式的计算机应用程序中，我们并不需要追溯胜者的历史。 为了获得更高的内存利用效率，当一个胜者晋级时，我们会用较低层级的另一条目来替代它，因此规则变为一个单元和它之下的两个单元包含三个不同条目，上方单元“胜过”了两个下方单元。
如果此堆的不变量始终受到保护，则序号 0 显然是最后的赢家。 删除它并找出“下一个”赢家的最简单算法方式是家某个输家（让我们假定是上图中的 30 号单元）移至 0 号位置，然后将这个新的 0 号沿树下行，不断进行值的交换，直到不变量重新建立。 这显然会是树中条目总数的对数。 通过迭代所有条目，你将得到一个 O(n log n) 复杂度的排序。
此排序有一个很好的特性就是你可以在排序进行期间高效地插入新条目，前提是插入的条目不比你最近取出的 0 号元素“更好”。 这在模拟上下文时特别有用，在这种情况下树保存的是所有传入事件，“胜出”条件是最小调度时间。 当一个事件将其他事件排入执行计划时，它们的调试时间向未来方向延长，这样它们可方便地入堆。 因此，堆结构很适宜用来实现调度器，我的 MIDI 音序器就是用的这个 :-)。
用于实现调度器的各种结构都得到了充分的研究，堆是非常适宜的一种，因为它们的速度相当快，并且几乎是恒定的，最坏的情况与平均情况没有太大差别。 虽然还存在其他总体而言更高效的实现方式，但其最坏的情况却可能非常糟糕。
堆在大磁盘排序中也非常有用。 你应该已经了解大规模排序会有多个“运行轮次”（即预排序的序列，其大小通常与 CPU 内存容量相关），随后这些轮次会进入合并通道，轮次合并的组织往往非常巧妙 1。 非常重要的一点是初始排序应产生尽可能长的运行轮次。 锦标赛模式是达成此目标的好办法。 如果你使用全部有用内存来进行锦标赛，替换和安排恰好适合当前运行轮次的条目，你将可以对于随机输入生成两倍于内存大小的运行轮次，对于模糊排序的输入还会有更好的效果。
另外，如果你输出磁盘上的第 0 个条目并获得一个可能不适合当前锦标赛的输入（因为其值要“胜过”上一个输出值），它无法被放入堆中，因此堆的尺寸将缩小。 被释放的内存可以被巧妙地立即重用以逐步构建第二个堆，其增长速度与第一个堆的缩减速度正好相同。 当第一个堆完全消失时，你可以切换新堆并启动新的运行轮次。 这样做既聪明又高效！
总之，堆是值得了解的有用内存结构。 我在一些应用中用到了它们，并且认为保留一个 ‘heap‘ 模块是很有意义的。 :-)
常用方法示例
1 import heapq 2 list1 = [3, 5, 6 ,13, 2, 22, 45, 1] 3 heapq.heapify(list1) #[1, 2, 6, 5, 3, 22, 45, 13] 对于列表使用堆排序是直接改变原列表，返回值为空； 4 # 原列表被修改以后符合对于所有的 k ，都有 heap[k] <= heap[2*k+1] 和 heap[k] <= heap[2*k+2]；排序出来是小顶堆排序的列表 5 print(list1, type(list1)) 6 #如果需要按数值顺序输出对应的值则需要使用heappop方法而不是直接迭代排序以后的列表 7 for loop in range(len(list1)): 8 print(heapq.heappop(list1)) 9 #1 2 3 5 6 13 22 45 10 11 list2 = [3, 5, 6 ,13, 2, 22, 45, 1] 12 heapq.heapify(list2) 13 heapq.heappush(list2, 34) #push和pop方法直接对liat也能使用，但是取出或者添加的数据不符合小顶堆的排序顺序，必须将其用headify方法排序后push pop方法才能达到预期的效果 14 print(list2) #[1, 2, 6, 5, 3, 22, 45, 13, 34] 15 for loop in range(len(list2)): 16 print(heapq.heappop(list2)) 17 #1 2 3 5 6 13 22 34 45 18 19 list3 = [3, 5, 6 ,13, 2, 22, 45, 1] 20 heapq.heapify(list3) 21 return_num = heapq.heappushpop(list3, 2) #heappushpop方法相比先调用push再调用pop效率更高；先将对象push进堆再返回最小值，总能保证返回的是push和原堆的最小值，堆大小不变 22 print(return_num, list3) #1 [2, 2, 6, 5, 3, 22, 45, 13] 23 24 list4 = [3, 5, 6 ,13, 2, 22, 45, 1] 25 heapq.heapify(list4) 26 return_num = heapq.heapreplace(list4, 0) #heapreplace用新值替换原堆的堆顶，然后对堆进行重新排序，堆大小不变；其返回值一定是原堆的堆顶 27 print(return_num, list4) #1 [0, 2, 6, 5, 3, 22, 45, 13] 28 29 list5 = [] 30 heap_merge_test = heapq.merge(list3,list4) #两个队合并，返回一个迭代器，迭代器产生值的顺序是堆排序，直接迭代出来的数据顺序不是预期的殊勋 31 print(heap_merge_test) 32 #遍历迭代器将其数据存入列表，这样使用pop方法就能按顺序将元素取出 33 for num in heap_merge_test: 34 list5.append(num) 35 print(list5) #[0, 2, 2, 2, 3, 5, 3, 6, 5, 6, 22, 22, 45, 13, 45, 13] 36 for loop in range(len(list5)): 37 print(heapq.heappop(list5)) #将list5从小到大输出 38 39 heap_merge_test1 = heapq.merge(list3,list4) 40 large_n = heapq.nlargest(5, heap_merge_test1) #[45, 45, 22, 22, 13] nlargest 从可迭代对象中返回最大的n个值,可迭代对象可以使迭代器也可以是未进行堆排序的列表，nsmallest效果相反 41 #可以使用heapq.nlargest(len(iter_obj), iter_obj)来对非生成器的迭代对象进行从大到小排序 42 print(large_n) 43 large_n1 = heapq.nlargest(3, list4) 44 print(large_n1) #[45, 22, 13] 45 46 list6 = [53, 1, 57, 8, 7, 9, 3, 4, 2, 66, 54, 89] 47 large_n2 = heapq.nlargest(3, list6) 48 print(large_n2) #[89, 66, 54]
原文：https://www.cnblogs.com/flags-blog/p/12670685.html