堆的应用-优先级队列

概念

在很多应用中，我们通常需要按照优先级情况对待处理对象进行处理，比如首先处理优先级最高的对象，然后处理次高的对象。最简单的一个例子就是，在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话。

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

内部原理

优先级队列的实现方式有很多，但最常见的是使用堆来构建

java集合中的优先级队列(PriorityQueue）

常用方法

当然我们PriorityQueue这个实现类还有很多其他方法，例如其自己实现的向上调整方法siftUp或者向下调整方法siftDown等等，包括其自增长方法grow等等，感兴趣同学可以自己下来看看

接下来我们可以看到我们的优先级队列PriorityQueue实现了我们的Queue接口，下面我们先来看一段代码:

public class TestDemo {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue = new PriorityQueue<>();
        //每次插入都会进行向上调整，保证最后是一个小根堆
        priorityQueue.offer(15);
        priorityQueue.offer(45);
        priorityQueue.offer(35);
        priorityQueue.offer(2);
        priorityQueue.offer(44);
        priorityQueue.offer(67);
        priorityQueue.offer(78);
        priorityQueue.offer(89);
        //输出结果为2
        System.out.println(priorityQueue.peek());
        //我们把当前的队头元素弹出
        priorityQueue.poll();
        //输出结果为15
        System.out.println(priorityQueue.peek());
    }
}

按照正常队列来说我们使用peek方法获取队头元素应该为15，而此处的输出结果竟然为2，是所有插入到优先级队列中最小的那个数字，从这里我们可以得出结论，在集合中，我们的优先级队列的底层其实默认为一个小根堆，即我们的优先级队列每次存元素的时候，一定都会保证数据进入堆中后，依然可以维持成一个小堆.,每次取出一个元素的时候，也一定会保证剩下的元素调整为一个小堆.

扩展(将底层默认的小根堆改为大根堆)

我们知道java集合当中的优先级队列PriorityQueue其底层默认是一个小根堆，但是我们就想让其变成大根堆，该怎么办呢？

此时就用到了我们的比较器，也就是我们的Comparator接口，如下所示：

那么下面我们直接来看代码示例:

public class TestDemo {
    public static void main(String[] args) {
        //此时我们PriorityQueue底层默认是一个小根堆，此时我们想要将其变成一个大根堆就需要用到Comparator接口
        //括号里面用到的其实是匿名内部类
        Queue<Integer> qu = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                //这样比较的话就是大根堆
                return o2-o1;
            }
        });
        //每插入一个元素就要进行向上调整
        qu.offer(3);
        qu.offer(1);
        qu.offer(2);
        qu.offer(40);
        qu.offer(6);
        qu.offer(5);
        qu.offer(7);
        qu.offer(9);
        qu.offer(13);
        qu.offer(12);
        //因为此时调整结果为40
        System.out.println(qu.poll());
        //结果为13
        System.out.println(qu.poll());
        //结果为12
        System.out.println(qu.poll());
    }
}

注意事项

1：想要将PriorityQueue底层默认的小根堆改为大根堆，那么就需要使用到我们的Comparator接口，注意代码中的写法属于匿名内部类的写法，后面我们会讲到，大家在这里只需要记住该写法即可

2：需要注意的是，我们的return方法返回的是o2-o1,只有返回这个的时候我们PriorityQueue底层默认才是大根堆，当返回o1-o2的时候底层默认是小根堆，这种写法大家也只需要死记硬背即可.

实战模拟

虽然我们java集合中已经封装了对于优先级队列入队和出队的操作，但是在这里我们还是自己来动手实现一下入队和出队操作，方便大家的理解

注意：在集合中的优先级队列(堆)的出队和入队操作都是针对于其底层的小根堆来操作的，本文所有的例子都是以大根堆进行操作的，但是原理其实是相同的，希望大家注意.

入队列(向上调整)(入堆)

当我们向优先级队列中插入元素的时候，我们的优先级队列一定会再次进行调整，变成新的大根堆或者小根堆.所以此处我们来实现这个调整的过程，我们此处还是接着刚才我们所调整过后的大根堆，在它的基础上我们来继续做实验:

