第一次懵懵懂懂接触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