数据结构——优先队列与堆-阿里云开发者社区

一、什么是优先队列与堆

优先级队列的底层实际上就是利用堆这种数据结构实现的。

堆在逻辑上是一棵完全二叉树，而其物理结构却是数组，二叉树中的每个节点对应着数组的下标树中的第一个节点（根节点）的数组下标为0，树中的最后一个节点不一定为数组的最后一个元素（数组可能没满），而我们学习的堆，分为两种：

① 大顶堆：每个双亲节点的值都 >= 其左右孩子节点的值，此外，根节点的值一定是所有堆中其余节点的最大值。

② 小顶堆：每个双亲节点的值都 <= 其左右孩子节点的值，此外，根节点的值一定是所有堆中其余节点的最小值。

二、通过代码创建一个堆

说明一下：这里只是采用个人逻辑创建的一个堆，旨在与更深入地理解堆这个数据结构。

创建一个 .java 文件，里面放着一个类 Heap，通过 createHeap( ) 方法和 shiftDown( ) 来模拟一个堆。

public class Heap {
    public int [] elem;
    public int usedSize;
    public Heap() {
        this.elem = new int[10];
    }
    //创建一个堆
    public void createHeap(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            this.elem[i] = arr[i];
            usedSize++;
        }
        for (int parent = ((usedSize-1)-1) / 2; parent >= 0 ; parent--) {
            shiftDown(parent, usedSize);
        }
    }
    //向下调整
    public void shiftDown(int parent, int len){
        int child = parent*2 +1 ;
        while (child < len){
            if(child+1 < len && elem[child] < elem[child+1]){
                child++; //保证 child 走到左右最大的一个节点
            }
            if(elem[parent] < elem[child]){
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
            }else {
                break;
            }
            parent = child;
            child = parent*2 +1 ;
        }
    }
    //打印堆元素（层序）
    public void print(){
        for (int i = 0; i < usedSize; i++) {
            System.out.print(elem[i] + " ");
        }
        System.out.println();
    }
}

创建另一个 .java 文件，里面用主函数进行测试

public class Test {
    public static void main(String[] args) {
        int[] arr = {4,0,2,1,5,6,9,8,3,7};
        Heap heap = new Heap();
        System.out.println(Arrays.toString(arr));
        heap.createHeap(arr);
        System.out.println("-------------大顶堆-------------");
        heap.print();
    }
}

原始的堆：

优化成大顶堆：

输出结果：

在上述代码中，如果我们创建一个小顶堆，那么只需要更改几个不等号即可。

三、堆排序

一类问题：给定一组数据，将其按升序/逆序排序。

我们见过冒泡排序，但是本次我们通过堆排序进行操作。

举例，给定下列的数组 arr，让其升序排序

int[] arr = {4,0,2,1,5,6,9,8,3,7};
//排序后：0 1 2 3 4 5 6 7 8 9

堆排序思路：

① 在排序数组之前，我们要让数组符合大顶堆的逻辑

② 循环交换堆顶元素（即数组第一个元素）和堆尾元素（即数组最后一个元素），那么这样一来，数组的末尾逐渐排好

注意：每交换一次元素，我们就得重新让堆变成大顶堆逻辑，之后才能继续交换，这样做目的是：我们始终要让堆顶的元素处于最大值。

创建一个 .java 文件，里面放着一个类 Heap，通过 createHeap( ) 方法和 shiftDown( ) 来模拟一个堆，通过 heapSort( ) 进行堆排序

