Bit Focus

在前一篇文章中纸上谈了堆的性质以及如何在插入元素和弹出最值时保持这些性质. 这篇文章将聊聊实现方式.
从实现的角度来说, 使用完全二叉树作为堆的前提的好处是, 完全二叉树非常容易实现, 甚至可以说是最容易实现的二叉树. 由于完全二叉树的节点编号是连续的, 那么它可以被拉平, 放进一个日常的数组中, 如

+---+ | 4 | +---+ / \ +---+ +---+ | 5 | | 9 | +---+ +---+ / \ +---+ +---+ | 8 | | 5 | +---+ +---+

这样一棵完全二叉树可以被转换成

.----. /--. \ +---+---+---+---+---+---+----- | - | 4 | 5 | 9 | 8 | 5 | ... +---+---+---+---+---+---+----- \______/ / \________/

其中的线连接节点与它们的子节点. 如果用节点的编号来标识这个数组, 则会是

.----. /--. \ +---+---+---+---+---+---+----- | 0 | 1 | 2 | 3 | 4 | 5 | ... +---+---+---+---+---+---+----- \______/ / \________/

这里有个很奇妙的性质, 索引为 i 的节点, 它的左子节点的索引是 2i, 而右子节点的索引是 2i+1, 其父节点索引则是 floor(i/2) (根节点除外). 如果用 0 号节点而不是 1 号节点存储根节点呢? 如

.----. /--. \ +---+---+---+---+---+---+----- | - | 0 | 1 | 2 | 3 | 4 | ... +---+---+---+---+---+---+----- \______/ / \________/

也能很容易计算, 索引为 i 的节点, 左子节点索引是 2i+1, 右子节点索引是 2i+2, 父节点索引是 floor((i-1)/2). 似乎也没什么太大区别. 不过, 之前那种计算方式的好处在于, 2i, 2i+1, i/2 这样的算式都能换成极快的位运算: 2i 等效于 i << 1, 2i+1 等效于 (i << 1) | 1, floor(i/2) 等效于 i >> 1, 这还能提供一丁点效率优化 (和一部分代码混乱程度加成, 以及大量的极客自豪感上升).
既然堆的逻辑结构是数组, 那么可以采用 std::vector 作为存储数据结构. 此外, 将比较方式以模板形式抽出, 这样可以构造一个抽象的最值堆, 而不是死板的最大堆或者最小堆. 下面是堆的框架

template <typename _T, typename _Less>
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();
};

	Back to Bit Focus
	NijiPress - Copyright (C) Neuron Teckid @ Bit Focus
	About this site