数据结构之优先级队列【堆】（Heap）_c语言 优先级队列heapsort

目录

1. 优先级队列（Priority Queue）

2.堆的概念

3.堆的存储方式

4.堆的创建

5.用堆模拟实现优先级队列

 6.PriorityQueue常用接口介绍

6.1 PriorityQueue的特点

6.2 PriorityQueue几种常见的构造方式

7.top-k问题

8.堆排序

---

本篇主要内容总结

（1）优先级队列底层是堆来实现的

（2）堆的本质是完全二叉树  ，堆有大根堆和小根堆

（3）大根堆：根节点最大的堆； 小根堆：根节点最小的堆

（4）堆的创建实现：大根堆为例

大根堆创建：孩子结点和根节点比较交换，核心思想：向下调整   时间复杂度O(n)

堆的插入：插入到最后一个位置，和根结点交换，核心思想：向上调整

堆的删除：只能删除堆顶，然后重新向下调整组成新的大根堆

插入和删除时间复杂度O（log n）

（4）priorityQueue建堆是小根堆，如果要建立大根堆就要写比较器

（5）priorityQueue添加元素，要写明比较的类型才能添加

（6）top-K问题：前K个最大的元素建小根堆；前K个最小的元素建大根堆

第K个最大元素建小根堆 拿栈顶；    第K个最小元素建大根堆 拿栈顶

（7）堆排序：升序：大根堆    降序：小根堆

核心思想：堆元素的删除

---

在说堆的概念之前，先说一下堆的常用方法，从这个方向来写这篇文章

堆的常用方法有

（1）用来构建优先级队列

（2）支持堆排序（大堆或小堆）

（3）top-k问题

---

1. 优先级队列（Priority Queue）

优先级队列 ：是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。

优先级队列相对于普通队列应该提供两个最基本的操作，

（1）返回最高优先级对象（2）添加新的对象

在JDk1.8中的优先级队列底层使用了堆

2.堆的概念

简单的说 ，堆这种数据结构本质上就是一个完全二叉树

并且堆中某个结点的值总是不大于或不小于其父结点的值

小堆：根节点最小的堆，满足Ki <= K2i+1 且 Ki <= K2i+2 

大堆：根节点最大的堆,   满足Ki >= K2i+1 且 Ki >= K2i+2 

3.堆的存储方式

堆是一颗完全二叉树，所以按照层序来看，可以采用顺序数组的存储方式

但是非完全二叉树就不适用于顺序存储了，这是因为非完全二叉树如果有空结点，那顺序存储也要存储这个空节点，这就造成空间上的浪费

i表示孩子结点，父亲结点（i-1）/ 2

i表示根节点 ，左孩子 2 * i + 1    右孩子   2 * i + 2

4.堆的创建

5.用堆模拟实现优先级队列

按照大根堆来创建

先写一个数组，按顺序存储的方式

    public int[] elem;
    public int userSize;//当前堆中有效的元素数据个数
 
    public MyHeap() {
        this.elem = new int[10];
        this.userSize = 0;
    }
 
    public void initArray(int[] array) {
        elem = Arrays.copyOf(array,array.length);
        userSize = elem.length;
    }

(1) 创建堆

