Heaps and Priority Queues Study Guide

CS61B

Overview

C Level

根据定义，一个元素按降序排列的array完全可以被当做一个Max-oriented heap. 它实际上就是一个array representation of a binary tree，并且每个Node比它的子Node大。

3

参考答案：

更正：

4

B Level:

1

答案：

更正：

3.

这里用priority queue来写stack, 我们用的API是insert(int k, Item iten),意识是插入某个item的时候自动与一个整数k联系起来。首先我们初始化一个int c = 0, 然后每次insert, c都自减。这样新插入的item所匹配的int就越来越小，这个int就是这些item在这里的priority. 由于stack是filo, 它pop()是要remove最上面的item,也就是priority最小的item, 所以用一个Min Priority的removeSmallest()就可以完成pop（）.

Queue则相反，是FIFO，先进先出，那么每次insert后，c就要自加，最后用min priority来removeSmallest实现删除最早放进的item.

5.

实际上对任意N， 要removeMax， 至少都是需要2次exchange items.

至于2,3 sucessive removeMax, 目前觉得是 2*2， 2*3次，还没找到答案。

参考：
What is the minimum number of items that must be exchanged during a remove the maximum operation in a heap of size N with no duplicate keys?