Priority queue

wanweibaike Priority queue

In computer science, a priority queue is an abstract data type similar to a regular queue or stack data structure in which each element additionally has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. In some implementations, if two elements have the same priority, they are served according to the order in which they were enqueued, while in other implementations, ordering of elements with the same priority is undefined.

NOTE:

根据priority来进行排名，原文的下面这段话总结得非常到位:

One can imagine a priority queue as a modified queue, but when one would get the next element off the queue, the highest-priority element is retrieved first.

次序是由priority而决定的，而不是由位置决定的

Operations

A priority queue must at least support the following operations:

1、is_empty: check whether the queue has no elements.

2、insert_with_priority: add an element to the queue with an associated priority.

3、pull_highest_priority_element: remove the element from the queue that has the highest priority, and return it.

One can imagine a priority queue as a modified queue, but when one would get the next element off the queue, the highest-priority element is retrieved first.

NOTE:

这个比喻非常好

Implementation

Naive implementations

NOTE:

现实中，并没有人会使用这种方式

Usual implementation

1、heap

2、self-balancing binary search tree

Equivalence of priority queues and sorting algorithms

Using a priority queue to sort

Name	Priority Queue Implementation	Best	Average	Worst
Heapsort	Heap
Smoothsort	Leonardo Heap
Selection sort	Unordered Array
Insertion Sort	Ordered Array
Tree sort	self-balancing binary search tree

Applications

NOTE:

在非常多的algorithm中，都使用到了priority queue

1、leetcode 23. 合并K个升序链表

2、leetcode 215. 数组中的第K个最大元素

使用min heap，不断地弹出小元素，留下大元素

3、labuladong 啊这，一道找中位数的算法题把东哥整不会了…

leetcode 剑指 Offer 41. 数据流中的中位数

leetcode 295. 数据流的中位数

使用两个heap