此处我们想在现在这个大根堆中插入100这个值，那么首先先把100这个值插入数组的最后面：

然后开始进行我们的调整，与之前我们堆变成大根堆不同的是，之前的堆完全不是一个大根堆，而我们现在的这个堆是在一个本身就是大根堆的基础上添加了元素后的堆，那么将这个堆调整成大根堆的过程与之前将一个完全不是大根堆的一个堆调整成大根堆的过程在调整的过程上还是有点区别的，前者为向上调整，后者为向下调整，下面来看向上调整的过程：

首先是让P指向我们的37，然后C指向我们的100，在程序中我们是只知道新插入的100这个值的下标，那么怎么获得其双亲结点37的下标呢？其实非常简单，就是使用之前的下标公式parent = (child-1)/2便可以获得，然后100>37，直接互换如下图所示:

2:然后新的C就指向我们当前P的位置，也就是4这个下标处，然后我们P需要指向的下标为1这个下标处，还是利用双亲结点公式便可以获取到P所应指向的结点:

此时100>49,则交换两个值：

3：此时C指向1下标处，P指向0下标处 :

发现100>65,所以继续交换：

最后C指向P,C此时的下标为0，而P指向的下标为(0-1)/2=负数,负数不存在，那么P为负数就代表最终我们调整完毕，此时我们的优先级队列在插入元素后，又及时调整成了一个大根堆，接下来我们来看代码实现吧。

代码预期结果:

调整完后的大根堆按照层序遍历的结果为：

100 65 34 25 49 27 19 18 15 28 37

代码实现

首先实现我们的入队方法push和向上调整的adjustUp方法

