从实现的角度来说, 使用完全二叉树作为堆的前提的好处是, 完全二叉树非常容易实现, 甚至可以说是最容易实现的二叉树. 由于完全二叉树的节点编号是连续的, 那么它可以被拉平, 放进一个日常的数组中, 如
+---+
| 4 |
+---+
/ \
+---+ +---+
| 5 | | 9 |
+---+ +---+
/ \
+---+ +---+
| 8 | | 5 |
+---+ +---+
.----.
/--. \
+---+---+---+---+---+---+-----
| - | 4 | 5 | 9 | 8 | 5 | ...
+---+---+---+---+---+---+-----
\______/ /
\________/
.----.
/--. \
+---+---+---+---+---+---+-----
| 0 | 1 | 2 | 3 | 4 | 5 | ...
+---+---+---+---+---+---+-----
\______/ /
\________/
.----.
/--. \
+---+---+---+---+---+---+-----
| - | 0 | 1 | 2 | 3 | 4 | ...
+---+---+---+---+---+---+-----
\______/ /
\________/
i << 1, 2i+1 等效于 (i << 1) | 1, floor(i/2) 等效于 i >> 1, 这还能提供一丁点效率优化 (和一部分代码混乱程度加成, 以及大量的极客自豪感上升).既然堆的逻辑结构是数组, 那么可以采用
std::vector 作为存储数据结构. 此外, 将比较方式以模板形式抽出, 这样可以构造一个抽象的最值堆, 而不是死板的最大堆或者最小堆. 下面是堆的框架template
class heap {
std::vector<_T> array;
_Less const less;
typedef typename std::vector<_T>::size_type size_type;
public:
heap()
: array(1) /* insert a placeholder, array[0] */
, less(_Less())
{}
void push(_T const& value);
_T pop();
};