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

标签： std Algorithm Data Struct Order Statistic | 发表时间：2011-10-04 01:01 | 作者：Neuron Teckid Linker Lin
出处：http://blog.bitfoc.us

    如果设计一个顺序统计系统, 需要动态向集合内添加元素, 又可以随时从集合中取得并丢弃最小值. 由于集合中有集合会被移除, 因此接下来再次取最小值时如果重新扫一次集合, 时间开销会相当大. 在一般情形中, 若为了均衡时间开销, 需要考虑维护一个更复杂的数据结构.
    这个数据结构建立在满二叉树 (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 开始), 如

                            +---+
                            | 1 |
                            +---+
               .-----------'     `-----------.
            +---+                           +---+
            | 2 |                           | 3 |
            +---+                           +---+
       .---'     `---.                 .---'     `---.
    +---+           +---+           +---+           +---+
    | 4 |           | 5 |           | 6 |           | 7 |
    +---+           +---+           +---+           +---+
   /     \         /     \         /     \         /     \
+---+   +---+   +---+   +---+   +---+   +---+   +---+   +---+
| 8 |   | 9 |   | A |   | B |   | C |   | D |   | E |   | F |
+---+   +---+   +---+   +---+   +---+   +---+   +---+   +---+

    在这棵树上删除一些编号最大的节点, 得到的子树就是完全二叉树 (满二叉树本身也就是完全二叉树), 如

                            +---+
                            | 1 |
                            +---+
               .-----------'     `-----------.
            +---+                           +---+
            | 2 |                           | 3 |
            +---+                           +---+
       .---'     `---.                 .---'     `---.
    +---+           +---+           +---+           +---+
    | 4 |           | 5 |           | 6 |           | 7 |
    +---+           +---+           +---+           +---+
   /     \         /     \         /
+---+   +---+   +---+   +---+   +---+
| 8 |   | 9 |   | A |   | B |   | C |
+---+   +---+   +---+   +---+   +---+

    如果在编号较大的节点删除之前, 某个小号节点被删去了, 这样的子树则不是完全二叉树, 如

                            +---+                 -.
                            | 1 |                  |
                            +---+                  |
               .-----------'     `-----------.     |
            +---+                           +---+  |
            | 2 |                           | 3 |  | 非满二叉树
            +---+                           +---+  |
       .---'     `---.                 .---'       |
    +---+           +---+           +---+          |
    | 4 |           | 5 |           | 6 |          |
    +---+           +---+           +---+         -'
   /     \         /     \         /     \
+---+   +---+   +---+   +---+   +---+   +---+
| 8 |   | 9 |   | A |   | B |   | C |   | D |
+---+   +---+   +---+   +---+   +---+   +---+

:

                            +---+
                            | 1 |
                            +---+
               .-----------'     `-----------.
            +---+                           +---+
            | 2 |                           | 3 |
            +---+                           +---+
       .---'     `---.                 .---'     `---.
    +---+           +---+           +---+           +---+
    | 4 |           | 5 |           | 6 |           | 7 |
    +---+           +---+           +---+           +---+
   /     \         /     \         /               /
+---+   +---+   +---+   +---+   +---+           +---+    -.
| 8 |   | 9 |   | A |   | B |   | C |           | E |     | 缺少的节点不连续
+---+   +---+   +---+   +---+   +---+           +---+    -'

    完全二叉树的好处之一在于它是一棵天然平衡的树, 这样就不会出现由于不平衡导致二叉树退化成线性表的情况.

    如果完全二叉树上, 非叶节点元素的值小于或等于其子节点元素的值, 那么称它为最小堆 (minimum heap), 相反, 如果非叶节点元素的值大于或等于其子节点元素的值, 那么称这棵完全二叉树为最大堆 (maximum heap). 在计算机科学领域, 动态分配的内存所在的内存区域也被称之为堆 (heap), 然而这两个是完全不同的概念. 这里要讨论的堆是数据结构, 跟内存分配没有关系. 下面是一个整数最小堆的示例

                           +---+
                           | 2 |
                           +---+
               .----------'     `----------.
            +---+                         +----+
            | 4 |                         | 12 |
            +---+                         +----+
       .---'     `---.                   /      \
    +---+           +---+            +----+    +----+
    | 5 |           | 5 |            | 13 |    | 11 |
    +---+           +---+            +----+    +----+
   /     \         /     \          /
+---+   +---+   +---+   +---+   +----+
| 8 |   | 7 |   | 7 |   | 6 |   | 14 |
+---+   +---+   +---+   +---+   +----+

    回到文章最开始的需求之一, 向集合内添加元素. 新入堆的元素首先必须保证让堆仍然是一棵完全二叉树, 如插入 9 到上面的树中, 那么新入节点应该是完全二叉树下一个较大编号的节点

                           +---+
                           | 2 |
                           +---+
               .----------'     `----------.
            +---+                         +----+
            | 4 |                         | 12 |
            +---+                         +----+
       .---'     `---.                   /      \
    +---+           +---+            +----+    +----+
    | 5 |           | 5 |            | 13 |    | 11 |
    +---+           +---+            +----+    +----+
   /     \         /     \          /      \
