Java数据结构之优先级队列(堆)图文详解

什么是优先级队列(堆)

优先级队列(堆)是一种非常重要的数据结构，它能够更好地管理数据，分配任务等。优先级队列的本质就是一种特殊的队列，它是一种可以根据元素的优先级来出队的数据结构。

通常情况下，队列中存储了一系列具有优先级的数据。当我们从队列中取出元素时，优先级高的元素会先出队。因此，我们需要一种数据结构，来对这些元素进行优先级处理。

在优先级队列中，堆是最常用的一种数据结构。堆本身就是一种树形结构，可以很好地管理优先级队列。

堆的基本概念

堆是一种满足两种性质的树形数据结构:

1. 最大堆性质或最小堆性质

最大堆性质、最小堆性质可以根据实际情况来确定。在本文中我们以最大堆性质，也就是父节点的权值比子节点的权值大为例。

1. 完全二叉树

完全二叉树可以这样理解：除了最后一层，其他每层都必须是完全填满的，最后一层仅允许出现最右侧的若干位置为空。

堆可以分为两种类型：大根堆（Max Heap）和小根堆（Min Heap）

• 大根堆（Max Heap）：在一个大根堆中，父节点的权值比子节点的权值大。
• 小根堆（Min Heap）：在一个小根堆中，父节点的权值比子节点的权值小。

在Java中，优先级队列可以通过java.util.PriorityQueue来实现，该类底层通过二叉小根堆实现。我们在实际开发过程中，只需要简单调用Java API中的方法来进行使用就好。

堆的应用

堆在数据结构中有广泛的应用，主要有以下两种：

1. 堆排序

堆本身就是一种排序方法，也称为堆排序。它的时间复杂度是O(nlogn)。堆排序将一个无序的序列构建成一个堆，然后将堆的根节点输出，递归地输出剩余的元素。由于建堆的时间为O(n)，输出堆顶元素后，可以每次将剩余堆的最后一个元素放到堆顶，再重新进行堆化。这个过程下来，只需要O(nlogn)的时间，即可对序列进行排序。

1. 模拟优先级队列

在程序中，优先级队列是一种常见的数据结构，通常用于任务调度、网络通信等需要对任务进行优先级处理的场景。Java提供了PriorityQueue类来实现优先级队列，其底层是使用堆来实现的。我们只需要根据实际的需求，来实现对应的堆。

堆的实现

在Java中，堆的实现可以使用数组来完成，同时为了使数组下标从1开始，下标为0的位置不保存数值。

基本实现

public class Heap {

    // 数组存储堆的节点
    private int[] a;

    // 堆的大小
    private int n;

    // 堆的容量
    private int capacity;

    // 构造函数，初始化堆
    public Heap(int capacity) {
        this.a = new int[capacity + 1];
        this.n = 0;
        this.capacity = capacity;
    }

    // 获取堆中的最大值
    public int getMax() {
        if (n == 0) {
            return -1;
        }
        return a[1];
    }

    // 加入一个新的元素
    public boolean insert(int x) {
        if (n == capacity) {
            return false;
        }
        ++n;
        a[n] = x;
        // 堆化操作
        int i = n;
        while (i > 1 && a[i] > a[i/2]) {
            swap(a, i, i/2);
            i = i/2;
        }
        return true;
    }

    // 删除堆顶元素
    public boolean removeMax() {
        if (n == 0) {
            return false;
        }
        a[1] = a[n];
        --n;
        // 堆化操作
        heapify(a, n, 1);
        return true;
    }

    // 堆化操作
    private static void heapify(int[] a, int n, int i) {
        while (true) {
            int maxPos = i;
            if (i*2 <= n && a[i*2] > a[i]) {
                maxPos = i*2;
            }
            if (i*2+1 <= n && a[i*2+1] > a[maxPos]) {
                maxPos = i*2+1;
            }
            if (maxPos == i) {
                break;
            }
            swap(a, i, maxPos);
            i = maxPos;
        }
    }

    // 交换
    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

堆排序实现

public static void heapSort(int[] a) {
        if (a.length <= 1) {
            return;
        }
        // 建堆
        buildHeap(a, a.length-1);
        // 排序
        for (int i = a.length-1; i >= 1; i--) {
            swap(a, 1, i);
            heapify(a, i-1, 1);
        }
    }

    // 建堆
    private static void buildHeap(int[] a, int n) {
        for (int i = n/2; i >= 1; i--) {
            heapify(a, n, i);
        }
    }

示例说明

示例一：使用堆实现TopK

假设我们有一个数据集合，我们需要从中找出前K个最大的数。这个时候，我们就可以使用堆来实现。

比如，假设数据集合为{1,3,5,7,2,4,6,8,9,0}，我们需要找出前3个最大的数。那么我们就可以使用一个大小为3的最小堆来存储数据，每当插入一个新数据时，我们比较其与当前堆的根节点的大小，如果小于等于根节点，则跳过，否则则将该数据插入到堆中，并将堆中最小的数据删除。最终得到的就是前3个最大的数：{7,8,9}。

示例二：使用优先级队列模拟数据中心的任务调度

在某个数据中心中，需要处理很多任务，但是不同的任务的优先级不同。优先级高的任务需要先执行，优先级低的任务则需要等待。这个时候，我们可以使用优先级队列来模拟任务调度。

我们可以定义一个Task类，存储任务的信息，包括任务的优先级、创建时间、执行时间等等。然后使用PriorityQueue来存储这些任务。每当有新的任务进入时，我们可以将其加入到PriorityQueue中，PriorityQueue会自动根据优先级来排序。然后我们创建一个单独的线程来不断地从PriorityQueue中获取任务，执行任务，并更新PriorityQueue。

例如，我们有以下三个任务：

Task 1:
Priority: 2
CreateTime: 2021-10-01 08:00:00
ExecuteTime: 2021-10-01 08:10:00

Task 2:
Priority: 1
CreateTime: 2021-10-01 08:00:00
ExecuteTime: 2021-10-01 08:30:00

Task 3:
Priority: 3
CreateTime: 2021-10-01 08:00:00
ExecuteTime: 2021-10-01 08:20:00

首先，我们将三个任务加入PriorityQueue中，PriorityQueue会自动根据优先级排序。然后，我们开启一个线程来处理任务。该线程首先从PriorityQueue中获取优先级最高的任务，也就是Task 3；然后执行Task 3，并更新PriorityQueue；接着获取Task 1，执行Task 1，并更新PriorityQueue；最后获取Task 2，执行Task 2，并更新PriorityQueue。这个过程下来，所有的任务都会被正确地执行。