博客

1. 优先级队列

1.1 概念

队列是一种先进先出的数据结构，有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要

优先级高的元素先出列

，该中场景下，使用队列显然不合适，比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话。

这种情况下，数据结构因该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。而这种数据结构，就叫做

优先级队列(Priority Queue)

。

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


JDK1.8

中的

PriorityQueue

底层使用了堆这种数据结构，而堆实际就是在

完全二叉树

的基础上进行了一些调整。

2.1 堆的概念

如果有一个

关键码的集合K = {k

₀

，k

₁

，k

₂

，…，k

_n-1

}

，把它的所有元素

按完全二叉树的顺序存储方式存储在一个

一维数组

中

，并满足：

K

_i

<= K

_2*i+1

且 K

_i

<= K

_2*i+2


(或K

_i

>= K

_2*i+1

且 K

_i

>= K

_2*i+2

) i =

0

，1，2…，则

称为小堆

(或大堆)。根结点最大的堆叫做最大堆或者大根堆，根结点最小的堆叫做最小堆或小根堆。

解释：这里的K

_2*i+1

是K

_i

的左孩子，K

_2*i+2

是K

_i

的右孩子

堆的性质

：

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

数组中存储的就是完全二叉树

层序遍历

的结果

2.2 堆的存储方式

从堆的概念可知，

堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储

.

注意：对于



非完全二叉树

，则

不适合

使用

顺序

方式进行存储**，因为为了能够还原二叉树，

空间中必须要存储空节点，就会导致

空间利用率比较低


。

非完全二叉树建议采用链式存储

的方式进行存储。

2.3 堆的创建

2.3.1堆的向下调整

向下调整：从子树的根节点向下比较

我们来看这个数组

27,15,19,18,28,34,65,49,25,37

,如何将它变成大根堆？

先将它转化成为完全二叉树

我们从下面开始向上调整:37 > 28,change;49 > 25 > 18,change;65 > 34 > 19,change;

再次调整:65 > 15 > 27,change;49 > 37 > 27,change

再次调整:25 > 18 > 15,change;34 > 27 > 19,change

此时，就变成了大根堆。那么我们来思考以下三个问题：

1. 怎么确定最后一刻子树的位置？
2. 怎么从一棵子树调整完之后调整下一棵？
3. 怎么确定当前这棵树已经调整完了？

• 通过下标p来确定：length – 1是最后一个节点的位置，通过它来找父亲节点:(length – 1 – 1) / 2 ,该下标的结点就是最后一棵子树的根节点。

• p– 就可以找到其他子树的根节点

• 当根节点的孩子结点（实则它没有孩子结点）下标超出了length – 1，证明不用向下调整了。

  

拿这个为例，当p遍历到

5

下标时，它的左孩子结点下标child = 2 * p + 1 = 11，超过9，证明

5

这棵树不用再向下调整了

private int[] elem;
private int usedSize;
public Heap() {
    this.elem = new int[10];
}
//创建一个大根堆
public void createHeap(int[] arr) {
    //把原始数据给到了elem数组
    for (int i = 0; i < arr.length; i++) {
        elem[i] = arr[i];
        usedSize++;
    }
    for(int p = (usedSize - 1 - 1) / 2; p >= 0; p--) {
        //usedSize - 1 是最后元素的下标
        //(usedSize - 1 - 1) / 2 这里是找到最后一个元素的父亲节点，找到了最后一课子树，从最后一棵子树开始，向下调整。
        shiftDown(p, usedSize);
    }
}
/**
 * 向下调整
 * @param p 每棵子树的根节点
 * @param e 每棵子树调整的结束位置
 */
private void shiftDown(int p, int e) {
    int child = 2 * p + 1;//左孩子
    while(child < e) {//判断一定有左孩子
        if(child + 1 < e && elem[child] < elem[child + 1]) {
            //如果有右孩子并且右孩子的val比左孩子大，才有必要变child，为的就是让child永远指向两个孩子中val最大的那一个
            child += 1;
        }
        //最大值与父结点进行比较
        if(elem[child] > elem[p]) {
            //如果孩子的值比父结点的值大，交换
            int tmp = elem[child];
            elem[child] = elem[p];
            elem[p] = tmp;
            //交换之后，向下调整，看看交换之后的子树是否还满足大根堆
            p = child;
            child = 2 * p + 1;
        } else {
        	break;
        }
    }
}

