掌握优先级队列：提升效率的关键技巧

优先级队列的概念

队列是一种先进先出的数据结构，但在一些情况下我们要优先处理一些情况，比如：正在手机上打游戏的时候，如果有来电，那么系统就应该处理打进来的电话。
在这种情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。

优先级队列的模拟实现

DK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整。因此我们先来模拟堆的创建，插入与删除。

堆的创建

堆的创建代码：

   //找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点,遇到一个节点就使用向下调整
    public  void  creatHeap(int[] arr){
    int root = (arr.length-2)/2;
        for (; root>=0 ; root--) {
            shiftDown(arr,root);
        }
    }
1
2
3
4
5
6
7

建堆的时间复杂度为O(N)
堆的向下调整代码（以创建大堆代码为例）：

    public void shiftDown(int[] arr, int parent){
        // child先标记parent的左孩子，因为parent可能右左没有右
    int child = parent*2+1;
    int size = arr.length;
    while (child < size){
        // 如果右孩子存在，找到左右孩子中较大的孩子,用child进行标记
        if(child+1 < size && arr[child] < arr[child+1]){
            child++;
        }
        // 如果双亲比其最大的孩子还小，则交换
        if(arr[child]>parent){
            int temp = arr[child];
            arr[child] = arr[parent];
            arr[parent] = temp;
        }else {
            break;
        }
        parent = child;
        child = (parent*2)+1;
    }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

堆的插入与删除

堆的插入

堆的插入总共需要两个步骤：

1. 先将元素放入到底层空间中(注意：空间不够时需要扩容)
2. 将最后新插入的节点向上调整，直到满足堆的性质

public void push(int val) {
      if(isFull()){
          return;
      }
      //usedSize为堆中元素个数
      elem[usedSize]=val;
      usedSize++;
      shiftUp(usedSize-1);
    }


1
2
3
4
5
6
7
8
9
10
11

向上调整：

 private void shiftUp(int child){
        // 找到child的双亲
        int parent = (child-1)/2;
        while (parent >= 0){
            if(arr[parent]>=arr[child]){
                break;
            }else {
                // 将双亲与孩子节点进行交换
                int temp = arr[parent];
                arr[parent] = arr[child];
                arr[child] = temp;
                child = parent;
                parent = (child-1)/2;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

堆的删除

堆的删除一定删除的是堆顶元素。具体如下：

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

 public void pollHeap() {
        if(isEmpty()){
            return;
        }
        elem[0] = elem[usedSize-1];
        usedSize--;
        shiftDown(0,usedSize);
    }
1
2
3
4
5
6
7
8

用堆模拟实现优先级队列

 public class MyPriorityQueue { 
 private int[] array = new int[100];   
 private int size = 0;
 //入队
 public void offer(int e) {
 array[size++] = e;
 //向上调整
 shiftUp(size - 1);
 }
 //出队
 public int poll() {
 int oldValue = array[0];
 array[0] = array[--size];
 //向下调整
 shiftDown(0);
 return oldValue;
 }
 //出堆首元素
 public int peek() {
 return array[0];
 }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

常见接口了解

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的。
关于PriorityQueue的使用要注意：

1. 使用时必须导入PriorityQueue所在的包
2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常
3. 不能插入null对象，否则会抛出NullPointerException
4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
5. 插入和删除元素的时间复杂度为O（logN）
6. PriorityQueue底层使用了堆数据结构
7. PriorityQueue默认情况下是小堆-即每次获取到的元素都是最小的元素

PriorityQueue的几种常见构造方法

我们可以使用优先级队列解决一些问题，例如TOPK问题：最大或者最小的前k个数据。
思路就是我们求最大的前k个数据，我们用数据的前k个数字建一个小堆，然后依次拿堆顶元素与剩下的数据进行比较，如果那个数据大于堆定元素就进行互换，直到遍历完剩下的数据，堆中k个数据就为最大的k个数据。堆顶元素就为第k大元素。
总结思路就是：

1. 用数据集合中前K个元素来建堆
   前k个最大的元素，则建小堆
   前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
   将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。