+---+   +---+   +---+   +---+   +----+    =====
| 8 |   | 7 |   | 7 |   | 6 |   | 14 |    [ 9 ]
+---+   +---+   +---+   +---+   +----+    =====

    这是非常容易做到的. 但是这样做会破坏堆的性质. 不过好在这种破坏是局部的, 所以进行修正只需要少量的工作. 首先, 9 比其父节点小, 那么交换它和其父节点的值 13

                           +---+
                           | 2 |
                           +---+
               .----------'     `---------.
            +---+                        +----+
            | 4 |                        | 12 |
            +---+                        +----+
       .---'     `---.                  /      \
    +---+           +---+            =====    +----+
    | 5 |           | 5 |            [ 9 ]    | 11 |
    +---+           +---+            =====    +----+
   /     \         /     \          /     \
+---+   +---+   +---+   +---+   +----+   +----+
| 8 |   | 7 |   | 7 |   | 6 |   | 14 |   | 13 |
+---+   +---+   +---+   +---+   +----+   +----+

    这时, 9 仍然比其父节点小, 再来交换 9 和其父节点 12

                           +---+
                           | 2 |
                           +---+
               .----------'     `----------.
            +---+                         +---+
            | 4 |                         | 9 |
            +---+                         +---+
       .---'     `---.                   /     \
    +---+           +---+            +----+   +----+
    | 5 |           | 5 |            | 12 |   | 11 |
    +---+           +---+            +----+   +----+
   /     \         /     \          /      \
+---+   +---+   +---+   +---+   +----+    +----+
| 8 |   | 7 |   | 7 |   | 6 |   | 14 |    | 13 |
+---+   +---+   +---+   +---+   +----+    +----+

    现在堆的规则重新满足, 无需进一步交换了. 每一次交换, 除了一直受到关注的 9, 其它节点交换是否一定合规则呢? 这其中有两种情况, 其一, 9 还是叶节点, 这时交换无须任何顾虑; 其二, 9 非叶节点, 由于这时它在与其父节点交换, 而父节点肯定不小于它的任何直接或间接子节点, 父节点与 9 交换之后进入一个较深的节点时, 肯定还能满足这一点. 所以每次交换都将是合法的.
    那么, 最小堆的插入 – 修正过程可以简述为

  • 将新节点插入完全二叉树中下一个子节点位置;
  • 如果新节点不是根节点, 且新节点的值小于其父节点的值, 则交换它们.

    而从堆中弹出最小值节点, 也就是根节点. 与插入类似, 要让根节点弹出后, 满足二叉树的性质, 便于以后修正堆的性质. 要做到这一点, 须将根节点与最后一个子节点交换, 再移除之, 就不会破坏完全二叉树结构了.

                           ======
                           [ 13 ] <-------------------.
                           ======                     |
               .----------'      `---------.          |
            +---+                         +---+       |
            | 4 |                         | 9 |       |
            +---+                         +---+       |
       .---'     `---.                   /     \      |
    +---+           +---+            +----+   +----+  |
    | 5 |           | 5 |            | 13 |   | 11 |  |
    +---+           +---+            +----+   +----+  |
   /     \         /     \          /                 |
+---+   +---+   +---+   +---+   +----+     - -        |
| 8 |   | 7 |   | 7 |   | 6 |   | 14 |    : 2 : <-----'
+---+   +---+   +---+   +---+   +----+     - -

    现在, 要将目前的根节点下降到一个合理的位置. 方法是, 每次让它与它子节点中较小的那个交换, 直到到达叶节点, 或一个合适的位置. 首先 13 跟左子节点 4 交换

                            +---+
                            | 4 |
                            +---+
                .----------'     `---------.
            ======                        +---+
            [ 13 ]                        | 9 |
            ======                        +---+
       .---'      `--.                   /     \
    +---+           +---+            +----+   +----+
    | 5 |           | 5 |            | 13 |   | 11 |
    +---+           +---+            +----+   +----+
   /     \         /     \          /
+---+   +---+   +---+   +---+   +----+
| 8 |   | 7 |   | 7 |   | 6 |   | 14 |
+---+   +---+   +---+   +---+   +----+

    现在两个子节点值相同, 就换到左边吧

                           +---+
                           | 4 |
                           +---+
               .----------'     `-----------.
            +---+                          +---+
            | 5 |                          | 9 |
            +---+                          +---+
        .--'     `----.                   /     \
    ======           +---+            +----+   +----+
    [ 13 ]           | 5 |            | 13 |   | 11 |
    ======           +---+            +----+   +----+
   /      \         /     \          /
