优先队列（堆）

优先队列

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （largest-in，first-out）的行为特征。

在某些数据处理的例子中，总数据量太大，无法排序（甚至无法全部装进内存）。例如，需要从十亿个元素中选出最大的十个，你真的想把一个10亿规模的数组排序吗？但有了优先队列，你只用一个能存储十个元素的队列即可。具体做法是让元素一个个输入，只要优先队列的个数大于10，就不断删除最小元素，最后优先队列长度不大于10时停止删除，只剩10个自然就是所有元素中最大的10个了。很多情况我们会收集一些元素，处理当前键值最大（或最小）的元素，然后再收集更多的元素，再处理当前最大的（或最小的）元素，这可以看成我们按照事件的优先级顺序来处理，生活中很多任务都是有优先级高低之分的，所以优先队列可以高效地处理这些情况。

优先队列最重要的操作是删除最大元素和插入元素

优先队列不同数据结构实现的优先级

数据结构	插入元素	删除最大元素
有序数组	N	1
无序数组	1	N
堆	logN	logN
理想情况	1	1

堆

数据结构的二叉堆能很好的实现优先队列的基本操作。在二叉堆中，每个元素要保证大于等于另两个特定位置的元素。

堆（heap）也被称为优先队列（priority queue）。队列中允许的操作是先进先出（FIFO），在队尾插入元素，在队头取出元素。而堆也是一样，在堆底插入元素，在堆顶取出元素，但是堆中元素的排列不是按照到来的先后顺序，而是按照一定的优先顺序排列的。这个优先顺序可以是元素的大小或者其他规则。如图一所示就是一个堆，堆优先顺序就是大的元素排在前面，小的元素排在后面，这样得到的堆称为最大堆。最大堆中堆顶的元素是整个堆中最大的，并且每一个分支也可以看成一个最大堆。同样的，我们可以定义最小堆，如图二所示。

1350354702_4619.jpg

插入元素

向堆中插入一个新元素；在堆的最末尾插入新结点。然后自下而上调整子结点与父结点：比较当前结点与父结点，不满足堆性质则交换，使得当前子树满足二叉堆的性质。时间复杂度为 O(logn)。

插入元素1.png

删除最大元素

删除堆顶元素，再把堆存储的最后那个结点填在根结点处。再从上而下调整父结点与它的子结点。时间复杂度为 O(logn)。

删除元素1.png