public class Heap {
    public int [] elem;
    public int usedSize;
    public Heap() {
        this.elem = new int[10];
    }
    //创建一个大顶堆
    public void createHeap(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            this.elem[i] = arr[i];
            usedSize++;
        }
        for (int parent = ((usedSize-1)-1) / 2; parent >= 0 ; parent--) {
            shiftDown(parent, usedSize);
        }
    }
    //向下调整
    public void shiftDown(int parent, int len){
        int child = parent*2 +1 ;
        while (child < len){
            if(child+1 < len && elem[child] < elem[child+1]){
                child++; //保证 child 走到左右最大的一个节点
            }
            if(elem[parent] < elem[child]){
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
            }else {
                break;
            }
            parent = child;
            child = parent*2 +1 ;
        }
    }
    public void heapSort(){
        int end = usedSize-1;
        while(end > 0){
            int temp = elem[0];
            elem[0] = elem[end];
            elem[end] = temp;
            end--;
            shiftDown(0,end);
        }
    }
    //打印堆元素（层序）
    public void print(){
        for (int i = 0; i < usedSize; i++) {
            System.out.print(elem[i] + " ");
        }
        System.out.println();
    }
}

创建另一个 .java 文件，里面用主函数进行测试

public class Test {
    public static void main(String[] args) {
        int[] arr = {4,0,2,1,5,6,9,8,3,7};
        Heap heap = new Heap();
        System.out.println(Arrays.toString(arr));
        heap.createHeap(arr);
        System.out.println("-------------创建一个大顶堆-------------");
        heap.print();
        System.out.println("-------------进行堆排序-------------");
        heap.heapSort();
        heap.print();
    }
}

输出结果：

四、Java 实现的优先队列

我们来测试一下 Java 实现的优先级队列，并使用一些对应的方法：

可以发现 Java 集合框架中实现的优先级队列，它的底层实际上默认就是一个小顶堆。而我们不管使用了 offer( ) 方法，还是 poll( ) 方法，使用过后，Java 底层会自动将数组变换成小顶堆，也就是说：只要你向优先级队列中传入了数据，那么之后你所进行的所有操作，都只应用于小顶堆。

import java.util.PriorityQueue;
public class Test1 {
    public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(7);
        System.out.println(priorityQueue);
        priorityQueue.offer(3);
        System.out.println(priorityQueue);
        priorityQueue.offer(1);
        System.out.println(priorityQueue);
        priorityQueue.offer(5);
        System.out.println(priorityQueue);
        System.out.println(priorityQueue.size());
        System.out.println(priorityQueue.peek());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue);
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue);
        System.out.println(priorityQueue.size());
    }
}

输出结果：

1. 深度解析offer( ) 方法

这里的 offer( ) 方法采用了向上调整的逻辑，与我们之前的建堆逻辑不同，因为这里是从数组的尾部一个一个加进去的，通俗地说，就是先尾插，然后 Java 实现的优先级队列会自动为我们调整为小顶堆。

2. 深度解析poll( ) 方法

这里的 poll ( ) 方法并不是从数组的头部一个一个删除的，而是先将数组的第一个元素与数组的最后一个元素进行交换，之后进行调整。也就是说：我们每一次 poll 之后，底层就会帮我们调整为小顶堆。

下面是进行了优先队列的循环添加和循环删除，更好理解：

import java.util.PriorityQueue;
public class Test2 {
    public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        int[] arr = {4,2,5,6,0,9,1,8,3,7};
        for (int i = 0; i < 10; i++) {
            priorityQueue.offer(arr[i]);
            System.out.println(priorityQueue);
        }
        System.out.println("----------------------------------");
        for (int i = 0; i < 10; i++) {
            priorityQueue.poll();
            System.out.println(priorityQueue);
        }
    }
}

输出结果：

五、深度理解 Java 优先队列底层的代码

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Test1 {
    public static void main(String[] args) {
        //默认 优先级队列中的元素为11
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        int [] arr1 = {4,0,2,1,5,6,9,8,3,7};
        System.out.println(Arrays.toString(arr1));
        for (int i = 0; i < arr1.length; i++) {
            minHeap.offer(arr1[i]);
        }
        System.out.println("---------------小顶堆---------------");
        System.out.println(minHeap);
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int i = 0; i < arr1.length; i++) {
            maxHeap.offer(arr1[i]);
        }
        System.out.println("---------------大顶堆---------------");
        System.out.println(maxHeap);
        int k = 3;
        PriorityQueue<Integer> maxHeap2 = new PriorityQueue<>(k,new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int i = 0; i < k; i++) {
            maxHeap2.offer(arr1[i]);
        }
        System.out.println("---------------大顶堆---------------");
        System.out.println(maxHeap2);
    }
}

