InTheBloodHorse

数据结构与算法(4) 堆(优先队列)

字数统计: 274阅读时长: 1 min
2018/09/20 Share

今天看到堆(Heap)这个概念,可以用来实现优先队列。之前写过一篇关于二叉堆的)数据结构与算法(1)-二叉堆
那个二叉堆已经写的很详细了。
对于优先队列的删除,插入操作都是O(logN)的复杂度
向堆中插入数据,首先将数据项存放到叶节点中(即存到数组的最后一项),然后从该节点开始,逐级向上调整,直到满足堆中节点关键字的条件为止。

从堆中删除数据与插入不同,删除时永远删除根节点的数据,因为根节点的数据最大,删除完后,将最后一个叶节点移到根的位置,然后从根开始,逐级向下调整,直到满足堆中节点关键字的条件为止。
关于代码实现的话,在二叉堆里面已经实现了,只是删除的优先队列肯定是删除最大或者最小的节点,所以传入index=0就行,这个问题不大。

CATALOG