2.4.17

问题：

2.4.17 Prove that building a minimum-oriented priority queue of size k then doing N - k replace the minimum (insert followed by remove the minimum) operations leaves the k largest of the N items in the priority queue.

分析：

题意是insert followed by remove the minimum，先插入后删除。

例如

N=10, 元素为：0,2,4,6,8,1,3,5,7,9

k=3， qp = 0 2 4
N-k = 10 - 3 = 7，将要进行7次操作

pq = 0 2 4

count = 1
insert 6, pq = 0 2 4 6
remove 0, pq = 2 4 6

count = 2
insert 8, pq = 2 4 6 8
remove 2, pq = 4 6 8

count =3
insert 1, pq = 1 4 6 8
remove 1, pq = 4 6 8

...

count = 7
insert 9, pq = 6 7 8 9
remove 6, pq = 7 8 9

最大的3个元素被保留了下来。

从上面的规律可以看出，若本次插入的元素在pq中为最小的元素，那么将会在remove时被删除。

若本次插入的元素>=当前pq中最小的元素，则插入的元素会被保留下来。

如此往复，最终pq中保留了N个元素中前k个最大的元素。

参考：

沈星繁-2.4.17