输出结果如下，关于使用 offer( ) 方法后，怎么进行调整为大顶堆/小顶堆，我已经通过上面两幅图说明的很清楚了。接下来我们一起来看看为什么我们要让堆实现内部类。

输出结果：

总结：

下面的这幅图是 Java 底层实现优先级队列的源码，当我们只看代码的时候，我要说明以下几点

① 在 PriorityQueue 类，当我们没有给定初始容量时，其默认容量为 11 ，当然我们也可以自己给定初始容量。

② 当我们不实现内部类，不传参的时候， PriorityQueue 类默认底层实现的是小顶堆。

③ 我们可以通过接口 Comparator，来重写 compare( ) 方法，以此来实现小顶堆或大顶堆。

小顶堆和大顶堆的语法格式

格式1

//默认为小顶堆，初始优先级队列的数组容量为11
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

格式2

为什么会出现格式2 这种形式？

在下面的代码块中，实际上我们并不是直接通过 Comparator 接口 new 了一个对象，而是通过匿名内部类实现了 Comparator 接口，并重写了 compare( ) 方法，这就是匿名内部类的语法。而这么做是为了更清楚地知道优先队列底层：堆这个数据结构是按什么比较的。

//小顶堆，初始优先级队列的数组容量为11
PriorityQueue<Integer> minHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

格式3

在下面的格式中，我们可以看到，在 compare( ) 方法中，我们将 o2 和 o1 的位置调换过来了，对照格式2，我们就能清楚地明白，下面地程序是一个大顶堆地构造方式，因为大顶堆的堆顶永远是最大的元素。

//大顶堆，初始容量为3
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(3,new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

六、使用堆解决TopK问题

一类问题：给你一组数据，让你求这组数据中前 k 个最大的 / 最小的元素

举例题目：给你下面的一个数组 arr，求出其前三个最小的元素

int[] arr = {4,2,5,6,0,9,1,8,3,7};
//最小的三个元素 0,1,2

下面两个方法求的均是前 k 个最小的元素，当求前 k 个最大的元素逻辑其实是一样的，只是转换一下堆的使用即可。

方法一

创建一个大小为 3 的一个大顶堆
开始遍历数组
（1）前 k 个元素组建成大顶堆
（2）从 k+1 个元素开始，开始进行与堆顶判断
（3）如果新添加的元素＜堆顶的元素，那么就先头删，再尾插，过程中底层会自动帮我们调整大顶堆顺序
把前 k 个元素放入一个新的数组中，并返回给主函数

public class Test1 {
    public static void main(String[] args) {
        int[] arr = {4,2,5,6,0,9,1,8,3,7};
        int k = 3;
        int[] ret = topK(arr,k);
        System.out.println(Arrays.toString(ret));
    }
    public static int[] topK(int[] arr, int k){
        //1. 创建一个大小为 k 的一个大顶堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        //2. 开始遍历数组
        for (int i = 0; i < arr.length; i++) {
            //2.1 前 k 个元素组建成大顶堆
            if(maxHeap.size() < k){
                maxHeap.offer(arr[i]);
            }else {
                //2.2 从 k+1 个元素开始，开始进行与堆顶判断
                int top = maxHeap.peek();
                if(top > arr[i]){
                    maxHeap.poll();
                    maxHeap.offer(arr[i]);
                }
            }
        }
        //3. 把前 k 个元素放入一个新的数组中，并返回给主函数
        int [] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = maxHeap.poll();
        }
        return ret;
    }
}

输出结果：

方法二

创建一个小顶堆
将堆顶元素一个一个弹出至 ret 数组中

