【数据结构】堆，优先级队列

堆

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

堆的性质

• 堆逻辑结构上是一棵完全二叉树。
• 堆上的节点一定不大于（大根堆）或者不小于（小根堆）父亲节点。

大根堆的模拟实现

使用代码来实现一个大根堆。

接口实现

接口成员方法。

public class PriorityQueue {
    public int[] elem;
    public int usedSize;
    public PriorityQueue() {}
    //建堆
    public void createHeap(int[] array) {}
    /**
     * @param root 是每棵子树的根节点的下标
     * @param len  是每棵子树调整结束的结束条件
     * 向下调整的时间复杂度：O(logn)
     */
    private void shiftDown(int root,int len) {}
    // 入堆：仍然要保持是大根堆
    public void push(int val) {}
    private void shiftUp(int child) {}
    //判断堆是否满
    public boolean isFull() {}
    //每次删除的都是优先级高的元素,删除后任是大根堆
    public void pollHeap() {}
    //判断堆是否为空
    public boolean isEmpty() {}
     // 获取堆顶元素
    public int peekHeap() {}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

构造方法

在构造方法中构建为长度10的数组。

public PriorityQueue() {
        elem = new int[10];
    }
1
2
3

建堆

createHeap思路：

1. 先将数组拷贝进成员数组中（注意看长度是否够）。
2. 我们从最后一棵子树的根节点开始调用shiftDown方法向上一棵一棵树的调整为大根堆。

shiftDown思路：

1. 将当前传入的根节点与他的孩子节点将最大值选出作为根。
2. 然后将根变成孩子节点再次调整。
3. 注意挑选最大值的时候要判断不能让下标越界。

 public void createHeap(int[] array) {
        if(elem.length < array.length){
            elem = Arrays.copyOf(elem, elem.length * 2);
        }
        for (int i = 0; i < array.length; i++){
            elem[i] = array[i];
            usedSize++;
        }
        for (int root = (usedSize -1 -1) / 2; root >= 0 ; root--) {
            shiftDown(root,usedSize);
        }
    }

    /**
     * @param root 是每棵子树的根节点的下标
     * @param len  是每棵子树调整结束的结束条件
     * 向下调整的时间复杂度：O(logn)
     */
    private void shiftDown(int root,int len) {
        int child = root * 2 + 1;
        while (child < len){
            //寻找孩子节点的大值
            if(child + 1 < len && elem[child] < elem[child + 1]){
                child++;
            }
            if(elem[root] < elem[child]){
                swap(elem,root,child);
                root = child;
                child = root * 2 + 1;
            }else {
                break;
            }
        }
    }
    //交换函数
    private void swap(int[] array,int x,int y){
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }
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

入堆

代码思路：

1. 先判断堆是否已经满了，满了要扩容。
2. 在堆最后存入该元素，然后与父亲节点相比较，比父亲节点大就交换，直到到根节点或者比父亲节点小为止。

	 /**
     * 入堆：仍然要保持是大根堆
     * @param val
     */
    public void push(int val) {
        if(isFull()){
            elem = Arrays.copyOf(elem, elem.length*2);
        }
        elem[usedSize] = val;
        shiftUp(usedSize);
        usedSize++;
    }
    private void shiftUp(int child) {
        int parent = (child - 1) / 2;
        while(parent >= 0) {
            if (elem[parent] < elem[child]) {
                swap(elem, parent, child);
                child = parent;
                parent = (child - 1) / 2;
            }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

判满

这个方法直接使用成员变量usedSize和数组长度判断即可。

public boolean isFull() {
        return usedSize == elem.length;
    }
1
2
3

删除

代码思路：

1. 先判断堆是否为空，为空直抛空指针异常。
2. 我们先将堆顶和堆尾交换，然后向下调整一次。
3. useds减1。

ublic void pollHeap() throws NullPointerException {
        if (isEmpty()) {
            throw new NullPointerException();
        }
        swap(elem,0,usedSize-1);
        shiftDown(0,usedSize);
        usedSize--;
    }
1
2
3
4
5
6
7
8

判空

这个方法直接使用成员变量usedSize是否为0就行。

public boolean isEmpty() {
        return usedSize == 0;
    }
1
2
3

获取堆顶元素

如果堆为空，抛空指针异常，没有直接返回堆顶元素。

public int peekHeap() throws NullPointerException {
        if (isEmpty()) {
            throw new NullPointerException();
        }
        return elem[0];
    }
1
2
3
4
5
6

Java中的PriorityQueue

在Java中使用集合类PriorityQueue来表示优先级队列，其底层是一个小根堆。

实现的接口

构造方法

提供了以下3种构造方法：

常用方法

常用方法如下：

PriorityQueue注意事项

1. 使用要导包import java.util.PriorityQueue;
2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常。
3. 不能插入null对象，否则会抛出NullPointerException。
4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容。
5. 如果要将PriorityQueue变成一个大根堆，类实现Comparator后重写 compare方法时将比较改为

public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
1
2
3

练习

最小k个数