数据结构 优先级队列(堆)

数据结构 优先级队列(堆)

1. 优先级队列

1.1 概念

在前面的文章里曾介绍过队列，队列是一种先进先出的数据结构，但有些情况下，我们需要操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列

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

2. 优先级队列的模拟实现

JDK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整

2.1 堆的概念

如果有一个关键码的集合K = {k0, k1, k2, … , kn-1},把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：ki<=k2i+1且ki <= k2i+2(ki>=k2i+1 且ki>=k2i+2) i = 0, 1, 2…, 则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

大根堆：根节点大于左右节点

小根堆：根节点小于左右节点

堆的性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树

2.2 堆的存储方式

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

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

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

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

2.3 堆的创建

2.3.1 堆向下调整

对于集合{27, 15, 19, 18, 28, 34, 65, 49, 25, 37} 中的数据，如果想要将它创建成堆又该怎么操作？

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

向下调整(这里我们以小根堆为例):

1. 使用parent标记需要标记的根节点，child标记parent的左孩子(parent如果有孩子一定是先有左孩子)
2. 如果parent的左孩子存在，即：child < size，进行以下操作，直到parent的左孩子不存在：
   • 判断parent右孩子是否存在，存在找到左右孩子中最小的孩子，让child进行标记
   • 将parent与较小的孩子child进行比较，如果：
     • parent小于较小的孩子child，调整结束
     • 否则：交换parent与较小的孩子child，交换完成之后，继续向下调整，即parent = child；child = parent * 2 + 1

代码示例:

public void shiftSmallDown(int parent,int len) {
        //左孩子
        int child = 2 * parent + 1;
        while(child < len) {
            //判断是否存在右孩子 且右孩子和左孩子哪个更小，小的为child
            if (child+1 < len &&  elem[child+1] < elem[child]) {
                child++;
            }
            //判断根节点和child的大小，若根节点小则结束遍历，否则交换两个节点
            if (elem[child] < elem[parent]) {
                swap(child, parent);
                parent = child;
                child = 2 * parent + 1;
            }
            else {
                break;
            }
        }
    }

public void createSmallHeap() {
        for (int parent = (usderSize-1-1)/2;parent >= 0;parent--) {
            shiftSmallDown(parent, usderSize);
        }
    }

public void swap(int x, int y) {
        int temp = elem[x];
        elem[x] = elem[y];
        elem[y] = temp;
    }
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

2.3.2 堆的创建

上述举的例子为特殊情况（即左右子树已经满足堆的特性，只需要修改根节点），那对于普通的序列{1, 5, 3, 8, 7, 6}，即根节点的左右子树不满足堆的特性时，又该如何调整？(这里我们以大根堆为例)

在这里，我们找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，每遇到一个节点，应用向下调整

代码示例:

public void shiftBigDown(int parent,int len) {
        //左孩子
        int child = 2 * parent + 1;
        while(child < len) {
            //判断是否存在右孩子 且右孩子和左孩子哪个更大，大的为child
            if (child+1 < len &&  elem[child+1] > elem[child]) {
                child++;
            }
            //判断根节点和child的大小，若根节点大则结束遍历，否则交换两个节点
            if (elem[child] > elem[parent]) {
                swap(child, parent);
                parent = child;
                child = 2 * parent + 1;
            }
            else {
                break;
            }
        }
    }
public void swap(int x, int y) {
        int temp = elem[x];
        elem[x] = elem[y];
        elem[y] = temp;
    }
public void createBigHeap() {
    //找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，每遇到一个节点，应用向下调整
        for (int parent = (usderSize-1-1)/2;parent >= 0;parent--) {
            shiftBigDown(parent, usderSize);
        }
    }
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

2.3.3 建堆的时间复杂度

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

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

2.4 堆的插入与删除

2.4.1 堆的插入

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

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

代码示例:

public void push(int val) {
        // 满了则扩容
        if (isFull()) {
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usderSize] = val;

        //向上调整
        shiftBigUp(usderSize);
        usderSize++;
    }

    private boolean isFull() {
        return usderSize == elem.length;
    }

    /**
     * 向上调整
     * 这里以大根堆为例
     */
    public void shiftBigUp(int child) {
        int parent = (child - 1)/2;
        while(child > 0) {
            if (elem[parent] < elem[child]) {
                swap(child,parent);
                child = parent;
                parent = (child - 1) / 2;
            }
            else {
                break;
            }
        }
    }
    public void swap(int x, int y) {
        int temp = elem[x];
        elem[x] = elem[y];
        elem[y] = temp;
    }
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

2.4.2 堆的删除

堆删除的一定是堆顶元素，操作方法如下：

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

代码示例:

 /*删除元素*/
public int pop() {
        if (empty()) {
            return -1;
        }
        int oldVal = elem[0];
        swap(0,usderSize-1);
        usderSize--;
        shiftBigDown(0,usderSize);
        return oldVal;
    }
public boolean empty() {
        return usderSize == 0;
    }

public void shiftBigDown(int parent,int len) {
        //左孩子
        int child = 2 * parent + 1;
        while(child < len) {
            //判断是否存在右孩子 且右孩子和左孩子哪个更大，大的为child
            if (child+1 < len &&  elem[child+1] > elem[child]) {
                child++;
            }
            //判断根节点和child的大小，若根节点大则结束遍历，否则交换两个节点
            if (elem[child] > elem[parent]) {
                swap(child, parent);
                parent = child;
                child = 2 * parent + 1;
            }
            else {
                break;
            }
        }
    }
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

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

