【数据结构】(9) 优先级队列（堆）

一、优先级队列

        优先级队列不同于队列，队列是先进先出，优先级队列是优先级最高的先出。一般有两种操作：返回最高优先级对象，添加一个新对象。

二、堆

2.1、什么是堆

        堆也是一种数据结构，是一棵完全二叉树，该完全二叉树中的所有子树的根都大于其孩子，即大根堆；如果都小于其孩子，就是小根堆。

2.2、堆的存储方式

        由于完全二叉树按层序遍历，节点之间没有空隙，所以存储在顺序表中不会造成空间浪费；并且顺序存储方便访问二叉树中某节点 i 的双亲（(i-1)/2）和孩子（左：2*i+1，右：2*i+2），以便调整堆。因此，堆采用顺序结构存储。

        大根堆示例：

三、优先级队列（堆）的模拟实现

       PriorityQueue 底层是用堆实现的。

3.1、将完全二叉树调整为堆（向下调整）

3.1.1、手动模拟过程

调整下面的完全二叉树为堆。

        从最后一个父节点开始调整（parent=((usedSize-1)-1)/2）：将较大的孩子 child 与父节点比较（没有右孩子不需要比较孩子大小），若 child 更大则于父节点交换。

        调整倒数第 2 棵子树（parent--）。

        调整倒数第 3 棵子树。

        调整倒数第 4 棵子树。

        如果p和c交换了，还要调整其子树（p=c），直到 p 和 c 没有交换为止，或者 c 超过二叉树大小 usedSize 为止。（向下调整）

        重复上述操作，直到调整完 p=0 的树。

