数据结构 - 6（ 堆与优先级队列 7000 字详解 ）

一：堆

1.1 堆的基本概念

堆分为两种：大堆和小堆。它们之间的区别在于元素在堆中的排列顺序和访问方式。

1. 大堆（Max Heap）：

在大堆中，父节点的值比它的子节点的值要大。也就是说，堆的根节点是堆中最大的元素。大堆被用于实现优先级队列，其中根节点的元素始终是队列中最大的元素。

3. 小堆（Min Heap）：

在小堆中，父节点的值比它的子节点的值要小。也就是说，堆的根节点是堆中最小的元素。小堆常用于实现优先级队列，其中根节点的元素始终是队列中最小的元素。

以下是一个示例图示，展示了一个包含 7 个元素的大堆和小堆的结构：

大堆：
        90
      /    \
    75      30
   /  \    /  \
  20   15  10   7

小堆：
        7
      /   \
    10     30
   /  \   /  \
  20   15 75  90
1
2
3
4
5
6
7
8
9
10
11
12
13

注意：堆总是一颗完全二叉树

1.2 堆的存储方式

从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储，

注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。

将元素存储到数组中后，可以根据二叉树章节的性质 5 对树进行还原，假设 i 为节点在数组中的下标，则有：

• 如果 i 为 0，则 i 表示的节点为根节点
• 节点 i 的左孩子下标为 2 * i + 1 ( 如果这个值小于节点个数，则没有左孩子 )
• 节点 i 的右孩子下标为 2 * i + 2 ( 如果这个值小于节点个数，则没有右孩子 )

1.3 堆的下沉

对于集合 { 27,15,19,18,28,34,65,49,25,37 } 中的数据，如果将其创建成小堆呢？

仔细观察上图后发现：根节点的左右子树已经完全满足堆的性质，因此只需将根节点向下调整好即可。

下面是代码实现：

