漫画：什么是优先队列？

漫画：什么是优先队列？-吴师兄学编程

在之前的五分钟学算法漫画中，我们介绍了二叉堆和堆排序。没看过的小伙伴可以看一看前文：

五分钟学算法漫画：什么是二叉堆？（修正版）

五分钟学算法漫画：什么是堆排序？

这一次，我们来讲一讲二叉堆的另外一个应用：优先队列

队列的特点是什么？

聪明的小伙伴们都知道，是先进先出（FIFO）。

入队列：

出队列：

那么，优先队列又是什么样子呢？

优先队列不再遵循先入先出的原则，而是分为两种情况：

最大优先队列，无论入队顺序，当前最大的元素优先出队。

最小优先队列，无论入队顺序，当前最小的元素优先出队。

比如有一个最大优先队列，它的最大元素是8，那么虽然元素8并不是队首元素，但出队的时候仍然让元素8首先出队：

要满足以上需求，利用线性数据结构并非不能实现，但是时间复杂度较高，最坏时间复杂度O（n），并不是最理想的方式。

至于为什么最坏时间复杂度是O（n），大家可以思考下。

让我们回顾一下二叉堆的特性：

1.最大堆的堆顶是整个堆中的最大元素

2.最小堆的堆顶是整个堆中的最小元素

因此，我们可以用最大堆来实现最大优先队列，每一次入队操作就是堆的插入操作，每一次出队操作就是删除堆顶节点。

入队操作：

1.插入新节点5

2.新节点5上浮到合适位置。

出队操作：

1.把原堆顶节点10“出队”

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

3.节点1下沉，节点9成为新堆顶

public class PriorityQueue {

1. private int[] array;

2. private int size;


3. public PriorityQueue(){

4.    //队列初始长度32

5.    array = new int[32];

6. }


7. /**

8. * 入队

9. * @param key  入队元素

10. */

11. private void enQueue(int key) {

12.    //队列长度超出范围，扩容

13.    if(size >= array.length){

14.        resize();

15.    }

16.    array[size++] = key;

17.    upAdjust();

18. }


19. /**

20. * 出队

21. */

22. private int deQueue() throws Exception {

23.    if(size <= 0){

24.        throw new Exception("the queue is empty !");

25.    }

26.    //获取堆顶元素

27.    int head = array[0];

28.    //最后一个元素移动到堆顶

29.    array[0] = array[--size];

30.    downAdjust();

31.    return head;

32. }


33. /**

34. * 上浮调整

35. */

36. private void upAdjust() {

37.    int childIndex = size-1;

38.    int parentIndex = childIndex/2;

39.    // temp保存插入的叶子节点值，用于最后的赋值

40.    int temp = array[childIndex];

41.    while (childIndex > 0 && temp > array[parentIndex])

42.    {

43.        //无需真正交换，单向赋值即可

44.        array[childIndex] = array[parentIndex];

45.        childIndex = parentIndex;

46.        parentIndex = parentIndex / 2;

47.    }

48.    array[childIndex] = temp;

49. }


50. /**

51. * 下沉调整

52. */

53. private void downAdjust() {

54.    // temp保存父节点值，用于最后的赋值

55.    int parentIndex = 0;

56.    int temp = array[parentIndex];

57.    int childIndex = 1;

58.    while (childIndex < size) {

59.        // 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子

60.        if (childIndex + 1 < size && array[childIndex + 1] > array[childIndex]) {

61.            childIndex++;

62.        }

63.        // 如果父节点大于任何一个孩子的值，直接跳出

64.        if (temp >= array[childIndex])

65.            break;

66.        //无需真正交换，单向赋值即可

67.        array[parentIndex] = array[childIndex];

68.        parentIndex = childIndex;

69.        childIndex = 2 * childIndex + 1;

70.    }

71.    array[parentIndex] = temp;

72. }


73. /**

74. * 下沉调整

75. */

76. private void resize() {

77.    //队列容量翻倍

78.    int newSize = this.size * 2;

79.    this.array = Arrays.copyOf(this.array, newSize);

80. }


81. public static void main(String[] args) throws Exception {

82.    PriorityQueue priorityQueue = new PriorityQueue();

83.    priorityQueue.enQueue(3);

84.    priorityQueue.enQueue(5);

85.    priorityQueue.enQueue(10);

86.    priorityQueue.enQueue(2);

87.    priorityQueue.enQueue(7);

88.    System.out.println("出队元素：" + priorityQueue.deQueue());

89.    System.out.println("出队元素：" + priorityQueue.deQueue());

90. }

代码中采用数组来存储二叉堆的元素，因此当元素超过数组范围的时候，需要进行resize来扩大数组长度。

—————END—————

喜欢本文的朋友们，欢迎长按下图关注订阅号程序员小灰，收看更多精彩内容

原文始发于微信公众号（程序员小灰）：五分钟学算法漫画：什么是优先队列？