1.优先队列的API和初等实现

做一个总结&＃xff1a;

栈 &＃xff1a;先进后出
队列 &＃xff1a;先进先出
随机队列 &＃xff1a; 随机出
优先队列&＃xff1a;每次出来的是最大值或最小值

1.1优先队列的API

优先队列在很多场合都有用&＃xff0c;
比如&＃xff1a;在大量数据里&＃xff0c;如果取前M大的数据(存储不足以存下如此大规模数据)&＃xff0c;就可以用优先队列&＃xff08;MinPQ来做&＃xff0c;类似MaxPQ&＃xff0c;只是每次删除最小值)——一直保证队列中只有M个比较大的数据&＃xff0c;每次删除超过M个里面的最小值。

1.2初等实现

如果用数组来做&＃xff0c;我们可以考虑用排序好的数组或没排序的数组。

它们的实现方案都比较简单&＃xff0c;但是都有致命的缺点&＃xff1a;

排序数组&＃xff0c;每次插入的时候需要N的时间复杂度
未排序的数组&＃xff1a;每次删除或查找的时候&＃xff0c;需要N的时间复杂度
我们的目标是找到一个插入和删除都logN复杂度的数据结构。——二叉堆