// shiftDown方法用来实现下沉操作
// array参数是待构建小堆的数组
// parent参数是当前需要下沉的节点的索引
public void shiftDown(int[] array, int parent) {
    int length = array.length;
    int child = 2 * parent + 1; // 左子节点索引
    
    while (child < length) {
        // 找到左右孩子中较小的孩子
        if (child + 1 < length && array[child] > array[child + 1]) {
            child++; // 如果右子节点存在并且小于左子节点的值，则将child指向右子节点
        }
        
        // 如果当前节点小于或等于左右子节点中较小的节点，说明已经符合小堆要求
        if (array[parent] <= array[child]) {
            break;
        }
        
        // 否则，交换当前节点和较小子节点的值，接着需要继续向下调整
        int temp = array[parent];
        array[parent] = array[child];
        array[child] = temp;
        
        parent = child;
        child = 2 * parent + 1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

这段代码实现了堆排序中的下沉操作（也称为向下调整或堆化）。下沉操作用于维护小堆的性质，确保父节点永远小于或等于其子节点。

时间复杂度分析：最坏的情况即图示的情况，从根一路比较到叶子，比较的次数为完全二叉树的高度，即时间复杂度为 O（log n）

1.4 堆的创建

那对于普通的序列 { 1,5,3,8,7,6 }，即根节点的左右子树不满足大堆的特性，又该如何调整呢？

参考代码：

public static void createHeap(int[] array) {
  // 找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整
  int root = ((array.length-2)>>1);
  for (; root >= 0; root--) {
    shiftDown(array, root);
 }
}
1
2
3
4
5
6
7

1.5 建堆的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明( 时间复杂度本来看的就是近似值，多几个节点不影响最终结果 )：

因此：建堆的时间复杂度为 O(N)。

1.6 堆的插入和删除

1.6.1 堆的插入

堆的插入总共需要两个步骤：

1. 先将元素放入到底层空间中(注意：空间不够时需要扩容)
2. 将最后新插入的节点向上调整，直到满足堆的性质

下面是堆的删除操作的代码实现：

1.6.2 堆的删除

注意：堆的删除一定删除的是堆顶元素。具体如下：

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

下面是堆的删除操作代码实现：

public void deleteTop() {
  // 将堆顶元素与堆中最后一个元素交换
  array[0] = array[size - 1];
 
  // 堆中有效数据个数减少一个
  size--;
 
  // 对堆顶元素进行向下调整
  int parent = 0; // 当前节点的索引
 
  // 持续向下调整，直到满足堆的性质
  while (true) {
    // 左孩子节点的索引
    int leftChild = parent * 2 + 1;
    // 右孩子节点的索引
    int rightChild = leftChild + 1;
 
    // 父节点与左右孩子节点中值最大的节点进行交换
    int maxChild = parent; // 最大值节点的索引
 
    // 如果左孩子存在且大于父节点，则更新最大值节点
    if (leftChild < size && array[leftChild] > array[maxChild]) {
      maxChild = leftChild;
    }
 
    // 如果右孩子存在且大于当前最大值节点，则更新最大值节点
    if (rightChild < size && array[rightChild] > array[maxChild]) {
      maxChild = rightChild;
    }
 
    // 如果最大值节点是当前节点本身，则调整结束 
    if (maxChild == parent) {
      break;
    } else {
      // 交换最大节点与父节点
      int temp = array[parent];
      array[parent] = array[maxChild];
      array[maxChild] = temp;
 
      // 更新当前节点为最大值节点
      parent = maxChild;
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

二：优先级队列

2.1 概念

前面介绍过队列，队列是一种先进先出 (FIFO) 的数据结构.

但有些情况下，操作的数据可能带有优先级，出队列时，可能需要优先级高的元素先出队列，此时使用队列显然不合适，比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话；初中那会班主任排座位时可能会让成绩好的同学先挑座位。

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

2.2 堆的使用

Java 集合框架中提供了 PriorityQueue 和 PriorityBlockingQueue 两种类型的优先级队列，PriorityQueue 是线程不安全的，PriorityBlockingQueue 是线程安全的，本文主要介绍 PriorityQueue。

关于 PriorityQueue 的使用要注意：

1. 使用时必须导入 PriorityQueue 所在的包
2. PriorityQueue 中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出 ClassCastException 异常
3. 不能插入 null 对象，否则会抛出 NullPointerException
4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
5. PriorityQueue 底层使用了堆数据结构
6. PriorityQueue 默认情况下是小堆—即每次获取到的元素都是最小的元素

PriorityQueue 中常见的构造方法：

下面是使用示例：

static void TestPriorityQueue(){
    // 创建一个空的优先级队列，底层默认容量是11
    PriorityQueue<Integer> q1 = new PriorityQueue<>();
    
    // 创建一个空的优先级队列，底层的容量为initialCapacity
    PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
    ArrayList<Integer> list = new ArrayList<>();
    list.add(4);
    list.add(3);
    list.add(2);
    list.add(1);
    
    // 用ArrayList对象来构造一个优先级队列的对象
    // q3中已经包含了三个元素
    PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
    System.out.println(q3.size());//4
    System.out.println(q3.peek());//1
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

// 用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即可
class IntCmp implements Comparator<Integer>{
  @Override
  public int compare(Integer o1, Integer o2) { // 比较器
    return o2-o1;
 }
}
public class TestPriorityQueue {
  public static void main(String[] args) {
    PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());
    p.offer(4);
    p.offer(3);
    p.offer(2);
    p.offer(1);
    p.offer(5);
    System.out.println(p.peek());
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

下面是 PriorityQueue 中常用的方法：

下面是这些方法的使用示例：

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        
        // 测试插入元素
        heap.offer(10); // 返回 true
        heap.offer(5); // 返回 true
        heap.offer(15); // 返回 true
        heap.offer(2); // 返回 true
        
        // 测试获取优先级最高的元素
        // 结果为 2
        System.out.println(heap.peek());
        
        // 测试移除优先级最高的元素
        // 结果为 2
        System.out.println(heap.poll());
        
        // 测试获取有效元素的个数
        // 结果为 3
        System.out.println(heap.size());
        
        // 测试清空优先级队列
        heap.clear();
        
        // 测试检测优先级队列是否为空
        // 结果为 true
        System.out.println(heap.isEmpty());
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

以下是 JDK 1.8 中，PriorityQueue 的扩容方式：

• 如果容量小于 64 时，是按照 oldCapacity 的 2 倍方式扩容的
• 如果容量大于等于 64，是按照 oldCapacity 的 1.5 倍方式扩容的
• 如果容量超过 MAX_ARRAY_SIZE，按照 MAX_ARRAY_SIZE 来进行扩容

MAX_ARRAY_SIZE 等于 Integer.MAX_VALUE - 8，等于 2,147,483,639。

2.3 用堆模拟实现优先级队列

我们通过堆可以模拟实现优先级队列，因为堆具有以下特性：

1. 大堆或小堆：大堆意味着父节点的值大于或等于其子节点的值，而小堆意味着父节点的值小于或等于其子节点的值。
2. 优先级定义：优先级可以根据堆的层次来确定。

优先性在优先级队列中体现在以下方面：

1. 插入元素：由于堆的性质，插入的元素会按照其优先级找到正确的位置插入。较高优先级的元素会被放置在堆的顶部（根节点）。
2. 删除元素：从堆中删除元素时，会删除具有最高（最大堆）或最低（最小堆）优先级的元素。这样，每次删除的元素都是具有最高/最低优先级的元素。

通过以上方式，可以使用堆来实现优先级队列，确保具有更高优先级的元素优先被处理或删除，下面我们基于堆来模拟实现一个优先级队列：

public class MyPriorityQueue {
  // 演示作用，不再考虑扩容部分的代码
  private int[] array = new int[100];  // 使用数组来存储元素
  private int size = 0;  // 当前队列的大小

  // 向优先队列中插入元素
  public void offer(int e) {
    array[size++] = e;  // 将元素插入数组末尾
    shiftUp(size - 1);  // 对插入的元素进行上浮操作，以保持堆的性质
  }

  // 弹出并返回优先队列中最高优先级的元素
  public int poll() {
    int oldValue = array[0];  // 保存堆顶元素的值
    array[0] = array[--size];  // 将堆尾元素移到堆顶
    shiftDown(0);  // 对堆顶元素进行下沉操作，以保持堆的性质
    return oldValue;  // 返回弹出的元素值
  }

  // 返回优先队列中最高优先级的元素
  public int peek() {
    return array[0];  // 直接返回堆顶元素的值
  }
}

  //扩容代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

三： 堆的应用

3.1 堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆

升序：建大堆
降序：建小堆

2. 利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

3.2 Top-k 问题

TOP-K 问题：即求数据集合中前 K 个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前 10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等 , 我们可以通过使用堆来解决 TOP-K 问题，具体步骤如下：

• 创建一个大小为 K 的最小堆（或最大堆，取决于你是求前K个最小值还是最大值）。
• 如果堆的大小小于K，将当前元素插入堆中。
• 如果堆的大小等于K，比较当前元素与堆顶元素的大小
• 如果当前元素大于堆顶元素（最小堆），将堆顶元素弹出，将当前元素插入堆中。
• 如果当前元素小于堆顶元素（最大堆），跳过当前元素。
• 遍历完数据集合后，堆中的元素即为前K个最小（或最大）的元素。

下面是一个使用 Java 实现堆解决 TOP-K 问题的示例代码：

import java.util.PriorityQueue;

public class TopK {
    public static void main(String[] args) {
        int[] nums = {9, 3, 7, 5, 1, 8, 2, 6, 4};
        int k = 4;

        findTopK(nums, k);
    }

    private static void findTopK(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : nums) {
            if (minHeap.size() < k) {
                minHeap.offer(num);
            } else if (num > minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(num);
            }
        }

        System.out.println("Top " + k + " elements:");
        while (!minHeap.isEmpty()) {
            System.out.print(minHeap.poll() + " ");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

以上示例中，对数组 nums 求前4个最小元素，使用了 PriorityQueue 实现了一个小顶堆。遍历数组时，根据堆的大小和当前元素与堆顶元素的比较进行插入和调整。最后，打印出堆中的元素即为前 4 个最小的元素。

四：java 对象的比较

4. 1 PriorityQueue 中插入对象

优先级队列在插入元素时有个要求：插入的元素不能是 null 或者元素之间必须要能够进行比较，为了简单起见，我们只是插入了 Integer 类型，那优先级队列中能否插入自定义类型对象呢？

class Card {
  public int rank; // 数值
  public String suit; // 花色
  
  public Card(int rank, String suit) {
    this.rank = rank;
    this.suit = suit;
 }
}
public class TestPriorityQueue {
  public static void TestPriorityQueue()
 {
    PriorityQueue<Card> p = new PriorityQueue<>();
    p.offer(new Card(1, "♠"));
    p.offer(new Card(2, "♠"));
 }
  public static void main(String[] args) {
    TestPriorityQueue();
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

优先级队列底层使用堆，而向堆中插入元素时，为了满足堆的性质，必须要进行元素的比较，而此时 Card 是没有办法直接进行比较的，因此抛出异常。

因为 Card 是引用类型，所以当我们需要比较他们的时候，需要重写 equals 方法，通过这个方法来告诉程序比较的规则是什么。