优先级队列（堆）详解

优先级队列（堆）详解

目录

• 堆的概念
• 堆的存储方式
• 堆的基本操作
• 优先级队列模拟实现
• PriorityQueue接口介绍
• 堆排序
• Top-k问题

1、堆的概念

如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
从堆的概念中不难看出，堆实际上是一个特殊的完全二叉树。必须满足的条件是：对于每一个根结点都小于它的孩子结点（小堆）或者每一个根节点都大于孩子结点（大堆）。
如下图：

2、堆的存储方式

堆是一颗完全二叉树，可以按照层序的规则采用顺序的方式进行存储。（对于非完全二叉树，在存储过程中会存储空结点，浪费空间）
将元素存储到数组中后，可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标，则有：
如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2
如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子
如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子

3、堆的基本操作

1、向下调整

在讲堆的建立之前，我们要了解一个非常重要的操作：向下调整。
我们以建小根堆为例，给定这样一个完全二叉树：

我们要把它变成一个小根堆，就要使用到向下调整的方法，对于小根堆我们要保证每一个根结点都小于它的叶子结点（如果有叶子结点）。步骤如下：

1. 先从最初的根结点开始，记为parent结点，找到其左孩子结点（数组下标2*parent+1）。
2. 判断有没有右孩子结点，如果存在找到左右孩子中最小的孩子，让child进行标记。
3. 将parent与较小的孩子child比较，如果：parent小于较小的孩子child，调整结束。
   否则：交换parent与较小的孩子child，交换完成之后，parent中大的元素向下移动，可能导致子树不满足对的性质，因此需要继续向下调整，即parent = child，child = parent*2+1。 然后重复这个过程。直到parent超出数组下标。
   下图是向下调整的过程：
   向下调整的过程也是对于这颗树进行迭代比较而实现的。仔细思考一下，我们发现向下调整的过程其实只影响改变了一条路径，每次遇到孩子结点都有两种情况：1、parent结点不需要和child结点互换，调整直接结束。2、parent结点需要和child结点互换，将child结点作为parent结点继续调整。不需要调整的部分原来就是符合堆的定义，我们只是在这条路径上将最顶部的元素下调至相应位置，这才是parent可以一条路走到黑的根本原因。接下来，我们来看代码（十分巧妙）：

  public void shiftDown(int[] array, int parent) {
        int child = 2*parent+1;//左孩子结点
        while(child<array.length) {
            if(child+1< array.length&&array[child]<array[child+1]) {
            //先判断右孩子存不存在，再找出两个孩子中的较大孩子
                child+=1;//child指向较大的孩子结点
            }
            if(array[parent]>array[child]) {//比最大的孩子还大，向下调整
                swap(array,parent,child);
            }else{
                break;
            }
            parent = child;//继续向下调整
            child = 2*parent+1;
        }

注意：在调整以parent为根的二叉树时，必须要满足parent的左子树和右子树已经是堆了才可以向下调整。

2、堆的创建

对于一个普通序列：根节点的左右子树不满足堆的特性，我们又该如何调整呢？
答案仍然是利用向下调整，只不过我们要从下向上考虑。步骤如下：

1. 从后向前，找到第一个不为叶子结点的结点，记为root。
2. 从这个根结点向前遍历数组（root–），每遇到一个结点就向下调整一次，直到走完数组（root<0）。
   直接上代码：

  public static void createHeap(int[] array) {
        int root = (array.length-1-1)/2;//根据孩子结点求根结点
        for(;root>=0;root--) {
            shiftDown(array,root);
        }
    }

3、堆的插入

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

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

这时，我们所做的实际上是一种向上调整。仍然以小根堆为例，下面是代码实现：

public static void shiftUp(int[] array,int child) {
        int parent = (child-1)/2;
        while(child>0) {
            if(array[parent]>array[child]) {
                swap(array,parent,child);
            }else{
                break;
            }
            child = parent;
            parent = (child-1)/2;
        }
    }

比较向上调整与向下调整：
1、向上调整是通过child结点去找parent结点，而向下调整是通过parent结点去找child结点。
2、建堆的时候使用向下调整，而不使用向上调整。因为向下调整操作的复杂度较低。

4、堆的删除

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

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

4、优先级队列模拟实现

前面介绍过队列，队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，
在这种情况下，数据结构应该提供两个最基本的操作：一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。
我们接下来使用堆的操作模拟实现优先级队列，直接上代码：

import java.util.Arrays;

public class PriorityQueue {
    public int[] array;
    public int usedSize;
    public static final int default_Capacity = 10;//默认容量

    public PriorityQueue() {
        this.usedSize = 0;
        this.array = new int[default_Capacity];
    }

    /**
     *
     * @param array
     */
    public void createHeap(int[] array) {
        int parent = (array.length-2)/2;
        for(;parent>=0;parent--) {
            shiftDown(parent,usedSize);
        }
    }

    public static void swap (int[] array,int parent,int child) {
        int tmp = array[parent];
        array[parent] = array[child];
        array[child] = tmp;
    }
    /**
     *
     * @param parent 是每棵子树的根节点的下标
     * @param len  是每棵子树调整结束的结束条件
     * 向下调整的时间复杂度：O(logn)
     */
    private void shiftDown(int parent,int len) {
        int child = 2*parent+1;
        while(child<len) {
            if(child+1<len&&array[child]<array[child+1]) {
                child+=1;//child指向较大的孩子结点
            }
            if(array[parent]>array[child]) {
                swap(array,parent,child);
            }else{
                break;
            }
            parent = child;
            child = 2*parent+1;
        }
    }


    /**
     * 入队：仍然要保持是大根堆
     * @param val
     */
    public void push(int val) {
        if(isFull()) {
            array = Arrays.copyOf(array,2*array.length);
        }
        array[usedSize] = val;
        usedSize++;
        shiftUp(usedSize-1);
    }

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

    public boolean isFull() {
        return usedSize == array.length;
    }

    /**
     * 出队【删除】：每次删除的都是优先级高的元素
     * 仍然要保持是大根堆
     */
    public int pollHeap() {
        int tmp = array[0];
        swap(array,0,usedSize-1);
        usedSize--;
        shiftDown(0,usedSize);
        return tmp;
    }

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

    /**
     * 获取堆顶元素
     * @return
     */
    public int peekHeap() {
        return array[0];
    }
}

5、PriorityQueue接口介绍

三种构造器：

• PriorityQueue() 创建一个空的优先级队列，默认容量是11
• PriorityQueue(int initialCapacity)创建一个初始容量为initialCapacity的优先级队列，注意：
  initialCapacity不能小于1，否则会抛IllegalArgumentException异常
• PriorityQueue(Collection<?extends E> c) 用一个集合来创建优先级队列

常用方法：

• booleanoffer(E e)插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，时间复杂度为O（log2N） ，注意：空间不够时候会进行扩容
• E peek() 获取优先级最高的元素，如果优先级队列为空，返回null
• E poll() 移除优先级最高的元素并返回，如果优先级队列为空，返回null
• int size() 获取有效元素的个数
• void clear() 清空队列
• boolean isEmpty() 检测优先级队列是否为空，空返回true

6、堆排序

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

1. 建堆
   升序：建大堆
   降序：建小堆
2. 利用堆删除思想来进行排序
   建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

   public void heapSort() {
        int end = usedSize-1;
        while (end > 0) {
            swap(0,end);
            siftDown(0,end-1);
            end--;
        }

7、Top-k问题（堆排序的应用）

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

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

//使用比较器创建小根堆
class LessIntComp implements Comparator<Integer> { 
	@Override
	public int compare(Integer o1, Integer o2) { return o1 - o2; }
 }
//使用比较器创建大根堆
class GreaterIntComp implements Comparator<Integer>{ 
	@Override
	public int compare(Integer o1, Integer o2) { return o2 - o1; 
	} 
}
public class TestDemo<E> { //求最小的K个数，通过比较器创建大根堆
	public static int[] smallestK(int[] array, int k) { 
	if(k <= 0) { 
		return new int[k]; 
	}
	GreaterIntComp greaterCmp = new GreaterIntComp(); 
	PriorityQueue<Integer> maxHeap = new PriorityQueue<>(greaterCmp); 
	//先将前K个元素，创建大根堆 
	for(int i = 0; i < k; i++) {
		maxHeap.offer(array[i]); 
	}
	//从第K+1个元素开始，每次和堆顶元素比较 
	for (int i = k; i < array.length; i++) { 
	int top = maxHeap.peek(); 
	if(array[i] < top) {
		maxHeap.poll();
		maxHeap.offer(array[i]); 
		} 
	}
	//取出前K个
	int[] ret = new int[k]; 
	for (int i = 0; i < k; i++) { 
		int val = maxHeap.poll(); 
		ret[i] = val;
	}
	return ret; 
}