package heap;
import java.util.Arrays;
public class HeapDemo {
    //堆的底层存储是顺序数组
    public int[] elem;
    //表示我们堆中的元素个数，同时也是我们堆调整时结束的标志
    public int usedSize;
    //初始化的时候为堆的底层数组创建一个默认的大小
    public HeapDemo() {
        this.elem = new int[10];
    }
    /**
     * 注意在这里为什么要传len
     * 传len的目的是告诉堆调整结束时的时间，因为每颗子树在进行向下调整时最后结束的条件是一样的
     * 就是当下标值大于堆中元素个数-1的时候就停止调整了
     * 所以len就代表每次调整结束的位置，而我们传入的len的值其实就是usedSize
     * adjustDown的时间复杂度为O(log2(n))
     *
     * @param parent
     * @param len
     */
    //向下调整
    public void adjustDown(int parent, int len) {
        //获取当前根节点的左子树的下标值
        int child = 2 * parent + 1;
        //child<len的时候说明有左子树，但是未必有右子树
        while (child < len) {
            //注意要加上child+1<len这个操作，原因是可能会没有右孩子只有左孩子
            if (child + 1 < len && this.elem[child] < this.elem[child + 1]) {
                child++;
            }
            //代码如果走到这里就代表child此时一定是左右孩子中的最大值所对应的下标
            if (this.elem[child] > this.elem[parent]) {
                int tmp = this.elem[child];
                this.elem[child] = this.elem[parent];
                this.elem[parent] = tmp;
                parent = child;
                child = 2 * parent + 1;
            } else {
                /*因为是从最后一棵树开始调整的  只要我们 找到了
                this.elem[child] <= this.elem[parent]，就说明后续就不需要循环了
                后面的都已经是大根堆了，所以直接break即可*/
                break;
            }
        }
    }
    //创建一个堆
    //createBigHeap方法的时间复杂度为O(nlogn)
    //其实本质上来说建立一个大根堆和建立一个小根堆方法的时间复杂度为O(n)
    public void createBigHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            this.usedSize++;
        }
        //此处的i其实就代表了我们的图中P每次的下标
        //this.usedSize - 1 - 1是为了获取我们堆中最后一棵子二叉树的父亲节点的下下标
        //第一次减1是因为我们按照层序遍历拍序号的时候我们是从0开始编号的，而第二次减1是已知子节点求父节点下标的公式
        //代表我们从最后一刻子树开始调整
        for (int i = (this.usedSize - 1 - 1) / 2; i >= 0; i--) {
            adjustDown(i, this.usedSize);
        }
    }
    /**
     * push方法作用为向一个大根堆中插入元素，并将插入元素后的堆继续调整为大根堆
     */
    public void push(int val) {
        if (isFull()) {
            //如果堆底层的数组满了就进行扩容为原来的二倍
            this.elem = Arrays.copyOf(this.elem, this.elem.length * 2);
        }
        this.elem[this.usedSize] = val;
        //此时插入一个元素后原来的usedSize为10，现在变成了11
        this.usedSize++;
        //进行向上调整
        //此时这个元素插入到了数组的最后一个位置处，传入的应该是其下标为usedSize-1
        adjustUp(this.usedSize-1);
    }
    //判断当前堆是否已满
    public boolean isFull() {
        return this.usedSize == this.elem.length;
    }
    //向上调整
    public void adjustUp(int child) {
        int parent = (child - 1) / 2;
        while (child > 0) {
            if (this.elem[child] > this.elem[parent]) {
                int tmp = this.elem[child];
                this.elem[child] = this.elem[parent];
                this.elem[parent] = tmp;
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }
    //打印我们调整后的结果
    public void show() {
        for (int i = 0; i < usedSize; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }
}

测试类：

public class TestDemo {
    public static void main(String[] args) {
       HeapDemo demo = new HeapDemo();
       //建立我们想要调整的堆
       int[] array = { 27,15,19,18,28,34,65,49,25,37};
       //调整前的数组结果为[27, 15, 19, 18, 28, 34, 65, 49, 25, 37]
        System.out.println(Arrays.toString(array));
       //创建我们的大根堆
       demo.createBigHeap(array);
       //此时向我们已经创建好的大根堆内再次插入一个元素100
        demo.push(100);
       //调整后结果为100 65 34 25 49 27 19 18 15 28 37
       demo.show();
    }
}

关于向上调整方法adjustUp的时间复杂度为O(log2(n)).

出队列(出堆)

在优先级队列中出队列的那个元素一定是这个队列中优先级最高的那个元素，而在集合中的优先级队列因为其底层是一个小根堆，所以每次出队的元素一定是所有元素中值最小的那个，因为本文是按照大概堆实现的，所以出队的那个元素一定是值最大的那个元素.

我们还是拿之前的大根堆来举例子，模拟出队的过程：

此时对于这个大根堆来说，当我们执行出队操作的时候，出队的元素一定是65，并且出队后仍需要保持当前的堆是一个大根堆

那么我们的思路是这样的：

1：将我们第一个元素和最后一个元素进行交换:交换后删除最后一个元素即完成了我们出队列的第一步操作

2：当然我们出队可不能光说是将元素出队了就没事了，同时还要保证我们剩下的堆仍然是一个大根堆，这就到了我们的第二步，进行向下调整，并且只需要调整0号下标就好了

所以最终当我们将65出队后，进行完向下调整后，最后的结果如下所示:

下面我们来完成我们的出队方法poll

代码示例

package heap;
public class HeapDemo {
    //堆的底层存储是顺序数组
    public int[] elem;
    //表示我们堆中的元素个数，同时也是我们堆调整时结束的标志
    public int usedSize;
    //初始化的时候为堆的底层数组创建一个默认的大小
    public HeapDemo() {
        this.elem = new int[10];
    }
    /**
     * 注意在这里为什么要传len
     * 传len的目的是告诉堆调整结束时的时间，因为每颗子树在进行向下调整时最后结束的条件是一样的
     * 就是当下标值大于堆中元素个数-1的时候就停止调整了
     * 所以len就代表每次调整结束的位置，而我们传入的len的值其实就是usedSize
     * adjustDown的时间复杂度为O(log2(n))
     *
     * @param parent
     * @param len
     */
    //向下调整
    public void adjustDown(int parent, int len) {
        //获取当前根节点的左子树的下标值
        int child = 2 * parent + 1;
        //child<len的时候说明有左子树，但是未必有右子树
        while (child < len) {
            //注意要加上child+1<len这个操作，原因是可能会没有右孩子只有左孩子
            if (child + 1 < len && this.elem[child] < this.elem[child + 1]) {
                child++;
            }
            //代码如果走到这里就代表child此时一定是左右孩子中的最大值所对应的下标
            if (this.elem[child] > this.elem[parent]) {
                int tmp = this.elem[child];
                this.elem[child] = this.elem[parent];
                this.elem[parent] = tmp;
                parent = child;
                child = 2 * parent + 1;
            } else {
                /*因为是从最后一棵树开始调整的  只要我们 找到了
                this.elem[child] <= this.elem[parent]，就说明后续就不需要循环了
                后面的都已经是大根堆了，所以直接break即可*/
                break;
            }
        }
    }
    //创建一个堆
    //createBigHeap方法的时间复杂度为O(nlogn)
    //其实本质上来说建立一个大根堆和建立一个小根堆方法的时间复杂度为O(n)
    public void createBigHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            this.usedSize++;
        }
        //此处的i其实就代表了我们的图中P每次的下标
        //this.usedSize - 1 - 1是为了获取我们堆中最后一棵子二叉树的父亲节点的下下标
        //第一次减1是因为我们按照层序遍历拍序号的时候我们是从0开始编号的，而第二次减1是已知子节点求父节点下标的公式
        //代表我们从最后一刻子树开始调整
        for (int i = (this.usedSize - 1 - 1) / 2; i >= 0; i--) {
            adjustDown(i, this.usedSize);
        }
    }
    //出队方法
    public int poll() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        //使用ret保存我们要删除的元素
        int ret = this.elem[0];
        //第一步，将第一个元素和最后一个元素进行交换
        int tmp = this.elem[0];
        this.elem[0] = this.elem[this.usedSize - 1];
        this.elem[this.usedSize - 1] = tmp;
        //--后的usedSize的值为9
        this.usedSize--;
        //第二步，将剩下的堆仍然变成大根堆，进行向下调整，并且只对0号下标进行调整
        adjustDown(0, this.usedSize);
        return ret;
    }
    //判断当前的堆是否为空
    public boolean isEmpty() {
        return this.usedSize == 0;
    }
    //打印我们调整后的结果
    public void show() {
        for (int i = 0; i < usedSize; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }
}