2.3.2 建堆的时间复杂度

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

所以，建堆时间复杂度为

O(n)

堆的插入和删除

插入操作

插入元素的时候也要保证这个堆是大根堆或者小根堆。

可以将元素加到最后，然后通过

向上调整

，让这个堆依然是大根堆或者小根堆。

public void push(int val) {
    //check fill
    //如果满了就扩容
    if(usedSize == elem.length) {
        elem = Arrays.copyOf(elem, 2 * usedSize);
    }
    elem[usedSize] = val;//将这个元素放在数组的最后
    usedSize++;
    shiftUp(usedSize - 1);
}
public void shiftUp(int child) {
    int p = (child - 1) / 2;
    //通过下标找到新加元素的父亲节点，然后开始向上调整
    while(child > 0) {
        //当child遍历到下标为0的元素的时候，就没有父结点了，跳出循环。
        //这里就只用和父亲节点进行比较，不用和兄弟结点比较，因为这个堆插入元素之前就已经是有序的了，父亲节点一定会比另一个孩子节点大。
        if(elem[child] > elem[p]) {
            int tmp = elem[child];
            elem[child] = elem[p];
            elem[p] = tmp;
            child = p;
            p = (child - 1) / 2;
        } else {
            //如果当前孩子小于父亲，那么以后的结点也不用再比较了，因为此时没有发生交换，上面的树仍然保持着插入之前的顺序，依然是大根堆。所以直接返回就行。
            return;
        }
    }
}

时间复杂度为

log(N)

删除操作

删除元素只能删除堆顶，删除的方法就是：

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

public void poll() {
    if(usedSize == 0) {
        System.out.println("优先级队列为空");
        return;
    }
    //交换
    int tmp = elem[0];
    elem[0] = elem[usedSize - 1];
    elem[usedSize - 1] = tmp;
    usedSize--;//个数减一
    shiftDown(0, usedSize);//只需要向下调整0下标这一棵树
}
private void shiftDown(int p, int e) {
    int child = 2 * p + 1;
    while(child < e) {
        if(child + 1 < e && elem[child] < elem[child + 1]) {
            child += 1;
        }
        if(elem[child] > elem[p]) {
            int tmp = elem[child];
            elem[child] = elem[p];
            elem[p] = tmp;
            p = child;
            child = 2 * p + 1;
        }
    }
}

时间复杂度也为

O(N)

获得优先级最高的元素

public boolean isEmpty() {
    return usedSize == 0;
}
public int peek() throws HeapEmptyException{
    if(isEmpty()) {
        //抛异常
        throw new HeapEmptyException("empty");
    }
    return elem[0];
}

2.常用接口

2.1

PriorityQueue

的特性

Java集合框架中提供了**

PriorityQueue


和


PriorityBlockingQueue


两种类型的优先级队列，


PriorityQueue

是线程不安全的，

PriorityBlockingQueue

是线程安全的**，本文主要介绍

PriorityQueue

。

关于

PriorityQueue

的使用要注意：

1. 使用时必须导入
   
PriorityQueue

   所在的包，即:


import java.util.PriorityQueue;


2. 
PriorityQueue

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

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

   
4. 
   没有容量限制，可以插入任意多个元素，其内部可以自动扩容
   
5. 
   插入和删除元素的时间复杂度为O(log
   
   ₂
   
   N)
   
6. 
   
PriorityQueue

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

   默认情况下是小堆
   
   —即每次获取到的元素都是最小的元素

解析2：

因为是将元素放入堆中，一定会经过比较，调整为大根堆或者小根堆，所以插入的对象必须是可比较的。

2.2

PriorityQueue

常用接口介绍

1. 优先级队列的构造

public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
    //DEFAULT_INITIAL_CAPACITY = 11
}
//创建一个空的优先级队列，默认容量是11

public PriorityQueue(int initialCapacity) {
    this(initialCapacity, null);
}
//创建一个初始容量为initialCapacity的优先级队列，注意：initialCapacity不能小于1，否则会IllegalArgumentException异常

public PriorityQueue(Comparator<? super E> comparator) {
    this(DEFAULT_INITIAL_CAPACITY, comparator);
}
//用一个集合来创建优先级队列

public static void main() {
    PriorityQueue<Integer> q1 = new PriorityQueue<>();
    
    PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
    
    ArrayList<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(3);
    list.add(2);
    PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
    System.out.println(q3.peek());//1
}

