英国德比郡

普通队列是一种先进先出的数据结构，元素在队列尾插入，从队列头删除。（用栈-stack实现队列queue-LeetCode ）在优先队列中，元素具有了特殊属性，赋予了优先级。当删除队列中的元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （largest-in，first-out）的行为特征。

我们举一个数据处理的例子，被处理的总数据量太大，无法排序，可能无法全部装进内存。例如，我们要从十亿个元素中选出最大的十个，你是不可能把一个10亿规模的数组排序。但使用优先队列，你只用一个能存储十个元素的队列即可。具体做法是让元素一个个输入，只要优先队列的个数大于10，就不断删除最小元素，最后优先队列长度不大于10时停止删除，只剩10个自然就是所有元素中最大的10个了。

再举一个例子，例如，我们会收集一些元素，处理当前键值最大（或最小）的元素，然后再收集更多的元素，再处理当前最大的（或最小的）元素，这可以看成我们按照事件的优先级顺序来处理，生活中很多任务都是有优先级高低之分的，所以优先队列可以高效地处理这些情况。

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

数据结构的二叉堆（数据结构：二叉堆 ）能很好的实现优先队列的基本操作。在二叉堆中，每个元素要保证大于等于孩子节点位置的元素。优先队列（priority queue）可以用堆（heap）来实现。

队列中允许的操作是先进先出（FIFO），在队尾插入元素，在队头取出元素。

堆也是一样，在堆底插入元素，在堆顶取出元素，但是堆中元素的排列不是按照到来的先后顺序，而是按照一定的优先顺序排列的。

最大堆，堆优先顺序就是大的元素排在前面，小的元素排在后面；堆中堆顶的元素是整个堆中最大的，并且每一个分支也可以看成一个最大堆。同样的，最小堆也是一样的。

插入元素（enqueue）

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

我们图文并茂看一下优先队列的插入操作：

1.插入新节点5：

新插入节点5

2.新节点5向上调整（shiftUp）到合适的位置：

进行向上调整

删除最大元素（dequeue）

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

我们图文并茂看一下优先队列的删除操作：

1.让原堆顶出队列

堆顶出队列

2.把最后一个节点替换到堆顶位置

最后一个节点替换到堆顶

3.节点1进行向下调整（shiftDown），最大节点9成为新的堆顶

进行向下调整

class PriorityQueue:    def __init__(self):        self.array = []        self.size = 0    def enqueue(self, data):        self.array.append(data)        self.size += 1        self.up_adjust()    def dequeue(self):        if self.size < 0:            raise Exception("队列为空！")        ret = self.array[0]        self.array[0] = self.array[self.size - 1]        self.size -= 1        self.down_adjust()        return ret    def up_adjust(self):        child_index = self.size - 1        parent_index = (child_index - 1) // 2        temp = self.array[child_index]        while child_index > 0 and temp > self.array[parent_index]:            self.array[child_index] = self.array[parent_index]            child_index = parent_index            parent_index = (parent_index - 1) // 2        self.array[child_index] = temp    def down_adjust(self):        parent_index = 0        temp = self.array[parent_index]        child_index = 2 * parent_index + 1        while child_index < self.size:            if child_index + 1 < self.size and self.array[child_index + 1] > self.array[child_index]:                child_index += 1            if temp >= self.array[child_index]:                break            self.array[parent_index] = self.array[child_index]            parent_index = child_index            child_index = 2 * parent_index + 1        self.array[parent_index] = temp

往期精彩：

数据结构：二叉堆

数据结构：二叉堆的自我调整

队列解题-最近的请求次数LeetCode

数据结构-双端队列-deque-python3

用栈-stack实现队列queue-LeetCode

Cpython源码阅读18-从底层实现看列表与元组的区别