[数据结构]优先级队列(最大堆)详解_数据结构介绍优先队列 最大堆

基本性质

优先级队列，也叫二叉堆、堆（不要和内存中的堆区搞混了，不是一个东西，一个是内存区域，一个是数据结构）。

堆的本质上是一种完全二叉树，分为：

• 最小堆（小根堆）：树中每个非叶子结点都不大于其左右孩子结点的值，也就是根节点最小的堆，图（a）。
• 最大堆（大根堆）：树中每个非叶子结点都不小于其左右孩子结点的值，也就是根节点最大的堆，图（b）。

tip:本文之后的部分，均以大根堆为例。

存储方式

堆本质上是一颗完全二叉树，使用数组进行存储，**从a[1] 开始存储，这样对于下标为k 的结点 a[k]来说，其左孩子的下标为 2∗k，右孩子的下标为 2∗k+1。**且不论 k 是奇数还是偶数，其父亲结点（如果有的话）就是 [k/2]。

// 父节点的索引
int parent(int root) {
    return root / 2;
}
// 左孩子的索引
int left(int root) {
    return root * 2;
}

// 右孩子的索引
int right(int root) {
    return root * 2 + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

具体实现

需要实现的api主要如下所示

向上调整swim

假如我们向一个堆中插入一个元素，要使其仍然保持堆的结构。应该怎么办呢？

可以把想要添加的元素放在数组的最后，也就是完全二叉树的最后一个结点的后面，然后进行向上调整（heapinsert）。

向上调整总是把欲调整结点与父亲结点比较，如果权值比父亲结点大，那么就交换其与父亲结点，反复比较，直到到达堆顶或父亲结点的值较大为止。向上调整示意图如下：

最大堆每个节点都比它的两个子节点大，但是在插入元素和删除元素时，难免破坏堆的性质，这就需要通过这两个操作来恢复堆的性质了。

对于最大堆，会破坏堆性质的有有两种情况：

• 如果某个节点 A 比它的子节点（中的一个）小，那么 A 就不配做父节点，应该下去，下面那个更大的节点上来做父节点，这就是对 A 进行下沉。

• 如果某个节点 A 比它的父节点大，那么 A 不应该做子节点，应该把父节点换下来，自己去做父节点，这就是对 A 的上浮。

当然，错位的节点 A 可能要上浮（或下沉）很多次，才能到达正确的位置，恢复堆的性质。所以代码中肯定有一个while循环。

//    上浮第k个元素，以此维护最大堆性质
private void swim(int k) {

    if (k > N) {
        // 不符合要求的输入
        return;
    }
    //  如果浮到了堆顶，就不能再上浮
    while (k > 1 && isLess(parent(k), k)) {
        //   如果第k个元素比上层大，就浮上去
        exchange(parent(k), k);
        k = parent(k);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

向下调整sink

假如我们要删除一个堆中的堆顶元素，要使其仍然保持堆的结构。应该怎么办呢？

移除堆顶元素后，将最后一个元素移动到堆顶，然后对这个元素进行向下调整（heapify），向下调整总是把欲调整结点 KK 与其左右孩子结点比较，如果孩子中存在权值比当前结点 KK 大的，那么就将其中权值最大的那个孩子结点与结点 KK，反复比较，直到到结点 KK 为叶子结点或结点 KK 的值比孩子结点都大为止。向下调整示意图如下：

时间复杂度也是O(logn)

// 下沉第k个元素，以此维护最大堆性质
private void sink(int k) {
    // 如果沉到底，就沉不下去了
    while (left(k) <= N) {
        // 假设左边节点比较大
        int bigger = left(k);

        // 如果右边节点存在，比较一下大小
        if (right(k) <= N && isLess(bigger, right(k))) {
            bigger = right(k);
        }

        // 节点k比两个孩子都大，不用下沉了
        if (isLess(bigger, k)) break;

        // 否则，不符合最大堆的结构，下沉k节点
        exchange(k, bigger);

        k = bigger;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

实现delMax （删除队顶元素）

这个方法是建立在swim和sink上的。

delMax方法先把堆顶元素 A 和堆底最后的元素 B 对调，然后删除 A，最后让 B 下沉到正确位置。

public Key delMax() {
    // 最大堆的堆顶就是最大元素
    Key max = pq[1];
    // 把这个最大元素换到最后，删除之
    exch(1, N);
    pq[N] = null;
    N--;
    // 让 pq[1] 下沉到正确位置
    sink(1);
    return max;
}
1
2
3
4
5
6
7
8
9
10
11

实现insert

这个方法也是建立在swim和sink上的。

insert方法先把要插入的元素添加到堆底的最后，然后让其上浮到正确位置。

public void insert(Key e) {
    N++;
    // 先把新元素加到最后
    pq[N] = e;
    // 然后让它上浮到正确的位置
    swim(N);
}
1
2
3
4
5
6
7

完整代码

一个优先级队列就实现了，插入和删除元素的时间复杂度为 O(logK)。

K为当前二叉堆（优先级队列）中的元素总数。

因为时间复杂度主要花费在sink或者swim上，而不管上浮还是下沉，最多也就树（堆）的高度，也就是 log 级别。

package com.dataSruct;

public class MaxPQ<Key extends Comparable<Key>> {
    // 存储元素的数组
    private Key[] pq;

    // 当前Priority Queue中的元素个数
    private int N = 0;

    public MaxPQ(int cap) {
        // 索引0 不用，所以多分配一个空间
        pq = (Key[]) new Comparable[cap + 1];
    }

    //    返回当前队列中最大元素
    public Key max() {
        return pq[1];
    }

    //    插入元素e
    public void insert(Key e) {
        N++;
        //  先把新元素加到最后
        pq[N] = e;

        // 让其上浮到正确位置
        swim(N);
    }

    //    删除并返回当前队列中最大元素
    public Key delMax() {
        // 最大堆的堆顶就是最大元素
        Key max = pq[1];

        // 把这个最大元素换到最后，删除之
        exchange(1, N);

        pq[N] = null;

        N--;

        // 让pq[1]下沉到正确位置
        sink(1);

        return max;
    }

    //    上浮第k个元素，以此维护最大堆性质
    private void swim(int k) {

        if (k > N) {
            // 不符合要求的输入
            return;
        }
        //  如果浮到了堆顶，就不能再上浮
        while (k > 1 && isLess(parent(k), k)) {
            //   如果第k个元素比上层大，就浮上去
            exchange(parent(k), k);
            k = parent(k);
        }
    }

    // 下沉第k个元素，以此维护最大堆性质
    private void sink(int k) {
        // 如果沉到底，就沉不下去了
        while (left(k) <= N) {
            // 假设左边节点比较大
            int bigger = left(k);

            // 如果右边节点存在，比较一下大小
            if (right(k) <= N && isLess(bigger, right(k))) {
                bigger = right(k);
            }

            // 节点k比两个孩子都大，不用下沉了
            if (isLess(bigger, k)) break;

            // 否则，不符合最大堆的结构，下沉k节点
            exchange(k, bigger);

            k = bigger;
        }
    }

    //    交换数组的两个元素
    private void exchange(int i, int j) {
        Key temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }

    //    比较大小  i是否比j小？
    private boolean isLess(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }


    private int parent(int root) {
        return root / 2;
    }

    private int left(int root) {
        return root * 2;
    }

    private int right(int root) {
        return root * 2 + 1;
    }

    //    获得父节点
    private Key parentNode(int k) {
        return pq[k / 2];
    }

    // 获得左子结点
    private Key leftNode(int k) {
        return k * 2 > N ? pq[k * 2] : null;
    }

    // 获得右节点
    private Key rightNode(int k) {
        return k * 2 + 1 > N ? pq[k * 2 + 1] : null;
    }


}

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

建堆

自顶向下建堆

自顶向下建堆的思想是，从第 i=1个元素开始，对其进行向上调整，始终使前 i 个元素保持堆的结构。时间复杂度 O(nlogn)

// 从一个数组 自顶向下建堆
// 自顶向下建堆的思想是，从第 i=1 个元素开始，对其进行向上调整，始终使前 i 个元素保持堆的结构。时间复杂度 O(nlogn)
public void ArrayToPQ(Key[] a){
    N = a.length;
    pq = a;

    for(int i=1; i <= N; i++){
        // 向上调整 上浮
        swim(i);
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13

自底向上建堆

自底向上建堆的思想是，自底向上建堆的思想是，从底 i=⌊n/2⌋ 个元素开始，对其进行向下调整，始终让后 n−i 个元素保持堆的结构。

// 从一个数组  自底向上建堆
// 自底向上建堆的思想是，从底 i=⌊n/2⌋ 个元素开始，对其进行向下调整，始终让后 n−i 个元素保持堆的结构。
private void ArrayToBPQ{Key []a}{
    N = a.length;
    pq = a;

    int i = n/2;
    for(; i>=1; i--){
        sink(i);
    }
}
1
2
3
4
5
6
7
8
9
10
11

堆排序

堆排序的思想：假设一个大根堆有 n 个元素，每次把第 1 个元素，与第 n 个元素交换，对第一个元素进行向下调整（sink），并使得 n=n−1 ，直到 n=1

// 堆排序 输入乱序数组 输出有序数组  仅供参考
public Key[] heapSort(Key[] arr) {
  // 先自底向上建堆
  ArrayToBPQ(arr);

  // 然后将最大堆变成降序数组
  for (int i = N; i > 1; i++) {
    exchange(1, i);
    sink(i - 1);
  }

  return pq;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

例题

寻找第K大元素

首先用数组的前k个元素构建一个小根堆，然后遍历剩余数组和堆顶比较，如果当前元素大于堆顶，则把当前元素放在堆顶位置，并调整堆（heapify）。遍历结束后，堆顶就是数组的最大k个元素中的最小值，也就是第k大元素。

c++写法如下。

void heapify(int* a, int index, int length) {
	int left = index * 2 + 1;
	while (left <= length) {
		if (left + 1 <= length - 1 && a[left + 1] > a[left])left++;
		if (a[index] > a[left])break;
		swap(a[index], a[left]);
		index = left;
	}
}

void ArrayToBheap(int* a, int length) {
	int i = length / 2 - 1;
	for (; i >= 0; i--) {
		heapify(a, i, length);
	}
}

void FindKMax(int* a, int k, int length) {
	ArrayToBheap(a, k);
	for (int i = k; i < length; i++) {
		if (a[i] > a[0]) a[0] = a[i];
		heapify(a, 0, k);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

java写法如下

import java.util.PriorityQueue;


public class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 小顶堆
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int num : nums) {
            pq.offer(num);
            // 堆中元素多于k个时，就删除堆顶元素 即 删除最小值
            if (pq.size() > k) {
                pq.poll();
            }
        }

        // pq中剩下的是nums中k个最大元素
        // 堆顶是最小的，即第k个大的元素
        return pq.peek();
    }
}

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

时间复杂度O(n)，只是举个例子。

事实上对于这个问题是有更快的做法的，快速排序的思想，时间复杂度 O(logn)

int Search_K(int left, int right, int k) {
	int i = left, j = right;
	int p = rand() % (right - left + 1) + left;
	int sign = a[p];
	swap(a[p], a[i]);
	while (i < j) {
		while (i < j && a[j] >= sign)j--;
		while (i < j && a[i] <= sign)i++;
		swap(a[i], a[j]);
	}
	swap(a[i], a[left]);
	if (i - left + 1 == k)return a[i];
	if (i - left + 1 < k)return Search_K(i + 1, right, k - (i - left + 1));
	else return Search_K(left, i - 1, k);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

堆更多时候，因为它建堆O(n)，调整O(logn)，当需要有序得到某些数据，是要优于排序（O(nlogn)）算法的，而且如果数据规模是动态增加的，那堆就要完全优于排序算法了，