19、数据结构与算法 - 基础：优先级队列

摘要

队列的数据结构保证先进先出特性，优先级队列打破先进先出特性，制定优先级高的先出队规则。依然使用数组的数据结构，并且也要优化遍历和插入操作，就需要满足这两个添加的大顶堆来支持。所以优先级队列基于大顶堆实现是最优的选择。

队列是符合先进先出的特性，即先入队的元素先出队。那么把入队的元素设置优先级，在队列中按照优先级由高到低排序，就可以实现优先级高的先出队，这样的队列就是优先级队列。

队列是线性的数据结构，若入队一个有优先级的元素，就需要遍历队列中的元素，找到元素的合适位置。传统的做法可以每入队一个元素就要遍历整个队列，然后插入元素，遍历或者插入的时间复杂度是无法被忽略的。

现在要使用大顶堆的数据结构实现，来减少遍历或者插入的次数，达到优化优先级队列的目的（大顶堆可以查看上期内容）。为什么呢？

因为大顶堆的遍历类似二叉树，只会发生在节点和子节点之间。插入操作也是发生在节点与子节点之间的交换，并在最后空的位置放入元素，也就是二叉树的路径长度就是遍历或者插入操作的次数，这比线性结构（比如数组）的遍历和插入次数要少很多。

大顶堆的添加元素

先来梳理一下大顶堆添加元素和删除元素的代码逻辑，这部分的代码与上期介绍大顶堆的文章关联性比较大，建议不太熟悉大顶堆时，先看一下上期的文章。

先上大顶堆添加元素的代码：

public void add(E element) {
   
     
  elementNotNullCheck(element);
  ensureCapacity(size++);
  elements[size -1] = element;
  siftUp(size-1);
}

在代码中，首先要判断添加的元素是不是 null ，即 elementNotNullCheck() 方法：

private void elementNotNullCheck(E element) {
   
     
  if (element == null) {
   
     
    throw new IndexOutOfBoundsException("element is not null");
  }
}

然后判断数组的容量是否够用，若不够用扩容数组，即 ensureCapacity() 方法，大致的逻辑如下：

1、 判断将要插入元素后的size是否大于原来的数组容量，若大于就往下走第2步；
2、 将数组的容量扩容为原来容量的1.5倍，即创建一个容量为原来1.5倍的新数组；
3、 将原来数组中的元素依次添加到新的数组中，完成；

具体的代码可以看之前介绍动态数组的那期，其中也有缩容的实现逻辑。

最后将元素放在数组的最后的位置（size-1)，并执行大顶堆的从 index 位置向上过滤方法（siftUp）将加入元素后的数组恢复成大顶堆性质。

大顶堆的删除元素

接下来是大顶堆删除元素的代码，实现的是删除堆顶元素并返回堆顶元素的逻辑：

public E remove() {
   
     
  emptyCheck();
  int lastIndex = -- size;
  E root = elements[0];
  elements[0] = elements[lastIndex];
  elements[lastIndex] = null;
  siftDown(0);
  return root;
}

emptyCheck 是检查数组是否为空的方法，如果为空，就无法再进行删除：

private void emptyCheck() {
   
     
  if (size == 0) {
   
     
    throw new IndexOutOfBoundsException("Heap is empty");
  }
}

删除元素的主要逻辑如下步骤，第 2 步是最核心的：

1、 先获取到堆顶元素，即索引为0元素，并size减1获取到最后元素的索引；
2、 最后索引的元素赋值到索引为0的元素，之后将最后索引位置赋值为null（即为删除元素）；
3、 最后从堆顶开始（即索引为0的位置）向下过滤（siftDown），恢复大顶堆结构；

优先级队列的主要方法

最后在大顶堆的基础上，实现优先级队列的几个主要方法就很简单了：

// 入队
public void enQueue(E element) {
   
     
  heap.add(element);
}

// 出队
public E deQueue() {
   
     
  return heap.remove();
}

// 获取队头元素，即数组中索引为 0 位置元素
public E front() {
   
     
  return heap.get();
}

总结：

• 优先级队列用大顶堆实现可以减少遍历和插入的时间复杂度，提高效率；
• 大顶堆的添加和删除元素方法及逻辑；
• 优先级队列基于大顶堆实现入队、出队等方法。