代码示例:

package demo2;

public class MyPriorityQueue {
    public int[] arr = new int[100];
    public int size = 0;

    public void offer(int e) {
        arr[size] = e;
        shiftBigUp(size);
        size++;
    }

    public int poll() {
        int oldval = arr[0];
        swap(0,size-1);
        size--;
        shiftBigDown(0,size);
        return oldval;
    }

    public int peek() {
        return arr[0];
    }

    public void shiftBigUp(int child) {
        int parent = (child - 1)/2;
        while(child > 0) {
            if (arr[parent] < arr[child]) {
                swap(child,parent);
                child = parent;
                parent = (child - 1) / 2;
            }
            else {
                break;
            }
        }
    }

    public void shiftBigDown(int parent,int len) {
        //左孩子
        int child = 2 * parent + 1;
        while(child < len) {
            //判断是否存在右孩子 且右孩子和左孩子哪个更大，大的为child
            if (child+1 < len &&  arr[child+1] > arr[child]) {
                child++;
            }
            //判断根节点和child的大小，若根节点大则结束遍历，否则交换两个节点
            if (arr[child] > arr[parent]) {
                swap(child, parent);
                parent = child;
                child = 2 * parent + 1;
            }
            else {
                break;
            }
        }
    }

    public void swap(int x, int y) {
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

    public void display() {
        for (int i = 0;i < size;i++) {
            System.out.print(arr[i] + " ");
        }
    }
}
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

3. 常用接口介绍

3.1 PriorityQueue的特性

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

使用PriorityQueue时需要注意:

1. 使用时必须导入PriorityQueue所在的包，即：

   import java.util.PriorityQueue;
   1

2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常

3. 不能插入null对象，否则会抛出NullPointeException

4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容

5. 插入和删除元素的时间复杂度为O(log₂N)

6. PriorityQueue底层使用了堆数据结构

7. PriorityQueue默认情况下是小根堆–即每次获取到的元素都是最小的元素

3.2 PriorityQueue常用接口介绍

3.2.1 优先级队列的构造

package demo3;

import java.util.ArrayList;
import java.util.PriorityQueue;

public class TestPriorityQueue {

    public static void main(String[] args) {

        // 创建一个空的优先级队列，底层默认容量是11
        PriorityQueue<Integer> q1 = new PriorityQueue<>();

        // 创建一个空的优先级队列，底层默认容量是initialCapacity
        PriorityQueue<Integer> q2 = new PriorityQueue<>(100);

        ArrayList<Integer> list = new ArrayList<>();
        list.add(1234);
        list.add(123);
        list.add(12);
        list.add(1);

        // 用ArrayList对象来构造一个优先级队列的对象
        //此时q3中已经包含了三个元素
        PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
        System.out.println(q3);
        System.out.println("size = " + q3.size());
        System.out.println("队头元素为：" + q3.peek());

    }

}
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

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

class IntCmp implements Comparator<Integer> {
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}

//大根堆构建优先级队列
        PriorityQueue<Integer> q4 = new PriorityQueue<>(new IntCmp());
        q4.offer(4);
        q4.offer(3);
        q4.offer(2);
        q4.offer(1);
        q4.offer(5);
        System.out.println(q4);
1
2
3
4
5
6
7
8
9
10
11
12
13
14

此时创建出来的就是一个大根堆

3.2.2 插入/删除/获取优先级最高的元素

package demo3;

import java.util.PriorityQueue;

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

        //如果知道元素个数建议直接给底层容量
        PriorityQueue<Integer> q = new PriorityQueue<>(arr.length); // 注：默认时为小根堆

        //插入元素
        for (int e:arr) {
            q.offer(e);
        }

        System.out.println(q);
        System.out.println(q.peek()); // 获取优先级最高的元素
        System.out.println(q.size()); // 打印优先级队列中有效元素的个数

        //弹出元素
        q.poll();
        System.out.println(q);

        q.offer(0); // 插入元素后优先级会发生改变
        System.out.println(q);

        //清空队列
        q.clear();
        if (q.isEmpty()) {
            System.out.println("优先级队列为空");
        }
        else {
            System.out.println("优先级队列不为空");
        }
    }
}
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

3.3 OJ练习

top-k问题：求最大或者最小的前k个数据

代码示例:

import java.util.PriorityQueue;
class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if (k == 0 || arr == null) {
            return ret;
        }
        PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);
        for (int e:arr) {
            q.offer(e);
        }
        for (int i = 0;i < k;i++) {
            ret[i] = q.poll();
        }
        return ret;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4. 堆的应用

这里我们拓展一下堆排序

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

1. 建堆:

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

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

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

代码示例:

public void heapSort() {
        int end = usderSize - 1;
        while(end > 0) {
            swap(0,end);
            shiftBigDown(0,end-1);
            end--;
        }
    }

public void shiftBigDown(int parent,int len) {
        //左孩子
        int child = 2 * parent + 1;
        while(child < len) {
            //判断是否存在右孩子 且右孩子和左孩子哪个更大，大的为child
            if (child+1 < len &&  elem[child+1] > elem[child]) {
                child++;
            }
            //判断根节点和child的大小，若根节点大则结束遍历，否则交换两个节点
            if (elem[child] > elem[parent]) {
                swap(child, parent);
                parent = child;
                child = 2 * parent + 1;
            }
            else {
                break;
            }
        }
    }
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