毕设论文 项二堆和fibonacci堆的分析与实现.doc

《毕设论文 项二堆和fibonacci堆的分析与实现.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、本科生毕业设计（论文）题目：二项堆和Fibonacci堆的分析与实现姓名：陈伟学号：110901004学院：数学与计算机科学学院专业：计算机科学与技术年级：2009级指导教师：（签名）年月日I二项堆和Fibonacci堆的分析与实现摘要堆是计算机科学中一类特殊的数据结构的统称。堆通常被视为部分有序的树形对象。堆总是满足堆中某个节点的值总是不大于或不小于其父节点的值这个特殊性质。通常将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆的实现包括二叉堆、二项堆，斐波那契堆。堆也是计算机程序

2、设计中经常用到的数据结构，在最短路算法的快速实现和最优编码的哈夫曼树实现中都需要用到堆.同时堆也经常作为优先级队列来使用，在程序调度算法中发挥重要作用。斐波那契堆有着非常好的均摊运行时间，可是其数据结构和算法实现相对比较复杂，因此人们一直在寻找一种既能实现较好的均摊运行时间，同时数据结构相对比较简洁的实现算法。本课题的目的是学习连续空间上二叉堆的性质特点和离散空间上二项堆以及斐波那契堆的性质特点同时实现二项堆和斐波那契堆的具体算法。通过具体代码实现来对比二项堆和斐波那契堆实现的时间空间上消耗，对比起各自的优劣，

3、同时探讨堆在具体应用中发挥的作用。关键字：二叉堆，二项堆，斐波纳契堆，实现算法。27PerformanceanalysisandImplementationforbinomialheapandfibonacciheapAbstractHeapisaspecialkindofdatastructureincomputerscience.Heapisoftenviewedaspartialorderedtreeobject.Heapisalwaysmeetaspecialqualitythatthevalueofa

4、nodeisalwaysgreaterthanorlessthanthevalueofitsparent.Usuallytheheapiscalledthemaximumheaporbigrootheapifthevalueofrootisthebiggest,theminimumheaporsmallrootheapifthevalueofrootisthesmallest.Theimplementationofheapincludingbinaryheap,binomialheapandfibonaccih

5、eap.Heapisakindofdatastructurewhichisoftenusedinthedesignofcomputerprogram,itisusedinthefastimplementationofshortestpathalgorithmandoptimalcodingalgorithmofhuffmantree.Simultaneously,heapisoftenusedasapriorityqueue,playinganimportantroleinprocessschedulingal

6、gorithm.Fibonacciheaphasaverygoodcapitationrunningtime,butitsdatastructureandalgorithmimplementationisrelativelycomplicated,sopeoplehavebeenlookingforakindofdatastructurewhichhasbothgoodcapitationrunningtimeandrelativelysimpleimplementationalgorithm.Thepurpo

7、seofthissubjectislearningthepropertyofthebinaryheaponcontinuousspace.Atthesametime,learningthepropertyandspecificimplementationalgorithmofbinomialheapandfibonacciheapondiscretespace.Throughspecificcode,wecomparethetimeconsumptionandspaceconsumptionbetweenbin

8、omialheapandfibonacciheap,andcontrasttheirrespectiveadvantagesanddisadvantages.Atthesametime,westudytheeffectofheapinpracticalapplication.Keywords:binaryheap,binomialheap,fibonacciheap,implement