+---+    +---+   +---+   +---+   +----+
| 8 |    | 7 |   | 7 |   | 6 |   | 14 |
+---+    +---+   +---+   +---+   +----+

    最后再跟较小的 7 交换, 于是完全二叉树变回了一个堆

                            +---+
                            | 4 |
                            +---+
               .-----------'     `----------.
            +---+                          +---+
            | 5 |                          | 9 |
            +---+                          +---+
       .---'     `----.                   /     \
    +---+            +---+            +----+   +----+
    | 7 |            | 5 |            | 13 |   | 11 |
    +---+            +---+            +----+   +----+
   /     \          /     \          /      \
+---+   +----+   +---+   +---+   +----+    +----+
| 8 |   | 13 |   | 7 |   | 6 |   | 14 |    | 13 |
+---+   +----+   +---+   +---+   +----+    +----+

    同样, 除了一直被聚焦的节点 13, 其它与之交换的节点在交换过程中能够一直保持堆的约束.
    堆的移除 – 修正过程简单来说就是

  • 用完全二叉树编号最大的节点替换根节点;
  • 让当前的根节点与其子节点中较小的进行交换, 直到完全二叉树成为堆.

    对于堆而言, 无论是弹出最小值还是添加新节点, 堆的操作时间消耗都大致与节点数目的对数成比例. 而每次取最小值重新扫一次集合这种充满暴力美学的方法, 虽然在连续弹出最小值时开销较大, 但在加入新元素是能极快完成. 可见堆并不是一种完美的替代品, 它只是另一种应该被考虑的方案.

相关 [日常 数据结构 最值] 推荐：

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

- Linker Lin - Bit Focus
    如果设计一个顺序统计系统, 需要动态向集合内添加元素, 又可以随时从集合中取得并丢弃最小值. 由于集合中有集合会被移除, 因此接下来再次取最小值时如果重新扫一次集合, 时间开销会相当大. 在一般情形中, 若为了均衡时间开销, 需要考虑维护一个更复杂的数据结构..     这个数据结构建立在满二叉树 (full binary tree)和完全二叉树 (complete binary tree)的概念上..

数据结构之BloomFilter

- - 编程语言 - ITeye博客
BloomFilter是什么.        BloomFilter主要提供两种操作: add()和contains()，作用分别是将元素加入其中以及判断一个元素是否在其中，类似于Java中的Set接口，它内部采用的byte数组来节 省空间. 其独特之处在于contains()方法，当我们需要查询某个元素是否包含在BloomFilter中时，如果返回true，结果可能是不正确 的，也就是元素也有可能不在其中；但是如果返回的是false，那么元素一定不在其中.

使用graphviz画数据结构

- 王者自由 - Emacs中文网
今天下午用了些时间写了个小的函数，该函数配合 autoinsert + graphviz-dot-mode ，可以很方便的将 C 语言中指定的 struct 结构画出来. 这样，画了多个数据结构之后，再手动添加几条线， 数据结构之间的关系就一目了然了. 1.2 Graphviz 的安装. 1.3 Graphviz 的使用.

数据结构之红黑树

- Shengbin - 董的博客
红黑树是一种自平衡二叉查找树. 它的统计性能要好于平衡二叉树（AVL树），因此，红黑树在很多地方都有应用. 在C++ STL中，很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持).

数据结构-二分法查找

- - 操作系统 - ITeye博客
1、二分查找(Binary Search).     　二分查找又称折半查找，它是一种效率较高的查找方法.     　二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构. 2、二分查找的基本思想.     　二分查找的基本思想是：（设R[low..high]是当前的查找区间）.

redis数据结构缓存运用

- - 企业架构 - ITeye博客
之前redis已经描述了redis 的基本作用与用处， 这一篇主要讲述redis运用场景以及分片,和spring整合. redis 存储数据结构大致5种，String 普通键值对，用的比较多. HASH针对 key 唯一标识 hashmap 键值对运用也比较多 list set 当然是集合运用 sortedSet 排序集合使用.

可视化的数据结构和算法

- greenar - 酷壳 - CoolShell.cn
还记得之前发布过的那个关于可视化排序的文章吗. 在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页，网址在这里，大家可以看看. 我把这个页面的目录列在下面并翻译了一下，大家可以直接点击了. 不知道国内的教育有没有相关的教学课件，至少在我大学的时候是没有的. Queues队列: 数组实现.

为什么要学习算法和数据结构

- snowflip - TopLanguage Google Group

MySQL索引背后的数据结构及算法原理

- Mike - 博客园-EricZhang&#39;s Technology Blog
在编程领域有一句人尽皆知的法则“程序 = 数据结构 + 算法”，我个人是不太赞同这句话（因为我觉得程序不仅仅是数据结构加算法），但是在日常的学习和工作中我确认深深感受到数据结构和算法的重要性，很多东西，如果你愿意稍稍往深处挖一点，那么扑面而来的一定是各种数据结构和算法知识. 例如几乎每个程序员都要打交道的数据库，如果仅仅是用来存个数据、建建表、建建索引、做做增删改查，那么也许觉得数据结构和这东西没什么关系.