黑马程序员技术交流社区
标题:
探秘堆结构
[打印本页]
作者:
18895700133
时间:
2016-5-13 22:31
标题:
探秘堆结构
一、概述
此处所说的堆为数据结构中的堆，而非内存分区中的堆。堆通常可以被看做是树结构，满足两个性质：1）堆中任意节点的值总是不大于（不小于）其子节点的值；2）堆是一棵完全树。正是由于这样的性质，堆又被称为优先队列。根据性质一，将任意节点不大于其子节点的堆称为最小堆或最小优先队列，反之称为最大堆或最大优先队列。优先队列在操作系统作业调度的设计中有着举足轻重的作用。之前写了一篇优先队列的文章，详见算法导论第六章优先队列。
常见的堆结构，有二叉堆、左倾堆、斜堆、二项堆、斐波那契堆等。斐波那契堆在前文算法导论第十九章 斐波那契堆已经作了讲述。本文主要对其余几种堆结构做宏观上的概述，并说明它们的异同点。
二、二叉堆
二叉堆是最简单的堆结构，本质是一棵完全的二叉树，一般由数组实现，其父节点和左右子节点之间存在着这样的关系： 索引为i（i从0开始）的左孩子的索引是 (2*i+1); 右孩子的索引是 (2*i+2); 父结点的索引是 floor((i-1)/2)。详细请看我之前写的一篇文章：算法导论第六章堆排序（一）。众所周知，二叉堆在排序算法中应用甚广，特别是涉及到大数据的处理中，如Topk算法。
三、二项堆
某些应用中需要用到合并两个堆的操作，这个时候二叉堆的性能就不是很好，最坏情况下时间复杂度为O(n)。为了改善这种操作，算法研究者就提出了性能更好的可合并堆，如二项堆和斐波那契堆，当然还有左倾堆，斜堆等。二项堆对于该操作能在最坏情况Θ(lgn)下完成，而斐波那契堆则更进一步，能在平摊时间为Θ(1)下完成（注意是平摊时间），见下表。除了Union操作，二叉堆各操作的性能都挺好，而二项堆对此也仅仅是改善了Union操作，对于Minimum操作甚至还不如二叉堆，我想这大概是《算法导论》第三版没有把二项堆再作为一章的原因之一吧。而斐波那契堆各个操作都有极好的性能，除了Extract_min和Delete操作。
说回到二项堆，二项堆是由一组的二项树组成，二项树B_k是一种递归定义的有序树，其具有以下的性质：
1）共有2^k个节点；
2）树的高度为k；
3）在深度 i 处恰有C^i_k个节点，因为C^i_k为二项系数，正因如此，才称其为二项树；
4）根的度数为k（即孩子节点个数），它大于任何其他节点的度数。
二项树B_0只包含一个节点，二项树B_k由两棵二项树B_k-1连接而成，其中一棵树的根是另一棵树的根的最左孩子。如下图：
二项堆H由一组满足下面二项堆性质的二项树组成：
1）H中的每个二项树满足最小堆性质（说明二叉堆中最小节点在二项树的根中）；
2）对任意非负整数k，H中至多有一棵二项树的根具有度数k（说明在包含n个节点的二项堆中，至多有floor(lgn)+1棵二项树）。
不同于斐波那契堆采用双循环链表来连接根节点和孩子节点，二项堆中采用的是单链表，每个节点有指向父节点的指针，孩子节点指针和兄弟节点指针，如：
[url=]
[/url]
1
struct
BinomialHeapNode {
2
BinomialHeapNode *
parent;
3
BinomialHeapNode *
child;
4
BinomialHeapNode *
sibling;
5
6
unsigned
int
degree;
7
KeyType key;
8
};[url=]
[/url]
作者:
我有上将潘凤
时间:
2016-5-13 23:12
看不懂，先mark
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2
[/url][/url]