《堆最大堆最小堆堆排序优先队列课件.ppt》由会员分享，可在线阅读，更多相关《堆最大堆最小堆堆排序优先队列课件.ppt（42页珍藏版）》请在三一办公上搜索。
1、堆,堆能干什么,堆排序优先级队列,堆是什么,完全二叉树!,关于二叉树,节点数 n高度 logn父节点 i左子节点 2*i 右子节点2*i+1,堆支持的操作,插入删除排序,关键是怎样维护,保持堆的性质父节点=子节点,基本维护操作,MAX-HEAPIFY(i)维护函数，接受一个父节点i将父节点，子节点中的最大值与父节点交换向下递归,将一个无序数组变为一个最大堆,For(i=n/2;i=1;i-)MAX_HEAPIFY(i),最大堆完成时间复杂度O(n),排序,很简单带有优先队列的选择排序,方法,建立一个最大堆将最大的元素与最后一个元素交换维护堆顶,.,排序的时间效率,运行n次每次维护lognO(n
2、logn),优先级队列,插入,将新元素插入最后如果父节点小于该元素,交换重复,插入,O(logn),另一种建堆方法,从空堆开始每次将新元素插入,删除,将堆顶元素取出将末尾元素移至堆顶对堆顶维护,删除,O(logn),还有更高端的,二项堆斐波那契堆详见算导,还有.,STL!,关于堆的题目,Whos in the Middle,水题据说连冒泡都能过.仅当练习堆排序,The kth great number,优先队列的应用,Argus,优先队列的应用,Fence Repair,优先队列的应用注意！long long,Black Box,多种做法线段树，红黑树，SBT推荐优先队列,Sliding Window,多种做法线段树推荐优先队列,谢谢你的阅读,知识就是财富丰富你的人生,