import java.util.Arrays;
import java.util.PriorityQueue;
public class Test1 {
    public static void main(String[] args) {
        int[] arr = {4,2,5,6,0,9,1,8,3,7};
        int k = 3;
        topK(arr,k);
    }
    public static void topK(int[] arr, int k){
        //1. 创建一个小顶堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            minHeap.offer(arr[i]);
        }
        System.out.println(minHeap);
        int [] ret = new int[k];
        //2. 将堆顶元素弹出至 ret 数组中
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        System.out.println(Arrays.toString(ret));
    }
}

输出结果：

七、leetcode 373 查找和最小的K对数字

leetcode 373

下面的两种方法就是使用我刚刚堆的性质来做的，主要我们需要理解一下思想

方法一

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        //1. 创建一个大顶堆
        PriorityQueue<List<Integer>> maxHeap = new PriorityQueue<>(k, new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return ( o2.get(0)+o2.get(1) ) - ( o1.get(0)+ o1.get(1) ) ;
            }
        });
        //2. 遍历二维数组
        for (int i = 0; i < Math.min(nums1.length,k); i++) {
            for (int j = 0; j < Math.min(nums2.length,k); j++) {
                //2.1 将前三个一维数组放入大顶堆中
                if(maxHeap.size() < k){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums1[i]);
                    list.add(nums2[j]);
                    maxHeap.offer(list);
                }else{
                    //2.2 从第四个一维数组开始，与堆顶数组进行判断
                    int top = maxHeap.peek().get(0) + maxHeap.peek().get(1);
                    if( nums1[i] + nums2[j] < top){
                        maxHeap.poll();
                        List<Integer> list = new ArrayList<>();
                        list.add(nums1[i]);
                        list.add(nums2[j]);
                        maxHeap.offer(list);
                    }
                }
            }
        }
        List<List<Integer>> ret  = new ArrayList<>();
        for (int i = 0; i < k && !maxHeap.isEmpty() ; i++) {
            ret.add(maxHeap.poll());
        }
        return ret;
    }
}

为什么 for 循环的边界可以使用 Math.min( length, k) ？因为题目给出的原数组是两个升序的数组。

for (int i = 0; i < Math.min(nums1.length,k); i++) {
  for (int j = 0; j < Math.min(nums2.length,k); j++) {
  }
}

方法二

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<List<Integer>> minHeap = new PriorityQueue<>(k, new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return (o1.get(0)+o1.get(1)) - (o2.get(0)+o2.get(1));
            }
        });
        for (int i = 0; i < Math.min(nums1.length,k); i++) {
            for (int j = 0; j < Math.min(nums2.length,k); j++) {
                List<Integer> list = new ArrayList<>();
                list.add(nums1[i]);
                list.add(nums2[j]);
                minHeap.offer(list);
            }
        }
        List<List<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < k && !minHeap.isEmpty(); i++) {
            ret.add(minHeap.poll());
        }
        return ret;
    }
}

数据结构——优先队列与堆

一、什么是优先队列与堆

二、通过代码创建一个堆

三、堆排序

一类问题：给定一组数据，将其按升序/逆序排序。

四、Java 实现的优先队列

1. 深度解析offer( ) 方法

2. 深度解析poll( ) 方法

五、深度理解 Java 优先队列底层的代码

小顶堆和大顶堆的语法格式

格式1

格式2

格式3

六、使用堆解决TopK问题

一类问题：给你一组数据，让你求这组数据中前 k 个最大的 / 最小的元素

方法一

方法二

七、leetcode 373 查找和最小的K对数字

方法一

方法二

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

数据结构——优先队列与堆

一、什么是优先队列与堆

二、通过代码创建一个堆

三、堆排序

一类问题：给定一组数据，将其按升序/逆序排序。

四、Java 实现的优先队列

1. 深度解析offer( ) 方法

2. 深度解析poll( ) 方法

五、深度理解 Java 优先队列底层的代码

小顶堆和大顶堆的语法格式

格式1

格式2

格式3

六、使用堆解决TopK问题

一类问题：给你一组数据，让你求这组数据中前 k 个最大的 / 最小的元素

方法一

方法二

七、leetcode 373 查找和最小的K对数字

方法一

方法二

热门文章

最新文章

相关课程

相关电子书