注意：默认情况下，PriorityQueue队列是

小堆

，如果需要大堆,需要用户提供比较器.这部分内容在我的另一篇文章

java对象比较

中进行了详细的介绍，这里不再赘述。

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

注意

：

一般在创建优先级队列对象时，如果知道元素个数，建议就直接将底层容量给好 ，否则在插入时需要不多的扩容。

扩容机制：开辟更大的空间，拷贝元素，这样效率会比较低

以下是JDK 1.8中，PriorityQueue的扩容方式：

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1));
    // overflow-conscious code
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
    }
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
    throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
    Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

• 如果容量小于64时，是按照oldCapacity的2倍方式扩容的
• 如果容量大于等于64，是按照oldCapacity的1.5倍方式扩容的
• 如果容量超过
  
MAX_ARRAY_SIZE

  ，按照
  
Integer.MAX_VALUE

  来进行扩容

2.3 练习

最小K个数

运用最小堆的思想，我们不难想出，可以把数组的元素存入堆中，然后弹出k个堆顶元素，这就是最小的k个数字了

class Solution {
    public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int n : arr) {
            queue.offer(n);
        }
        int[] ret = new int[k];
        for(int i = 0; i < k; i++) {
            ret[i] = queue.poll();
        }
        return ret;
    }
}

但是这样并不是最优的解法，他的时间复杂度比较高

建堆复杂度为O(n),删除元素复杂度为O(k*log(n))。

那我们就换种思路，这里要求出的是前k个最小元素，我们可以

建立一个k大小的大根堆

，为什么要建大根堆呢？

因为大根堆可以保证这k个元素里的最大值在堆顶，然后再将剩下的n-k个元素与堆顶元素进行比较，如果小于堆顶元素，就将堆顶元素删除，将该元素入堆。

代码实现

class imp implements Comparator<Integer>{
    @Override
    public int compare(Integer n1, Integer n2) {
        return n2 - n1;
    }
}
class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] ans = new int[k];
        if(k == 0) {
            return ans;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>(k, new imp());
        for(int i = 0; i < k; i++) {
            queue.offer(arr[i]);
        }
        for(int i = k; i < arr.length; i++) {
            int top = queue.peek();
            if(top > arr[i]) {
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        for(int i = 0; i < k; i++) {
            ans[i] = queue.poll();
        }
        return ans;
    }
}

分析

：

1. 堆的大小是k
2. 遍历n个元素
3. 极端情况下，从第k + 1个元素开始，每个元素都要进行调整

时间复杂度：O(n + (n – k) * log(k)) ≈

O(n)

3. 堆的应用

3.1 PriorityQueue的实现

用堆作为底层结构封装优先级队列

3.2 堆排序

给你一组数据：[27, 15, 19, 18, 28, 34, 65, 49, 25, 37]，如果利用堆将他们从小到大进行排序，我们该怎么排？

肯定会有人想到，建立一个小根堆不就好了，但是，小根堆只能保证结点数值比左右两边小，不能确定左右两边的大小关系，所以简单的建堆肯定是不能的。

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

1. 
   建堆
   

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

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

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

public static void heapSort(int[] arr) {
    createBigHeat(arr);
    int end = arr.length - 1;
    while (end > 0) {
        //让堆顶元素与最后一个元素进行交换，因为堆顶元素是最大的元素，将它放在最后一个，就让最大的元素有序了
        swap(arr, 0, end);
        //只有0下标这棵树不符合大根堆，所以只需对0下标这一颗树进行向下调整就行
        siftDown(arr, 0, end);
        end--;
    }
}
private static void createBigHeat(int[] arr) {
    for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
        siftDown(arr, i, arr.length);
    }
}
private static void siftDown(int[] arr, int parent, int len) {
    int child = parent * 2 + 1;
    while(child < len) {
        if(child + 1 < len && arr[child] < arr[child + 1]) {
            child++;
        }
        if(arr[child] > arr[parent]) {
            swap(arr, child, parent);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

3.3 Top-k问题

TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 
   用数据集合中前K个元素来建堆
   

   • 前k个最大的元素，则建小堆
   • 前k个最小的元素，则建大堆

2. 
   用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
   

   将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

拓展一下

如果要求第k小的元素，该怎么求呢？

不难得出，大小为k的大根堆的

堆顶元素

其实就是第k小的元素。