3.1.2、代码实现

        向下调整过程，时间复杂度推导：如果某棵子树高为 k，则最多交换 k-1 次，高为 k 的完全二叉树最多有 N=(2^k)-1 个结点，因此 k-1 = (log(N+1)-1)，时间复杂度为 O(logN)。

    /*** 向下调整* 时间复杂度：O(logN)* @param parent 子树根节点的下标* @param size 子树的大小*/private void shiftDown(int parent, int size) {int maxChild = 2*parent+1; // 默认最大孩子为左孩子while(maxChild < size) { // 存在左孩子就继续调整if(maxChild+1 < size && arr[maxChild+1] > arr[maxChild]) { // 存在右孩子且右孩子大于左孩子maxChild++;}if (arr[maxChild] > arr[parent]) { // 最大孩子大于父节点，交换swap(parent, maxChild);parent = maxChild; // 继续调整子树maxChild = 2*parent+1;}else { // 没有交换，结束调整break;}}}

        将完全二叉树调整为堆，时间复杂度推导：

T=1*(h-1)+2^1*(h-2)+……+2^(h-2)*1。

2T=2^1*(h-1)+2^2*(h-2)+……+2^(h-1)*1。

2T-T=T=2^1+2^2+……+2^(h-2)+2^(h-1)-h+1=2^h-1-h=2^log(N+1)-1-log(N+1)=N-log(N+1)

时间复杂度为 O(N)。

    /*** 将一棵完全二叉树调整为大根堆* 时间复杂度：O(N)*/public void shift2Heap() {int initParent = ((usedSize - 1)-1)/2;for (int i = initParent; i >= 0; i--) {shiftDown(i, usedSize);}}

        测试结果：

3.2、堆中插入一个新节点（向上调整）

        另一种创建堆的方法是，每插入一个新节点，就调整二叉树为堆。

3.2.1、手动模拟过程

        在结尾插入新结点80，并从最后一棵子树开始（child=usedSize-1），从下往上调整，直到 parent=0，或者没有交换为止。（向上调整）

        child=parent。

3.2.2、代码实现

        向上调整：

    /*** 向上调整* 时间复杂度：O(logN)* @param child 添加的孩子节点的下标*/private void shiftUp(int child) {int parent = (child-1)/2; // 父节点下标while(parent >= 0 && arr[child] > arr[parent]) { // 父节点存在且孩子大于父节点，交换swap(child, parent);child = parent;parent = (child-1)/2; // 继续向上调整}}

        插入一个新节点：

    /*** 添加元素到堆中* 时间复杂度：O(NlogN)*/public void offer(int val) {if (isFull()) { // 数组已满，扩容arr = Arrays.copyOf(arr, arr.length * 2);}arr[usedSize] = val;usedSize++;shiftUp(usedSize-1); // 向上调整}

        测试：

        如果插入 N 个结点，时间复杂度推导：

T=2*1+2^2*2+……+2^(h-2)*(h-2)+2^(h-1)*(h-1)

2T=2^2+2^3*2+……+2^(h-1)*(h-2)+2^h*(h-1)

2T-T=T=2^h*(h-1)-2^2-2^3-……-2^(h-1)-2=2^h*(h-1)-2*(2^(h-1)-1)

=2^h*(h-1)-2^h+2=2+2^h*(h-2)+2=(N+1)*(log(N+1)-2)+2

时间复杂度为：O(NlogN)

3.3、删除堆顶元素

        步骤：

• 堆顶与堆尾元素交换。
• 删除堆尾元素。
• 对堆从树根开始向下调整。

    public int poll() {if (isEmpty()) {return -1;}int ret = arr[0];arr[0] = arr[usedSize-1];usedSize--;shiftDown(0, usedSize); // 向下调整return ret;}

四、PriorityQueue 的使用

4.1、注意事项

• PriorityQueue 是线程不安全的，PriorityBlockingQueue 是线程安全的。
• PriorityQueue 中放置的元素必须是可比较大小的，否则会抛出异常。
• 不能插入 null，否则会抛出异常。

        而我们之前学习的 LinkList 是可以插入 null 的：

• 默认构建小根堆。

4.2、构造函数的使用

        无参构造器：默认容量 11，默认比较器为空。

        带初始容量参数的构造器：指定初始容量，默认比较器为空。

        用一个集合创建优先级队列：传入某集合对象。

        因为 String 不是 Number 及其子类，所以语法错误。

        Integer 是 Number 的子类，成功调用。

        指定初始容量、比较器的构造函数：

        transient 的作用：让不想被序列化的属性不被序列化，保证信息的隐私，比如密码。序列化就是把对象的信息转成字符串放到磁盘里；反序列化就是把磁盘里的字符串转成对象信息。transient 就让修饰的属性信息的生命周期仅在调用者的内存中，而不会写进磁盘中持久化。

4.3、offer 插入一个元素

        插入一个元素，offer 源码：

        扩容，grow 源码：

        向上调整，shiftUp 源码：

        如果元素是基础类型的包装类，会使用自身重写的 compareTo：

        如果构造函数参数指定了比较器：

4.4、poll 删除堆顶元素

        删除堆顶元素，poll 源码：

        可以看到源码的向下调整的方法，与我们实现的方法大致相同。

五、OJ练习

5.1、top-k 问题：最小的 k 个数

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

• 解法1：用排序算法，从小到大排序，取前 k 个。最快的排序算法时间复杂度 O(NlogN)。
• 解法2：创建小根堆，取 k 次堆顶元素，每次删除堆顶元素后，向下调整。时间复杂度 O(NlogN)。

    /*** 方法1：使用小根堆实现topK小，* 时间复杂度：O(NlogN) + O(k*logN) = O(NlogN)*/public static int[] topK1(int[] arr, int k) {if(k > arr.length) { // k大于数组长度，直接返回数组return arr;}if(k <= 0) { // k小于等于0，返回空数组return new int[0];}// 创建一个小根堆，O(NlogN)PriorityQueue<Integer> pq = new PriorityQueue<>(k);for (int x : arr) {pq.offer(x);}// 取k次堆顶元素，存入数组，O(k*logN)int[] ret = new int[k];for (int i = 0; i < k; i++) {ret[i] = pq.poll();}return ret;}

• 解法三：创建大小为 k 的大根堆，从 k 开始遍历数组，遇到比堆顶（堆中的最大值）小的 x，就删除堆顶，插入 x。效率最高，O(N*logk)。

    /*** 方法2：使用大根堆实现topK小，* 时间复杂度：O(k*logk) + O((N-k)*logk) + O(k*logk) = O(N*logk)*/public static int[] topK2(int[] arr, int k) {if(k > arr.length) { // k大于数组长度，直接返回数组return arr;}if(k <= 0) { // k小于等于0，返回空数组return new int[0];}// 自定义比较器，实现大根堆Comparator<Integer> cmp = new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}};// 创建一个大小为 k 的大根堆，O(k*logk)PriorityQueue<Integer> pq = new PriorityQueue<>(k, cmp);for (int i = 0; i < k; i++) {pq.offer(arr[i]);}// 遍历数组，如果元素小于堆顶元素，替换堆顶元素，并调整堆，O((N-k)logk)for (int i = k; i < arr.length; i++) {if (arr[i] < pq.peek()) {pq.poll();pq.offer(arr[i]);}}// 取出堆中的元素，存入数组，O(k*logk)int[] ret = new int[k];for (int i = 0; i < k; i++) {ret[i] = pq.poll();}return ret;}

5.2、堆排序

将序列从小到大排序：

• 方法1：创建小根堆，每次取堆顶，放入一个新的数组中。

空间复杂度：O(N)，创建了一个新数组存放结果。当数据很多时，浪费内存。

时间复杂度：O(NlogN)。

• 方法2：创建大根堆，执行 N-1 次循环，每次将堆顶最大元素与未排序的堆尾元素交换，交换后对未排序的部分进行调整。

空间复杂度：O(1)

时间复杂度：O(NlogN)

        初始状态：

        第一次交换，并调整：

        第二次交换，并调整：

    // 堆排序public void sort() {for (int i = usedSize-1; i > 0; i--) {// 交换堆顶和最后一个未排序的元素swap(0, i);// 向下调整堆，元素 i-1 已排序shiftDown(0, i-1);}}