天天看点

算法:堆(Heap)

背景

Heap 可以用来实现优先级队列,也可以用来做堆排序,本文简单的做个介绍。

Heap

是一个完全二叉树,隐含的意思是:他是平衡的、使用数组进行存储也是连续的。

给定的任意节点,该节点小于等于其父亲节点,大于他们的孩子节点。

对于一个完全二叉树,如果将其存储到数组中,给定父节点的索引为:x,则:

left child's index is:2*x + 1。

right child's index is:2*x + 2。

root's index is:0.

说明:上面的公式很容易自己推到出来,有兴趣的朋友可以推到一下,这样就不用记住这个特性了。

图示

算法:堆(Heap)

存储到数组的顺序为:先存储第一层,然后是第二层,直到第 N 层。

添加和删除后还必须保证 Heap 满足规则。

添加前

算法:堆(Heap)

添加 6

算法:堆(Heap)

先将 6 添加到完全树的下一个节点,然后沿着祖先路径,将其插入到合适的节点(不一定是根节点)。

代码

结果

接着上面的例子执行删除

先将删除根节点(6),再将完全树最后的节点(2)直接移动到根节点。 

算法:堆(Heap)

接着将 2 向下插入到合适的节点,比如:5 > 4 && 5 > 2,因此结果是:

算法:堆(Heap)

备注

下篇简单的介绍一下堆排序。

继续阅读