第一次懵懵懂懂接触 Heap 是在学信息检索的时候, 讲到用 min heap 直接在 disk 上对 posting lists 做合并操作.
今天看了 < 算法导论(3rd)> 第六章堆排序, 感触颇深, 以此博客记录一下.
6.1 堆:
概要
(二叉) 堆可以看作为一个完全二叉树. 个人觉得它最神奇的特性就是每个相邻节点 (父节点 / 左孩子 / 右孩子) 的关联关系可以轻松取到:
二叉堆又分为最小堆和最大堆.
定义: 对于每个节点(除了 root 节点), 左孩子和右孩子的值都小于父节点(左右孩子的值并没有顺序).
练习:
(TODO)
6.2 维护堆的性质:
MAX-HEAPIFY:
发现看了一会文字描述, 云里雾里的, 还不如直接看伪代码, 瞬间就明白了:
大意就是说, 在一个最大堆中, 选取一个 node(A[i]), 如果 max(node.val, node.left.val, node.right.val)是 node.val, 程序结束; 否则就将 node 和 left 和 right 中的较大的交换. 交换之后, 递归调用 MAX-HEAPIFY(A, i)
练习:
(TODO)
6.3 建堆:
BUILD-MAX-HEAP:
SHOW ME THE CODE:
伪代码的第二行可能有些看不懂, 意思就是说对所有非叶子节点, 从右到左, 从下到上, 循环执行上一章的MAX-HEAPIFY(6.3-2: 对循环执行顺序的解释.)
练习:
(TODO)
6.4 堆排序算法:
HEAPSORT = BUILD-MAX-HEAP(6.3) + MAX-HEAPIFY(6.2):
伪代码:
上图中每个循环的核心思想就是:
- 将第一个元素 (当前堆的最大值) 和最后一个元素交换
(line 3) - 取出当前最大值, 并对之前的最后一个元素 (交换后为第一个元素, A[1]) 做 MAX-HEAPIFY(A, 1)
(line 5)练习:
(TODO)
6.5 优先队列(priority queue):
一个最大 优先队列 支持以下四个操作:
1) MAXIMUM:
返回 S 中具有最大值的元素(就是返回第一个元素) → return A[1]
2) HEAP-EXTRA-MAX:
和 MAXIMUM 不同的是, 除了获取到最大元素, 还要将此元素从优先队列中取出.
伪代码:
其实就是 6.4 堆排序 中的第一次循环.
3) HEAP-INCREASE-KEY:
意思就是说将某个元素 A[i]更新值 (变大), e.g. 3 → 13...
伪代码:
说明:
如果大于 parent.val 就一直和 parent 做交换.
4) MAX-HEAP-INSERT:
这个就比较神奇了, 插入一个新元素, 但强行使用 HEAP-INCREASE-KEY 来实现:
个人思考:
堆排序是否也可以使用 MAX-HEAP-INSERT + HEAP-EXTRA-MAX 实现呢? 时间复杂度也是 O(lg n)
练习:
(TODO)
思考题:
TODO