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();
}

总结:

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