数据结构中堆及优先级队列的特色解析

文章标题：

数据结构里堆与优先级队列的特性剖析

文章内容：

文章目录

• • 📕1. 堆(Heap)
  • • • ✏️1.1 堆的概念
    • ✏️1.2 堆的存储形式
    • ✏️1.3 堆的构建
    • ✏️1.4 堆的插入
    • ✏️1.5 堆的删除
  • 📕2. 优先级队列(PriorityQueue)
  • • • ✏️2.1 堆和优先级队列的关联
    • ✏️2.2 优先级队列的构造途径
    • ✏️2.3 优先级队列的常用操作
  • 3. Java对象的比较
  • • • 3.1 基于Comparble接口的比较
    • 3.2 基于比较器的比较

📕1. 堆(Heap)

✏️1.1 堆的概念

堆属于一种特殊的完全二叉树，它具备这样的特性：父节点的值要么始终不大于子节点的值，要么始终不小于子节点的值。其中，根节点最大的堆被称作最大堆或者大根堆，根节点最小的堆则叫做最小堆或者小根堆。

堆满足如下两个特性:
1. 堆中任意一个节点的值都不会大于或小于其根节点的值
2. 堆始终是一棵完全二叉树

✏️1.2 堆的存储形式

从堆的概念可知，堆是一棵完全二叉树，所以能够按照层序的规则采用顺序的方式来高效存储。

对于非完全二叉树而言，不适合运用顺序的方式进行存储，因为要还原二叉树的话，空间中得存储空节点，这会使得空间利用率比较低。

当元素存储到数组中后，假设i为节点在数组中的下标，那么有：

1. 若i为0，则该节点为根节点；不然，i节点的双亲节点是 (i - 1)/2
2. 若2 * i + 1 小于节点个数，那么节点i的左孩子下标为2 * i + 1，否则没有左孩子
3. 若2 * i + 2 小于节点个数，那么节点i的右孩子下标为2 * i + 2，否则没有右孩子

✏️1.3 堆的构建

要构建堆，首先得了解向下调整（这里以构建小根堆为例）：

1. 将想要调整的节点标记为parent，child为该节点的左孩子（若存在孩子节点，必定是左孩子）
2. 若存在左孩子节点，即child < size（数组元素个数）时，进行如下操作，直到child < size的条件不成立
   2.1 查看parent的右孩子是否存在，找出左右孩子中较小的那个，并用child标记（若右孩子比左孩子小，则child += 1）
   2.2
   将parent与child进行比较，如果parent <= child，那么调整结束；否则进行元素交换，交换之后，新构建的子树可能不再满足小根堆的条件，所以需要将parent = child，child = parent * 2 + 1，然后重复2步骤。这就是向下调整。

public void siftDown(int[] arr, int parent) {
    // 此时child标记左孩子，因为parent右孩子节点的话必然先有左孩子
    int child = parent * 2 + 1;
    int size = arr.length;
    while (child < size) {
        // 如果右孩子存在，找到左右孩子中较小的孩子，用child标记
        if (child + 1 < size && arr[child] < arr[child + 1]) {
            child += 1;
        }
        // 如果双亲比其最小的孩子还小，说明该结构已满足堆的特性
        if (arr[parent] <= arr[child]) {
            break;
        } else {
            // 将双亲与较小的孩子交换
            int t = arr[parent];
            arr[parent] = arr[child];
            arr[child] = t;
            // parent中大的元素往下移动，可能导致子树不满足堆的性质，因此需继续向下调整
            parent = child;
            child = parent * 2 + 1;
        }
    }
}

了解了向下调整后，对于任意给定的数据，该如何构建成小根堆呢？

public void createHeap(int[] arr) {
    // 找到倒数第一个非叶节点，从该节点位置开始往前一直到根节点，遇到一个节点就应用向下调整
    int root = (arr.length - 2) / 2;
    for (; root >= 0; root--) {
        siftDown(arr, root);
    }
}

还需注意，建堆的时间复杂度为O(N)；

✏️1.4 堆的插入

堆的插入总共分为两个步骤：

1. 先把元素放到数组的最后一个空间中（数组长度不够时需要扩容）
2. 利用向上调整新插入的节点，直至满足堆的特性

向上调整：

public void siftUp(int child) {
    // 以创建小根堆为例
    // 找到child的根节点
    int parent = (child - 1) / 2;

    while (child > 0) {
        // 如果双亲比孩子小，parent满足堆的性质，调整结束
        if (arr[parent] < arr[child]) {
            break;
        } else {
            // 将双亲与孩子节点进行交换
            int tmp = arr[parent];
            arr[parent] = arr[child];
            arr[child] = tmp;
        }

        // 小的元素向下移动，调整后的子树可能不满足堆的性质，因此需继续向上调整
        child = parent;
        parent = (child - 1) / 2;
    }
}