先写一个向下调整的方法

  /**
     * @param parent: 每颗子树的根节点下标
     * @param len:每颗子树的结束位置
     * @description 向下调整
     */
    private void shiftDown(int parent,int len) {
        int child = 2*parent+1;//左孩子
        //必须要有左孩子
        while(child < len) {
            //如果一定有右孩子。那就判断 左孩子和右孩子大小，谁大保存谁
            if(child + 1 < userSize && elem[child] < elem[child+1]) {
                child++;
            }
            //交换 比较孩子和根大小交换 然后根节点往下走继续必须
            if (elem[child] > elem[parent]) {
                swap(elem,child,parent);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

再写一个交换根和孩子的方法

    //交换  比较孩子和根大小交换
    private void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

然后通过循环每个结点，向下调整，然后创建好这棵树

    /**
     *建堆：大根堆
     *时间复杂度O(n)
     */
    public void createHeap() {
        for (int parent = (userSize-1-1)/2; parent >= 0 ; parent--) {
            shiftDown(parent,userSize);
        }
    }

分析一下建堆的时间复杂度O(n)

---

 （2）堆的插入

先写一个方法来判断空间满不满

    public boolean isFull() {
        return userSize == elem.length;
    }

再写一个向上调整

 //向上调整
    private void shiftUp(int child) {
        int parent = (child - 1) / 2;
        while(child > 0) {
            if(elem[child] > elem[parent]) {
                swap(elem,child,parent);
                child = parent;
                parent = (child - 1) / 2;
            }else {
                break;
            }
        }
    }

 最后再写堆的插入，如果空间满了就扩容，然后再向上调整，变成新的大根堆

    //堆的插入
    public void offer(int x) {
        if (isFull()) {
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        this.elem[userSize] = x;
        userSize++;
        shiftUp(userSize-1);
    }

 （3）堆的删除（优先级队列删除，只能删除堆顶的元素）

再删除前，先要看堆是不是空的

    public boolean isEmpty() {
        return userSize == 0;
    }

然后再删除堆顶元素

  //堆的删除  只能删除堆顶元素
    public int poll() {
        if (isEmpty()) {
            return -1;
        }
        int old = elem[0];
        //1.交换
        swap(elem,0,userSize-1);
        //2.有效元素个数-1
        userSize--;
        //3.栈顶元素向下调整
        shiftDown(0,userSize);
        return old;
    }

看几个选择题把 

1.已知小根堆为8,15,10,21,34,16,12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较次数是     (C)

A: 1 B: 2 C: 3 D: 4

2.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后，其结果是    ()

A: [3 ， 2 ， 5 ， 7 ， 4 ， 6 ， 8] B: [2 ， 3 ， 5 ， 7 ， 4 ， 6 ， 8]

C: [2 ， 3 ， 4 ， 5 ， 7 ， 8 ， 6] D: [2 ， 3 ， 4 ， 5 ， 6 ， 7 ， 8]

 6.PriorityQueue常用接口介绍

6.1 PriorityQueue的特点

（1）首先最重要的先明白priorityQueue建堆是小根堆

    public static void main(String[] args) {
        //默认是小根堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(45);
        priorityQueue.offer(12);
        priorityQueue.offer(55);
        priorityQueue.offer(66);
        System.out.println(priorityQueue.peek());
    }

可以看到这里打印的是12所以是priorityQueue是小根堆

如果要建堆为大根堆，那就要写比较器Comparator了 

    public static void main(String[] args) {
       PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
           @Override
           public int compare(Integer o1, Integer o2) {
               return o2-o1;
           }
       });
    }

（2） 在priorityQueue使用offer添加元素时，一定要明确比较的规则，然后再添加

如果是直接这样比较的话，offer不知道以什么规则比较然后添加，就会报错。 

    public static void main(String[] args) {
        PriorityQueue<Fruit> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(new Fruit() );
        priorityQueue.offer(new Fruit() );
    }

所以这里必须告诉offer以什么方式比较添加，

比如说这里实现comparable接口

class Fruit implements Comparable<Fruit>{
    public int age;
    //必须告诉priorityQueue.offer 以什么方式比较添加元素
    @Override
    public int compareTo(Fruit o) {
        return this.age - o.age;
    }
}

（3）不能插入null对象，否则会抛出NullPointerException异常

（4）可以插入任意多个元素，会自动扩容，没有容量限制

 

 （5）插入和删除元素的时间复杂度为O(log n),建栈的时间复杂度O（n）

---

6.2 PriorityQueue几种常见的构造方式

（1）PriorityQueue()   初始默认容量为11

（2）PriorityQueue(int initialCapacity)

（3）PriorityQueue(Collection<? extends E> c)

 

（4）PriorityQueue(int initialCapacity, Collection<? super E> comparator

---

7.top-k问题

适用情况，在数据量比较大时，求数据集合中前K个最大的元素或者最小的元素

比如说求很多个元素的前k个最大的元素 

思路1：

（1）将这些元素，全部放进大根堆中，堆顶的元素就是最大的值

（2）然后出k次，就能得到前k个最大的值，并且每出一次都会进行向下调整，变成新的大根堆

 public static void topK1(int[] array, int k) {
        PriorityQueue<Integer> maxPQ = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
 
        for (int i = 0; i < array.length; i++) {
            maxPQ.offer(array[i]);
        }
        for (int i = 0; i < k; i++) {
            int val = maxPQ.poll();
            System.out.println(val);
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] array = {16,15,22,155,89,12,45};
        topK1(array,3);
    }

 

 缺点：数字有多少，这个堆就有多大，时间复杂度是O(n*log n)

 思路2：

（1）求前K个最大的元素，建立大小为K的小根堆

（2）然后用剩下的集合里面的元素轮流和堆顶元素比较，如果剩下集合里面的元素比堆顶的元素大，那就替换掉堆顶的元素

（3）然后向下调整，变成新的小根堆，此时这个堆中的元素就是前K个最大元素

差不多和前面一样的方法，不同的是

（1）求前K个最小的元素，要建立大根堆

（2）比较的时候谁小，就把小的放在堆顶

 力扣链接：   面试题 17.14. 最小K个数 - 力扣（LeetCode）

class Solution {
    public int[] smallestK(int[] arr, int k) {
       int[] ret = new int[k];
        if(k == 0) return ret;
        PriorityQueue<Integer> maxPQ = new PriorityQueue<>(k,new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
 
        for (int i = 0; i < arr.length; i++) {
            if(maxPQ.size() < k) {
                maxPQ.offer(arr[i]);
            }else {
                //获取到堆顶元素
                int top = maxPQ.peek();
                //找前k个最小的
                if(arr[i] < top) {
                    maxPQ.poll();
                    maxPQ.offer(arr[i]);
                }
            }
        }
        for (int i = 0; i < k; i++) {
            ret[i] = maxPQ.poll();
        }
        return ret;
    }
}

（1）前面求前K个最大的元素时，建立的小根堆，按照规则，到最后栈中全部都是前K个最大的元素，然后栈顶就是所要求得的第K大的元素

（2）前面求前K个最小的元素时，建立的大根堆，按照规则，到最后栈中全部都是前K个最小的元素，然后栈顶就是所要求得的第K小的元素

---

8.堆排序

 如果是将堆排成一个升序的，那就建立大根堆，操作如下

    public void heapSort() {
        int end = userSize -1;
        while(end > 0) {
            swap(elem,0,end);
            shiftDown(0,end);
            end--;
        }
    }

如果是将堆排成一个降序的，那就建立小根堆，操作和上面类似

一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为  (C)

A: (11 5 7 2 3 17) B: (11 5 7 2 17 3) C: (17 11 7 2 3 5)

D: (17 11 7 5 3 2) E: (17 7 11 3 5 2) F: (17 7 11 3 2 5)

---