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
网友评论