插入数据：

/**
* 插入数据：
* 每次插入到当前堆的最后一个（数组的最后一个），然后向上调整
*/
public void offer(int val) {
    if (isFull()) {
        elem = Arrays.copyOf(elem, 2 * elem.length);
    }
    elem[size] = val;
    // 调整
    siftUp(size);
    size++;
}

✏️1.5 堆的删除

堆的删除包含以下步骤：

1. 将堆顶元素与堆中最后一个元素交换
2. 将堆中有效数据减少一个
3. 对堆顶元素进行向下调整

注意：堆的删除一定删除的是堆顶元素

📕2. 优先级队列(PriorityQueue)

之前我们已经学习过队列，队列是一种先进先出（FIFO）的数据结构，但有些情况下，操作的数据可能带有优先级，出队列时，可能需要优先级高的元素先出队列。比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话。该场景下，使用队列显然不合适，因此数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列（PriorityQueue）。

✏️2.1 堆和优先级队列的关联

首先要明确，堆是一种数据结构，优先级队列也是一种数据结构，二者是完全不同的。优先队列的重点在于优先，队列只是形式。优先级队列不仅可以用堆来实现，用链表也能模拟实现，不过在JDK1.8中，PriorityQueue的底层实现采用了堆这种数据结构。

✏️2.2 优先级队列的构造途径

注意：默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器

✏️2.3 优先级队列的常用操作

优先级队列的扩容说明：
• 如果容量小于64时，是按照oldCapacity的2倍方式扩容的
• 如果容量大于等于64，是按照oldCapacity的1.5倍方式扩容的
• 如果容量超过MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE来进行扩容

3. Java对象的比较

在SE阶段中，我们介绍了引用类型变量使用equals()方法进行比较，基本数据类型变量使用大于号小于号进行比较，故以上两种方法此处不再赘述。

3.1 基于Comparble接口的比较

Comparble是JDK提供的泛型的比较接口类，源码实现具体如下：

public interface Comparable<E> {
    // 返回值:
    // < 0: 表示 this 指向的对象小于 o 指向的对象
    // == 0: 表示 this 指向的对象等于 o 指向的对象
    // > 0: 表示 this 指向的对象大于 o 指向的对象
    int compareTo(E o);
}

对于用户定义类型，如果要想按照大小的方式进行比较时：
在定义类时，实现Comparble接口即可，然后在类中重写compareTo方法。

public class Card implements Comparable<Card> {

    public int rank; // 数值
    public String suit; // 花色

    public Card(int rank, String suit) {
        this.rank = rank;
        this.suit = suit;
    }
    // 根据数值比较，不管花色
    // 这里我们认为 null 是最小的

    @Override
    public int compareTo(Card o) {
        if (o == null) {
            return 1;
        }
        return this.rank - o.rank;
    }

    public static void main(String[] args) {
        Card p = new Card(1, "♠");
        Card q = new Card(2, "♠");
        Card o = new Card(1, "♠");
        System.out.println(p.compareTo(o)); // == 0，表示牌相等
        System.out.println(p.compareTo(q)); // < 0，表示 p 比较小
        System.out.println(q.compareTo(p)); // > 0，表示 q 比较大
    }
}

3.2 基于比较器的比较

Comparator是java.util包中的泛型接口类，源码如下：

public interface Comparator<T> {
    // 返回值:
    // < 0: 表示 o1 指向的对象小于 o2 指向的对象
    // == 0: 表示 o1 指向的对象等于 o2 指向的对象
    // > 0: 表示 o1 指向的对象等于 o2 指向的对象
    int compare(T o1, T o2);
}

按照比较器方式进行比较，具体步骤如下：

1. 用户自定义比较器类，实现Comparator接口
2. 重写Comparator中的compare方法

import java.util.Comparator;

class Card {
    public int rank; // 数值
    public String suit; // 花色

    public Card(int rank, String suit) {
        this.rank = rank;
        this.suit = suit;
    }
}

class CardComparator implements Comparator<Card> {
    // 根据数值比较，不管花色
    // 这里我们认为 null 是最小的

    @Override
    public int compare(Card o1, Card o2) {
        if (o1 == o2) {
            return 0;
        }
        if (o1 == null) {
            return -1;
        }
        if (o2 == null) {
            return 1;
        }
        return o1.rank - o2.rank;
    }

    public static void main(String[] args) {
        Card p = new Card(1, "♠");
        Card q = new Card(2, "♠");
        Card o = new Card(1, "♠");
        // 定义比较器对象
        CardComparator cmptor = new CardComparator();
        // 使用比较器对象进行比较
        System.out.println(cmptor.compare(p, o)); // == 0，表示牌相等
        System.out.println(cmptor.compare(p, q)); // < 0，表示 p 比较小
        System.out.println(cmptor.compare(q, p)); // > 0，表示 q 比较大
    }
}