漫画:什么是优先队列?

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


五分钟学算法漫画:什么是二叉堆?(修正版)


五分钟学算法漫画:什么是堆排序?


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



五分钟学算法漫画:什么是优先队列?



五分钟学算法漫画:什么是优先队列?



队列的特点是什么?


聪明的小伙伴们都知道,是先进先出(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—————




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

五分钟学算法漫画:什么是优先队列?

原文始发于微信公众号(程序员小灰):五分钟学算法漫画:什么是优先队列?

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 漫画:什么是优先队列?

我还会在以下平台发布内容

GitHub 哔哩哔哩