如果您想了解如何在 Python 中实现堆排序,那么标准库模块就是您的最佳选择heapq
。 Python 有堆排序的 C 和 Python 实现heapq
模块定义了 Python 模块,然后用 C 模块覆盖它们(如果可用)。这意味着您可以阅读和理解 Python 实现,但如果您实际使用它,则可以获得 C 版本的好处。
最后给出了使用该模块的快速示例:
heap = []
data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
for item in data:
heappush(heap, item)
sort = []
while heap:
sort.append(heappop(heap))
print sort
堆由部分排序的列表表示,该列表具有这样的约束:对于列表中索引 n 处的每个元素,该关系成立heap[n] <= heap[n*2+1] and heap[n] <= heap[n*2+2]
(忽略不存在的元素)。这是一种将二叉树折叠为简单列表以便于存储的简单方法。
heappush()
将一个新元素放入列表中以保持不变性,heappop()
删除最小的元素。heapify(somelist)
就地重新排序列表以满足不变量。
当您只想对列表的一部分进行排序(给我最小的 k 个项目),或者您想在不断接收进入列表的新项目的同时处理最小的项目时,堆排序非常有用。后者的一个很好的例子是操作系统任务调度程序,您可以在其中按优先级顺序保留一堆可运行线程,并且每当您需要调度线程运行时,都可以快速从堆中弹出最高优先级的可运行线程。
Edit:有几个原因可以解释为什么列表/数组比显式树结构更适合堆存储。最明显的是,显式树具有更大的内存开销(涉及每个对象内的指针或为堆中的每个对象分配一个单独的对象),并且当对象在堆内移动时速度也会变慢更新指向孩子和可能的父母的多个指针。
不太明显的是,您需要能够轻松获取最后一个元素,这在列表中很容易,但这意味着您还需要存储和更新每个元素上的同级指针。您需要能够轻松获取最后一个元素的原因是,要添加一个元素,请将其设为最后一个元素,然后相对于其父元素和同级元素对其重新排序(O(log n) 操作)或删除最小的,您只需将当前的最后一个元素放在其位置并向下重新排序。如果您没有 O(1) 访问树的最后一个元素的权限,那么这两个操作都会对性能造成严重影响。