Java底层实现PriorityQueue 优先队列

Java底层实现PriorityQueue 优先队列

PriorityQueue 优先队列

基于MaxHeap最大堆

Github LiYangSir
Home https://quguai.cn
Language Java

1、什么是优先队列

  优先队列也是一种队列,它的接口函数和队列相同。

public interface Queue<E> {
    int getSize();
    boolean isEmpty();
    E dequeue();
    void enqueue(E e);
    E getFront();
}

  虽然代码相同,需要注意的是,出队操作:拿出最大值(优先级最高)。但相对于普通的队列有着宏观上的不同。

  • 普通队列:先进先出,后进后出
  • 优先队列:出队和入队得顺序无关,和优先级有关

  形象地理解就是超市和医院的排队。超市排队这种特性就符合普通队列的形式。先排队先结账。医院就不一样啦,医院要优先处理急诊的病人,这就跟优先级有关,优先级越高的元素放在最前面。优先进行处理。

不同的底层实现方法:

  作为一种抽象的数据结构,底层实现的方法包含很多。数组或者链表这种线性结构,当然还有我们的树结构,当然我们也可以引入顺序的线性结构。具体的复杂度如下:

入队出队
普通线性结构O(1)O(N):拿出最大元素
顺序线性结构O(N):顺序放入元素O(1)
二叉堆O(log(N))O(log(N))

2、二叉堆的实现

2.1 什么是二叉堆

  二叉堆是一个完全二叉树。那什么是完全二叉树呢?
  满二叉树就是除了最下面一层,其他的节点都是具有左右孩子节点,就类似于这样。

满二叉树

完全二叉树就类似这种:

完全二叉树

  完全二叉树不是一颗满的二叉树,但是它的不满的那一部分一定在他的右下角部分。存放的过程也就是从左向右的过程。

  堆的特性和二分搜索树不同,堆的某个节点总是不大于其父亲节点的值。也就是它并不具有顺序性。我们可以看一下下面这张图。

二叉堆结构

可以看出任意子树的最大值永远是自己的父亲节点。

2.2、二叉堆的结构

  这里我们可以看出来二叉堆是一层一层的从左到右这么依次排列的,所以这里我们使用数组进行存储二叉树。通过数组索引找到节点。

  这样我们就非常巧妙的将树结构存储到了数组当中。我们还可以发现下面的规则:

  • 左孩子的索引等于该父亲节点索引值的 2 倍 + 1
  • 有孩子的索引等于该父亲节点的索引值的 2 倍 + 2
  • 父亲节点的索引值等于左右孩子节点的(索引值 - 1) / 2

用代码展示就是:

parent(i) = (i - 1)/ 2;//获得i索引值的父亲节点索引值
leftChild(i) = i * 2 + 1
rightChild(i) = i * 2 + 2

2.3、初始化操作

  在最大堆这个数据结构当中我们使用的是数组的底层实现,当然我们也就需要动态数组来实现这个动态大小的最大堆。关于Array动态数组这一章可以参考Array 动态数组。当然也可以直接使用Java自带的动态数组。

初始化程序实现:

public MaxHeap() {
    data = new Array<>();
}
public MaxHeap(int capacity) {
    data = new Array<>(capacity);
}

节点索引查询实现:
我们需要对查询父亲节点进行判断,因为index-1操作会导致负值出现。

private int parent(int index) {
    if (index == 0)
        throw new IllegalArgumentException("index isn't zero");
    return (index - 1) / 2;
}

private int leftChild(int index) {
    return index * 2 + 1;
}

private int rightChild(int index) {
    return index * 2 + 2;
}

2.4、添加元素

  这里的操作底层实现其实是上浮(SiftUp)操作。下面我们就来看看是如何上浮的。

  • 向数组末尾添加一个元素,也就是向树的最下角添加一个元素;
  • 根据堆的性质,父亲节点大于它的左右孩子节点,来进行替换操作
  • 不断进行第二步操作直到待添加节点小于它的父亲节点
SiftUp操作

程序实现:

public void add(E e) {
    data.addLast(e);
    siftUp(data.getSize() - 1);
}

private void siftUp(int index) {
    while (index > 0 && data.get(parent(index)).compareTo(data.get(index)) < 0) {
        data.swap(parent(index), index);
        index = (index - 1) / 2; //父亲节点也就是待插入元素现在的位置
    }
}

2.5、提取最大值

  对于我们上面实现的最大堆,看得出来,最大值的地方存在于根节点的位置。也就是数组索引位0的位置。而且我们需要维护二叉堆的性质。
步骤:

  • 用树最后一个节点移动到根节点
  • 判断待下沉操作的节点必须大于孩子节点的最大值,如果大于那么循环结束,否则替换孩子节点最大值和待下沉节点的位置。
SiftDown操作

提取最大值程序实现:

public E extractMax() {
    E ret = findMax(); //查找最大值
    data.swap(0, size() - 1); //移动最后一个节点到根节点
    data.removeLast(); 
    siftDown(0);
    return ret;
}
// 下沉操作
private void siftDown(int index) {
    while (leftChild(index) < size()) {
        int j = leftChild(index);
        if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0)
            j++;  //右孩子节点值大
        if (data.get(index).compareTo(data.get(j)) >= 0)
            break;
        else
            data.swap(index, j);
        index = j;
    }
}

2.6、查询操作

  查询操作就是查找元素最大的值,这里就是根节点位置,也就是索引为 0 的位置。
程序实现:

public E findMax() {
    if (isEmpty())
        throw new IllegalArgumentException("Empty");
    return data.get(0);
}

2.7、replace操作

  replace替换操作主要包括:去除最大元素,放入一个新的元素。这其实是一个组合操作。但这里我们准备封装一下,并对其进行优化。

  优化的方式就是在删除元素这里,如果我们分extraMax和add操作就需要两次 O(log(N)) 级别的时间复杂度。在replace操作中,我们可以直接将待添加的元素元素替换到根节点的位置,然后在执行下沉操作就可以,这样就是一次 O(log(N)) 级别的时间复杂度。

程序实现:

public E replace(E e) {
    E ret = findMax();
    data.set(0, e);
    siftDown(0);
    return ret;
}

2.8、Heapify数组堆化

  操作就是将任意数组整理成堆的形状。
具体的过程就是:

  • 找到树结构的倒数第一个非叶子节点;
  • 不断向上进行下沉SiftDown操作
Heapify数组堆化

初始位置的查询就是最后一个节点的父亲节点。

程序实现:

public MaxHeap(E[] arr) {
    data = new Array<>(arr);
    for (int i = parent(arr.length - 1); i >= 0; i--)
        siftDown(i);
}

3、优先队列的实现——基于最大堆

  具体的函数方法其实在最大堆已经映射过了。
||优先队列|最大堆|
|:---:|:---:|:---:|
|入队操作|enqueue|add|
|出队操作|dequeue|extraMax|
|查询栈顶元素|getFront|findMax|

@Override
public E dequeue() {
    return maxHeap.extractMax();
}

@Override
public void enqueue(E e) {
    maxHeap.add(e);
}

@Override
public E getFront() {
    return maxHeap.findMax();
}

最后

更多精彩内容,大家可以转到我的主页:曲怪曲怪的主页

或者关注我的微信公众号:TeaUrn

或者扫描下方二维码进行关注。里面有惊喜等你哦。

源码地址:可在公众号内回复 数据结构与算法源码 即可获得。

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://quguai.cn/archives/j-a-v-a-di-ceng-shi-xian-p-r-i-o-r-i-t-y-q-u-e-u-e--you-xian-dui-lie