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

一、什么是优先队列与堆

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

堆在逻辑上是一棵完全二叉树，而其物理结构却是数组，二叉树中的每个节点对应着数组的下标树中的第一个节点（根节点）的数组下标为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对数字

方法一

方法二

热门文章

最新文章

相关课程

相关电子书