高级数据结构 堆集及二进制堆

1、 7 堆集及二进制堆堆集及二进制堆 7 7 堆集及二进制堆堆集及二进制堆 高级算法与数据结构高级算法与数据结构 7 堆集及二进制堆堆集及二进制堆 堆集堆集 1 1 堆及堆排序堆及堆排序 2 2 二进制堆二进制堆 3 3 优先队列优先队列 7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 堆的定义 定义：定义：n n个元素称为堆，当且仅当它的关键个元素称为堆，当且仅当它的关键字序列字序列 满足：满足： 或者满足：或者满足： 称为最小堆或最大堆。称为最小堆或最大堆。nkkk,212/1122nikkkkiiii2/1122nikkkkiiii7 堆集及二进制堆堆集及二进制堆 7

2、堆集及二进制堆堆集及二进制堆 堆的性质 堆堆可看成是一棵完全二叉树。如果树的高可看成是一棵完全二叉树。如果树的高度为度为d d： 1 1所有的叶结点不是处于第所有的叶结点不是处于第d d层，就是处于层，就是处于第第d-1d-1层；层；2 2当当d d1 1时，第时，第d-1d-1层上有层上有2 2d-1d-1个结点；个结点；3 3第第d-1d-1层上如果有分支结点，则这些分支层上如果有分支结点，则这些分支结点都集中在树的最左边；结点都集中在树的最左边；4 4每个结点所存放元素的关键字，都大于或每个结点所存放元素的关键字，都大于或小于它子孙结点所存放元素的关键字。小于它子孙结点所存放元素的关键字

3、。7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 堆和堆集排序堆的概念7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 堆的建立7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 堆的建立7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 堆的建立7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 堆的排序7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 堆的排序7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 堆的排序7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆

4、集及二进制堆 堆的排序7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 堆的排序7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 堆的排序7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 堆的排序7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 堆存储结构用数组用数组H H存放具有存放具有n n个元素的堆个元素的堆。1 1根结点存放在根结点存放在H1H1；2 2假定结点假定结点x x存放在存放在HHi i ，如果它有左儿子，如果它有左儿子结点，则它的左儿子结点存放在结点，则它的左儿子结点存放在H2iH2i；如；如果它有右儿

5、子结点，则它的右儿子结点存果它有右儿子结点，则它的右儿子结点存放在放在H2i+1H2i+1；3 3非根结点非根结点HHi i 的父亲结点存放在的父亲结点存放在 。2/ iH7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 堆存储结构7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 堆排序算法一般来说，对于堆这样的数据结构，需要下一般来说，对于堆这样的数据结构，需要下面几种操作：面几种操作： void void sift_upsift_up(Type H (Type H ，intint i i) )； 把堆中的第把堆中的第i i个元素上移个元素上移 void

6、void sift_downsift_down(Type H (Type H ，intint n n，intint i i) )；第；第i i个元素下移个元素下移 void insert(Type H void insert(Type H ，intint &n &n，Type Type x)x)；元素；元素x x插入堆中插入堆中7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 堆排序算法 void delete(Type H void delete(Type H ，intint &n &n，intint i i) )； 删去第删去第i i个元素个元素 Type Type de

7、lete_maxdelete_max(Type H (Type H ，intint &n) &n)；从非空的最大堆中删除并回送关键字最大的从非空的最大堆中删除并回送关键字最大的元素元素 void void make_headmake_head(Type H (Type H ，intint n) n)；使数使数组组H H中的元素按堆的结构重新组织中的元素按堆的结构重新组织 堆排序算法堆排序算法7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 优先队列意义优先队列意义7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 优先队列定义优先队列定义7 堆集及二进制堆堆集

8、及二进制堆 7 堆集及二进制堆堆集及二进制堆 优先队列的运算优先队列的运算7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 优先队列与字典优先队列与字典7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 优先队列的实现优先队列的实现7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 优先队列的特征优先队列的特征7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 优先级树优先级树7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 优先级树实现优先队列优先级树实现优先队列7 堆集及二进制堆堆集及二进制堆 7 堆集及二

9、进制堆堆集及二进制堆 优先队列的堆实现优先队列的堆实现7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 二进制树二进制树B Bk kBk树性质（1）每一Bk树有2k个结点。（2）Bk树高为k。（3）深度为h的顶点数为C(k,h)(h=0,1k)。（4）树根的线度为k。7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 B Bk k树树7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 二进制堆二进制堆H Hk k在二进制树Bk上建立的数据结构Hk堆。7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 二进制堆二进制堆H Hk k 一个整数n可表示为二进制数： n=n020+n121+nk2k ni=0或1 i=1,2,k 一组n个关键字组成序列可以由一组Hk堆连接起来，称为二进制堆。 例如：n=13=（1 1 0 1）=23+22+207 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 例如：例如：1313个元素构成的二进制堆个元素构成的二进制堆7 堆集及二进制堆堆集及二进制堆 7 堆集及二进制堆堆集及二进制堆 二进制堆删除堆顶元素二进制堆删除堆顶元素7 堆集及二进制堆堆集及二进制堆