算法导论Let5-HeapS.ppt

该【算法导论Let5-HeapS 】是由【54156456】上传分享，文档一共【23】页，该文档可以免费在线阅读，需要了解更多关于【算法导论Let5-HeapS 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。算法导论Let5-HeapsCATALOGUE目录Heaps简介Heaps的实现Heaps的操作Heaps的应用Heaps的优化Heaps简介01堆是一种特殊的完全二叉树,用于实现优先队列。堆的根节点是键值最小的节点,称为最小堆。堆中的每个节点都有一个与之关联的值,称为键。堆的根节点是键值最大的节点,称为最大堆。什么是Heap堆是完全二叉树,即除了最后一层外,其他层的节点数都达到最大,且最后一层的节点尽可能靠左填充。堆中不存在环路,即从任意节点出发,沿着指向其子节点的边,无法回到起始节点。堆中的每个节点的键值都不大于(或不大于)其子节点的键值,即最小堆中每个节点的键值都不大于其子节点的键值,最大堆中每个节点的键值都不小于其子节点的键值。Heap的基本性质Heap的分类01根据堆中节点的键值是否可以改变,可以将堆分为静态堆和动态堆。02根据堆中根节点的键值最小还是最大,可以将堆分为最小堆和最大堆。根据堆中节点值的排序方式,可以将堆分为升序堆和降序堆。03Heaps的实现0203删除操作删除根节点时,先将其与最后一个节点交换,然后自上而下调整堆,确保堆的性质得到维护。01数组实现使用数组来存储堆的元素,通过父节点和子节点的相对位置关系来维护堆的性质。02插入操作插入新元素时,先将其存储在数组末尾,然后自下而上调整堆,确保堆的性质得到维护。数组实现链表实现使用链表来存储堆的元素,通过节点之间的关系来维护堆的性质。插入操作插入新节点时,先将其添加到链表末尾,然后自下而上调整堆,确保堆的性质得到维护。删除操作删除根节点时,先将其与链表末尾节点交换,然后自上而下调整堆,确保堆的性质得到维护。链表实现优先队列与Heap优先队列优先队列是一种数据结构,其中每个元素都有一个优先级,优先级最高的元素最先出队。Heap作为优先队列由于堆具有根节点最大(或最小)的性质,因此可以用作优先队列。根节点具有最高(或最低)优先级。插入操作插入新元素时,先将其存储在数组末尾(或链表末尾),然后自下而上调整堆,确保堆的性质得到维护。删除操作删除根节点时,先将其与最后一个节点交换(或与链表末尾节点交换),然后自上而下调整堆,确保堆的性质得到维护。