About
RSS

Bit Focus


日常的数据结构 - 堆的实现与第 K 最小堆

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

        +---+
        | 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();
};

Permanent Link: /p/441 Load full text

Post tags:

 C++
 Algorithm
 Template
 Heap
 Order Statistic
 Generic Programming
 Data Structure

日常的数据结构 - 动态最值统计与堆

    如果设计一个顺序统计系统, 需要动态向集合内添加元素, 又可以随时从集合中取得并丢弃最小值. 由于集合中有集合会被移除, 因此接下来再次取最小值时如果重新扫一次集合, 时间开销会相当大. 在一般情形中, 若为了均衡时间开销, 需要考虑维护一个更复杂的数据结构.
    这个数据结构建立在满二叉树 (full binary tree)完全二叉树 (complete binary tree)的概念上.
    "满" 这个字眼提示在树的每一层都摆满了节点, 而这恰好又是个充要条件, 即如果一棵二叉树每一层都堆满了节点, 那么它就是满二叉树. 满二叉树的定义干脆就按节点个数来: 一棵二叉树如果深度为 K, 而拥有 2K-1 个节点, 那么它就是一棵满二叉树. 如下面是 2 层和 3 层满二叉树, 分别拥有 3 个和 7 个节点

                             +---+
                             | a |
    +---+                    +---+
    | a |               .---'     `---.
    +---+            +---+           +---+
   /     \           | b |           | c |
+---+   +---+        +---+           +---+
| b |   | c |       /     \         /     \
+---+   +---+    +---+   +---+   +---+   +---+
                 | d |   | e |   | f |   | g |
                 +---+   +---+   +---+   +---+

    而如果一棵二叉树满足
  • 除了最后一层, 其余层构成一棵满二叉树
  • 最后一层从右起缺少 0 个或多个连续的节点
那么它就是一棵完全二叉树. 更直观一些, 将一个满二叉树的节点按照广度优先 (即逐层向下) 遍历的方式顺序编号, 编号从 1 开始 (而不是从 0 开始), 如

Permanent Link: /p/434 Load full text

Post tags:

 Data Structure
 Heap
 Algorithm
 Order Statistic


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