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

堆的概念

堆的分类：堆又称为优先队列和优先级队列，顾名思义，其进出堆的方式就是先进先出(FIrst In First Out)，堆可以分为大根堆和小根堆

根据上图，堆的底层实现就是一颗二叉树，且是一颗完全二叉树，但是不一样的地方是，这个完成二叉树有着特定的排列规则，当堆为大根堆时，其顶上根中的值是最大的值，每颗子树同样满足这一特点，左右结点都比根结点的值要小。且可以看出越小的值跟靠近顶上的根节点，但是也不一定，，小根堆相反。

堆的顺序储存

顺序结构是通过数组来实现，顺序结构为了防止造成空间浪费，一般适合完全二叉树，而堆结构其底层就是完全二叉树，所以用数组来储存堆。所以堆在物理物理储存上，是数组，在逻辑上，是一颗完全二叉树，所以遍历二叉树的时候，最好用层序遍历


可以看出完全二叉树用顺序存储，数组相对于非完全二叉树来说，可以充分利用，防空间的浪费，非完全二叉树不能充分利用其空间，顺序储存时，就会造成间隙，没有利用的空间

创建堆结构

    public void createHeap(int[] array){
        //初始化堆中的元素
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }

        for (int p = (usedSize - 1 -1) / 2; p >= 0 ; p-- ) {
            shiftDown(p,usedSize);
        }
    }

    /**
     *
     * @param root 是每棵子树的根节点的下标
     * @param len结束条件
     */
    private void shiftDown(int root,int len){   //向下调整
        int parent = root;
        int child = 2*parent+1;
        while(child < len){
            if(child+1 < len && elem[child] < elem[child+1]){
                child++;
            }

            if(elem[child] > elem[parent]){
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                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
35
36

入队（offer）

   public void push(int val){
        if(isFull()){
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        //放到最后位置
        elem[usedSize] = val;
        //进行向上调整
        shiftUp(usedSize);
        //有效数字加一
        usedSize++;
    }

    public void shiftUp(int child){
        int parent = (child-1) / 2;
        while(child > 0){
            if(elem[child] > elem[parent]){
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child-1) / 2;
            }else{
                break;
            }
        }
    }
    public boolean isFull(){
        return usedSize == elem.length;
    }
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

出堆（poll）

    public void pollHeap(){
        if(isEmpty()){
            System.out.println("优先级队列为空");
            return;
        }
        int tmp = elem[0];
        elem[0] = elem[usedSize - 1];
        elem[usedSize-1] = tmp;
        usedSize--;
        shiftDown(0,usedSize);
    }

    public boolean isEmpty(){
        return usedSize == 0;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

查看堆顶元素

    public int peekHeap(){
        if(isEmpty()){
            System.out.println("优先级队列为空");
            return -1;
        }
        return elem[0];
    }
1
2
3
4
5
6
7

堆的应用

用于解决topk问题

问题：设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]
思路：

• 求最小的k个数，先建大根堆;如果求最大的k个数，先建立小根堆。
• 如果求最小的k个数，这时候需要我们重写Comparator中的compare方法，因为PriorityQueue源码中已经实现了compare方法，且只能建立小根堆。
  注意事项：这里输入的k个数，k的不能为零，否则会报错，这时候需要单独判断零的情况
• 先将数组中的元素放满k个数到堆中，然后用数组中剩下元素与根结点进行比较，如果这个值小于根结点的值，则把它与根节点交换，堆内部就会重写形成一个新的堆，循环走完整个数组，就可以得到最小的k个元素。

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

class Solution {
    public int[] smallestK(int[] arr, int k) {
        if(k == 0){
            return new int[k];
        }
        IntCmp intCmp = new IntCmp();
        PriorityQueue maxHeap = new PriorityQueue<>(k,intCmp);
        for(int i = 0; i < arr.length; i++){
            if(maxHeap.size() < k){
                //说明没放满
                maxHeap.offer(arr[i]);
            }else{
                int top = maxHeap.peek();
                if(arr[i] < top){
                    maxHeap.poll();
                    maxHeap.offer(arr[i]);
                }
            }
        }
        int[] ret = new int[k];
        for(int i = 0; i < k; i++){
            int val = maxHeap.poll();
            ret[i] = val;
        }
        return ret;
    }
}
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

用于排序

//从小到大排序，则建立大根堆
    public void heapSort(){
        int end = usedSize - 1;
        while(end > 0){
            int tmp = elem[0];
            elem[0] = elem[end];
            elem[end] = tmp;
            shiftDown(0,end);
            end--;
        }
    }
1
2
3
4
5
6
7
8
9
10
11