二叉树（二）-二叉堆

2017-10-29 本文已影响0人 RavenX

1.什么是二叉堆

二叉堆是一种特殊的堆，二叉堆是完全二元树（二叉树）或者是近似完全二元树（二叉树）。二叉堆有两种：最大堆和最小堆。最大堆：父结点的键值总是大于或等于任何一个子节点的键值；最小堆：父结点的键值总是小于或等于任何一个子节点的键值。

上图说:

二叉堆

可以看出，这是一颗完全二叉树,同时这也是一个最大堆。
值得一提的是，完全二叉树具有以下性质，在之后的分析中会使用到:
假设节点编号从1开始,编程实现时，数组从0号开始，所以可采用占位符把0号位置占用，或者将后续所有节点全部减一。

结点i的父结点为结点i/2 （注意这里是地板除法，举个栗子，在C/JAVA...语言中直接另1/2等于0，而不是0.5。具体可以这样写floor(1/2)也就是将1/2的结果在向下取整。）
结点i的子结点分别为(2*i)和(2*i+1)

同时，基于完全二叉树的特性，二叉堆通常使用数组来编写。

2.二叉堆的基本操作

二叉堆的基本操作为插入，提取最大（最小）值。下面以最大堆作为例子来介绍，最小堆只是最大堆的镜像反转，所以我就不多说啦。

2.1插入

insert.gif

在上面的二叉堆中，我们插入了55这个节点。
我们来分析下，它是如何插入到这个二叉堆中的：

首先按照完全二叉树的顺序，我们在编号12这个地方生成55这个节点
接着，由于这是一个最大二叉堆，所以要比较它的父节点（如果有的话）和它的大小，这里55是大于7的，所以两个交换了位置
循环第2步，直到它的父亲节点不比它大，或者已经达到根节点。

从上面三步分析中，我们可以直到发生，一个插入的操作无非就是：插入到最后这个位置，向上更新两步。所以我们可以写出下面的代码:

void insert(int e) {
        ensureSize();            //保证空间还足够插入
        elem[length] = e;        //插入
        heapUp();                //向上更新
        length++;
    }

So,how to headUp()?

  void heapUp() {
        int i = length;
        while (hasParentIndex(i) && elem[parentIndex(i)] < elem[i]) {
            swap(elem[parentIndex(i)], elem[i]);
            i = parentIndex(i);
        }
    }

我相信已经足够简单了。一直向上检查是否有比自己小的元素，只要有，就交换。

知道怎么插入节点了，那么我们能够运用它来做什么呢？（废话，当然是插入操作了），其实最简单的我们可以用它来生成二叉堆。
为了加深印象，我再贴一张，生成二叉堆动态的图:

create.gif

生成二叉堆

就随机插入一些元素吧，randNumber是我写的随机函数，各位同学看自己熟悉的语言怎么实现方便就怎么实现吧。

    for (int i = 0; i < 10; i++) {
        heap.insert(randNumber(0, 1000));
    }

2.2 提取最大（最小）值

最大（最小）堆的根节点，代表了这个堆中的最大（最小）值，将它进行弹出，在把整棵树最后的节点放置到根节点，再把它交换到恰当的位置，这就是提取操作。

表达的不是很好，所以还是贴图吧

extract.gif

相信你已经能够理解什么是提取操作了。其实具体就分为三步：

Pop堆顶元素
把当前树（数组）中最后一个非空元素提取上来
heapDown，更新，只要遇到比自己大的元素就交换。

那么下面看代码:

 bool pop() {
        if (!isEmpty()) {
            elem[0] = elem[length - 1];
            length--;
            //swap down
            heapDown();
            return true;
        } else {
            return false;
        }
    }
  
   void heapDown() {
        int i = 0;
        while (hasLeftChild(i)) {
            //find the minimum index of this node's child
            int largerIndex = leftSonIndex(i);
            if (hasRightChild(i) && elem[rightSonIndex(i)] > elem[leftSonIndex(i)]) {
                largerIndex = rightSonIndex(i);
            }
            if (elem[i] > elem[largerIndex]) {
                break;
            }
            swap(elem[i], elem[largerIndex]);
            i = largerIndex;
        }
    }

heapDown操作比heapUp略微复杂一点，因为从上往下时有左子树和右子树，我们要检查哪个子树更大,总是把更大的哪个往上堆，至于为什么，因为越往下越小嘛。

那么提取操作能做什么呢？没错，就是今天的应用-堆排序

3.二叉堆应用-堆排序

所谓的堆排序，也就是利用了二叉堆本身性质，在循环调用提取操作的一种排序方式，其平均时间复杂度为O(nlogn)，是一种排序效率很高的排序方法。
还是老规矩，先上图：

heap_sort.gif

写个driver来测试一下：

int main(void) {
    Heap heap(1000);
    //初始化随机种子
    srand((unsigned int) time(NULL));
    for (int i = 0; i < 100000; i++) {
        heap.insert(randNumber(0, 1000000));
    }
    while (!heap.isEmpty()) {
        cout << heap.top() << " ";
        heap.pop();
    }
    return 0;
}

本文中所有的源码都可以在我的Github上找到：https://github.com/zzbb1199/DataStructure

除了本文，也推荐去看下这个视频（需要去外面看看才行哟）,10分钟搞定堆，虽然是全英文的，但是讲得简短而且很清晰，学习数据结构的同时也锻炼了自己的英语能力嘛:https://www.youtube.com/watch?v=t0Cq6tVNRBA&t=490s