测试类:

public class TestDemo {
    public static void main(String[] args) {
        HeapDemo demo = new HeapDemo();
        //建立我们想要调整的堆
        int[] array = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
        //调整前的数组结果为[27, 15, 19, 18, 28, 34, 65, 49, 25, 37]
        System.out.println(Arrays.toString(array));
        //创建我们的大根堆，并进行向下调整
        demo.createBigHeap(array);
        //经历过向下调整的全新的大根堆为65 49 34 25 37 27 19 18 15 28
        demo.show();
        //此时出队列的结果应该为65
        System.out.println(demo.poll());
        //出队后调整的结果为49 37 34 25 28 27 19 18 15
        //可以看出出队后会自行调整，继续变成一个大根堆
        demo.show();
    }
}

一篇搞懂优先级队列(堆)（二）

堆的应用-优先级队列

概念

内部原理

java集合中的优先级队列(PriorityQueue）

常用方法

扩展(将底层默认的小根堆改为大根堆)

实战模拟

入队列(向上调整)(入堆)

代码实现

出队列(出堆)

代码示例

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

一篇搞懂优先级队列(堆)（二）

堆的应用-优先级队列

概念

内部原理

java集合中的优先级队列(PriorityQueue）

常用方法

扩展(将底层默认的小根堆改为大根堆)

实战模拟

入队列(向上调整)(入堆)

代码实现

出队列(出堆)

代码示例

热门文章

最新文章

相关电子书