快速了解：PriorityQueue - 优先级队列（堆）的实际操作与应用

最编程 2024-02-21 09:03:21

...

1.优先级队列的模拟实现

1.1 优先级队列及堆的概念

在前边的文章中，我们介绍过队列这一数据结构【Queue——队列】,其是一种先入先出的数据结构，但是在一些常见中，如果队列中的元素带有优先级，就可能需要让优先级高的元素先出队列。

实际场景：我们在手机上刷剧时有人打进来电话，那么系统将会优先处理打进来的电话

在这种情况下，我们就有了优先级队列(Priority Queue ）这种数据结构，这种数据结构提供了两个基本操作，一是返回最高优先级对象，二是添加新的对象。

而PriorityQueue的底层使用了堆的数据结构，堆其实就是一棵完全二叉树，若该完全二叉树的每棵子树都是根结点最大叫做大根堆（否则就是小根堆）【也就是说堆中某个节点的值总是不大于或小于其父结点的值】。

1.2 堆的存储方式

堆是一棵完全二叉树，所以可以采用层序的规则来顺序高效存储元素。

微信图片_20230111022402.png

如上图所示的完全二叉树，利用层序规则将其中元素顺序存储到数组中：

微信图片_20230111022356.png

对于非完全二叉树，则不适用于该顺序方式进行存储，因为将会浪费掉一些空间来还原完全二叉树，将会导致其空间利用率较低。

在完全二叉树中，假设i为结点在数组中的下标，则有以下性质：

结点 i 的父结点为(i-1)/2
结点 i 的左孩子节点为2 * i+1，右孩子节点为2 * i+2

1.3 堆的创建

1.3.1 堆的创建与向下调整

我们以集合{27,15,19,18,28,34,65,49,25,37}中的数据为例，来将其创建成堆（以大顶堆为例）：

微信图片_20230111022351.png

堆结构：

public class Heap {
    public int[] elem;
    public int usedSize;//当前堆中有效元素的个数
    public Heap() {
        this.elem=new int[10];
    }
    public void initArray(int[] array) {
        elem= Arrays.copyOf(array,array.length);
        usedSize=elem.length;
    }
}

大顶堆需要满足条件为二叉树中每棵子树中根结点为最大值。

微信图片_20230111022348.png

微信图片_20230111022344.png

步骤：

1.确定最后一棵子树的根结点位置：

需要先找到最后一棵子树的最后一个节点的位置：len-1；

若该节点下标为i，则其父亲节点的下标为（i-1）/2,所以最后一棵子树的根结点为(len-1-1)/2。

2.下一棵子树的根结点为当前根结点-1

建堆：

/**
     * 建堆
     * 时间复杂度：O(N)
     */
    public void createHeap() {
        for (int parent = (usedSize-1-1); parent >=0 ; parent--) {
            shiftDown(parent,usedSize);
    //usedSize保证是所有子树的下标都不会比其大，也可比较用于所有子树的结束
        }
    }

向下调整：

/**
     * 向下调整
     * @param parent 每棵子树的根结点下标
     * @param len 每棵子树的结束位置(usedSize)
     */
    private void shiftDown(int parent,int len) {
        int child=2*parent+1;
        //len(usedSize)记录的是每棵子树的结束位置，只有当child<len时才需要做比较，然后向下调整
        while (child<len) {
            //存在右孩子的情况下，比较左右孩子的大小，child记录较大值的下标
            if(child+1<len&&elem[child]<elem[child+1]) {
                child++;
            }
            //此时child记录的是孩子中的较大值，再去与父节点进行比较
            if(elem[child]>elem[parent]) {
                swap(elem,child,parent);
                //向下调整，让parent到child的位置，继续往下做比较
                parent=child;
                child=2*parent+1;
            }else {
                //如果走到else，说明此时该子树符合大顶堆结构，不需要再做向下调整，直接跳出循环即可
                break;
            }
        }
    }
    /**
     * 交换两结点
     */
    private void swap(int[]array,int i,int j) {
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }

1.3.2 建堆的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

微信图片_20230111022341.png

因此：建堆的时间复杂度为O(N).

1.4 堆的插入与删除

1.4.1堆的插入

微信图片_20230111022337.png

注：当将元素插入堆尾时，若空间不够，则需要扩容。

将最后新插入的节点向上调整，直到满足堆的性质需要向上调整，代码如下：

/**
     * 插入元素（入队）
     * @param x
     */
    public void offer(int x) {
        if(isFull()) {
            elem=Arrays.copyOf(elem,elem.length*2);
        }
        this.elem[usedSize]=x;
        usedSize++;
    }
    public boolean isFull() {
        return usedSize==elem.length;
    }

/**
     * 向上调整
     * @param child 子结点下标
     */
    private void shiftUp(int child) {
        //找到其父结点
        int parent=(child-1)/2;
        //向上调整一直到根结点结束
        while (child>0) {
            //判读子结点与父结点大小
            if(elem[child]>elem[parent]) {
                swap(elem,child,parent);
                child=parent;
                parent=(child-1)/2;
            }else {
                //若不需要调整，则直接跳出循环
                break;
            }
        }
    }

1.4.2堆的删除

微信图片_20230111022333.png

/**
     * 删除元素（出队）
     * @return
     */
    public int poll() {
        if(isEmpty()) {
            return -1;
        }
        int old=elem[0];
        //交换堆顶与堆尾元素
        swap(elem,0,usedSize-1);
        //删除堆尾元素
        usedSize--;
        //将堆顶元素向下调整
        shiftDown(0,usedSize);
        return old;
    }
    public boolean isEmpty() {
        return usedSize==0;
    }

总结：

堆的插入和删除元素的时间复杂度都是O（log₂(N)）,也是树的高度；在向上调整或者向下调整的方法中可以知道，都是从最后一个结点开始调整，一直到根结点结束，若N为结点总个数，则进行log₂(N)次基本操作。

练习：

微信图片_20230111022329.png

答案：

1.A 2.C 3.C 4.C

题解：

1.堆为大顶堆或者小顶堆，其均为完全二叉树，将题目所给顺序排树即可得出是否为堆排序。最后选出答案A。

2.删除堆顶元素8，首先完成堆顶元素8和堆尾元素12的互换，然后堆顶元素的两个子结点15、10进行比较（第一次），较小结点10再与堆顶元素12比较（第二次），互换位置后，12还需要与16比较（第三次），共3次故选C。

3.将构建起的完全二叉树的所有子树做向下调整，得到答案C（该题目为大顶堆）

4.将堆顶元素与堆尾元素互换并将堆尾元素删除，然后将堆顶元素做向下调整得到如图堆示意图：

上一篇：用最大堆构建高效优先队列的方法

下一篇：快速排序器 (Priority Queue)

推荐阅读

快速了解：PriorityQueue - 优先级队列（堆）的实际操作与应用