知识卡片
堆序不等于整体排序
最小堆保证根部可取最小元素,但内部列表不一定整体有序。heapify建立堆后,反复heappop才按从小到大取出;每次弹出会破坏性地修改堆并维护剩余堆序,代价与堆大小M相关,常见为O(log M)。需要原数据时先作副本,不要把打印出来的堆数组当成已排序结果。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
堆最重要的特性就是heap[0]总是最小那个的元素。此外,接下来的元素可依次通过heapq.heappop()方法轻松找到。该方法会将第一个元素(最小的)弹出,然后以第二小的元素取而代之(这个操作的复杂度是O(logN),N代表堆的大小)。例如,要找到第3小的元素,可以
参考来源
- 位置:《Python Cookbook(第3版)中文版》1.4 找到最大或最小的N个元素(spine9;extracted/Python Cookbook(第3版)中文版/_epub-src/OEBPS/Text/part0007.xhtml;u006-ch01-006)。
- 结论依据:本条问题、全部示例代码与讨论已完整读取;区分算法性质、历史实现说明与本次未执行的性能结论。
- 原始内容:堆最重要的特性就是heap[0]总是最小那个的元素。此外,接下来的元素可依次通过heapq.heappop()方法轻松找到。该方法会将第一个元素(最小的)弹出,然后以第二小的元素取而代之(这个操作的复杂度是O(logN),N代表堆的大小)。例如,要找到第3小的元素,可以