Lecture 24: Priority Queues and Heaps

未分类

Priority Queue

要实现Priority Queue这个ADT考虑的数据结构：

BST是可能的，但是要维持Bushy很恼人，并且BST还不支持duplicate。

Heaps

Binary min heap:

• complete ：如果有空缺的Node，只能在最底部level, 所有的nodes都是竭尽可能地靠左；
• min heap : 每个Node都小于等于它的子Node.

Heap中如何Insert和delete:

Insert:

• 先暂时add这个item到Heap的尾部
• 再逐层向上移动到正确的地方

eg: insert 3.

delete min:

• 暂时将Heap里最后一个item换到root；
• 再沿着层级一层层下降到正确的地方

eg: delete min

动画demo

Tree Representations

参考书里的实施方式：