数据结构——堆与优先队列

《数据结构——堆与优先队列》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、5二叉树15.1二叉树的概念5.2二叉树的周游5.3二叉树的存储结构5.4二叉搜索树5.5堆与优先队列5.6Huffman树及其应用5.7二叉树知识点总结主要内容2复习完全二叉树3堆定义最大树（最小树）:每个结点的值都大于（小于）或等于其子结点（如果有的话）值的树。最大堆（最小堆）：最大（最小）的完全二叉树。45堆定义141210876965302527108461020501121最大树最小树5堆的操作插入初始化删除67最大堆的插入12015141021201514102178最大堆的插入22015141

2、0252015141022225201514105289最大堆的插入320151410221201514102222211514102022020202121151410202910最大堆的初始化建立n个元素的堆：通过在初始化为空的堆中执行n次插入操作来构建堆.O(nlogn);利用不同的策率在θ(n)时间内完成。1011最大堆的初始化根据inta[10]={20,12,35,15,10,80,30,17,2,1}建立最大堆20123515108030172101234567891112最大堆的初始化ste

3、p1已知n=10;i=(n-1)/2=4;2012351510803017210123456789i20123515108030172101234567891213最大堆的初始化step2i=320123515108030172101234567892012351510803017210123456789i2i+12i+21314最大堆的初始化step3i=220123517108030152101234567892012351710803015210123456789i2i+12i+21415最大堆的初始

4、化step4_0i=120128017103530152101234567892012801710353015210123456789i2i+12i+21516最大堆的初始化step4_1i=1,j=2i+1=320178012103530152101234567892017801210353015210123456789j2j+12j+21617最大堆的初始化step5_0i=020178015103530122101234567892017801510353012210123456789i2i+12i+

5、21718最大堆的初始化step5_1i=0,j=2i+2=280172015103530122101234567898017201510353012210123456789j2j+12j+21819最大堆的初始化step5_2801735151020301221012345678980173515102030122101234567891920最大堆的删除121151410202最大堆的删除：删除堆的根部元素删除21,得到的堆结构：1514102022151410202015141022021最大堆的删除

6、2最大堆的删除：删除堆的根部元素删除20,得到的堆结构：151421010151422015141021514210151410221例，序列49386597761327501.按顺序依次构造成完全二叉树的结点；49386597761327502.把完全二叉树改造成堆；从下向上，父子交换；50971365134949273.取得最小值134.删除13，重新改造成新堆；1397279797495.取得次小值27；6.删除27，重新改造成新堆；9727973897507.取得次次小值38；堆排序22课堂练习关键

7、码序列K={12，14，15，19，20，17，18，24，22，26}所对应的最小堆23建堆效率对于n个结点的堆，其对应的完全二叉树的层数为logn。设i表示二叉树的层编号，则第i层上的结点数最多为2i(i≥0)。建堆的过程中，对每一个非叶子结点都调用了一次SiftDown调整算法，而每个数据元素最多向下调整到最底层，即第i层上的结点向下调整到最底层的调整次数为logn–i。因此，建堆的计算时间为（公式5.3）令j=logn–i，代入5.3式得（公式5.4）24建堆效率建堆算法的时间复杂度是O(n)。这就

8、说明可以在线性时间内把一个无序的序列转化成堆序由于堆有logn层深，插入结点、删除普通元素和删除最小元素的平均时间代价和最差时间代价都是(logn)最小堆只适合于查找最小值，查找任意值的效率不高255.5.2优先队列优先队列(priorityqueue)是一种有用的数据结构。它是0个或多个元素的集合，每个元素都有一个关键码值，执行的操作有查找、插入和删除一个元素。优先队列的主要特点是支持从一个集合中快速地查找并