[算法]-优先队列及源码分析+堆排序

有些情景不一定需要元素全部有序，而是需要每次处理键值最大的元素，如手机运行程序，程序有优先级，来电的优先级比游戏程序的优先级高。

这是就适合优先队列数据结构。优先队列的主要操作有 删除最大元素delMax()和插入元素insert()。高效地实现优先队列具有挑战性，我们可以基于二叉堆来实现优先队列。

通过插入一系列元素，然后一个个删除其中最小的元素合一实现排序算法，堆排序就是基于堆的优先队列的实现。

初级实现

数组/链表实现（无序）

用实现栈的方式实现，insert方法就像实现push方法一样将新加入的元素插入到栈顶。delMax的时候需要一段内循环，实现类似选择排序的循环找出最大的元素和栈顶元素交换，然后删除栈顶（pop）。如果用数组而不是链表来实现的话，还可以加入调整数组大小的机制来保证栈不会溢出。

insert复杂度O（1）
delMax复杂度O（N），需要循环栈内元素找到最大并交换位置删除。

数组/链表实现（有序）

和上边的方法类似，用栈实现，排序的过程放到insert()方法中，插入一个元素，像插入排序那样将新元素插入到合适的位置并将后边的元素依次后移，保证栈顶是最大元素，delMax方法就和pop一样了。

insert复杂度O（N）
delMax复杂度O（1）

二叉堆实现

二叉堆的定义

当一颗二叉树的每个节点都大于它的两个字节点时（每个节点都小于它的父节点），被称为堆有序。根节点是堆有序的二叉树的最大节点。

堆有序二叉树的表示如果用指针的话，每个节点需要三个指针，分别指向两个孩子和父节点,但是如果我们使用完全二叉树来表示对有序的话，就会很方便，只用数组而不用指针就可以表示。

二叉堆是一组能够用堆有序的完全二叉树排序的元素

我们不用位置0，从1开始储存元素，位置k的节点的父节点的位置为k/2向下取整，子节点的位置分别为2k，2k+1.

二叉堆的插入和删除最大元素时对数级别的。

堆有序化（上浮swim）

当某个节点的优先级下降了，我们需要由下至上的恢复对的顺序，如堆底加入了一个大节点，需要上浮。

即某节点比父节点大了，这时要和它的父节点交换位置，至此这个位置不一定比它现在的父节点小，所以要一直上溯到合适的位置。

private void swim(int k) { //位置k需要上浮
	while(k>1 && pq[k].compareTo(pq[k/2])>0)
	{
		exchange(pq, k, k/2);
		k = k/2;
	}
}

堆有序化（下沉sink）

当某个节点的优先级上升了，我们需要由上至下的恢复对的顺序，如根加入了一个小节点，需要下沉。

即父节点比两个孩子或其中一个孩子小了，这时要和它的子节点中较大的一个节点交换位置，至此这个位置不一定比它现在的所有子节点大，所以要一直下沉到合适的位置。

private void sink(int k){
	while(2*k<=N){
		int j =2*k;
		if(j<N && less(j,j+1)) j++;
		if(!less(k,j)) break;
		exchange(pq, k, j);
		k=j;
	}
}

插入元素

将新元素加入到数组末尾，上浮到合适位置

删除最大元素

从数组顶部删去最大元素，并将最后一个元素放到顶端，减小堆的大小，并让新的顶端元素下沉到合适位置。

Java PriorityQueue源码

PriorityQueue继承了AbstractQueue类，而AbstractQueue类是实现了Queue接口。

成员变量

//默认大小
private static final int DEFAULT_INITIAL_CAPACITY = 11;

//优先队列数组，存放树节点，基于二叉堆来实现优先队列
transient Object[] queue; // non-private to simplify nested class access

//队列大小
private int size = 0;

构造函数

//创建一个优先队列对象，默认大小为11，队列中的元素按照自然顺序排序。
public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }
    
 //创建一个指定大小的优先队列对象，队列中的元素按照自然顺序排序  
public PriorityQueue(int initialCapacity) {
    this(initialCapacity, null);
}

//创建一个默认大小(11)的优先队列对象，队列中的元素按照指定比较器进行排序。
public PriorityQueue(Comparator<? super E> comparator) {
    this(DEFAULT_INITIAL_CAPACITY, comparator);
}

//根据指定的大小和比较器来创建一个优先队列对象。
public PriorityQueue(int initialCapacity,
                 Comparator<? super E> comparator) {
// Note: This restriction of at least one is not actually needed,
// but continues for 1.5 compatibility
if (initialCapacity < 1)
    throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}

//从已有的collection构造优先队列

主要方法

在队列中加入元素

//在队列中加入元素
 public boolean add(E e) {
    return offer(e);
}

public boolean offer(E e) {
    if (e == null)//加入null，异常
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)//队列满，进行扩容
        grow(i + 1);
    size = i + 1;
    if (i == 0) //若是空队列，插入到位置0
        queue[0] = e;
    else
        siftUp(i, e); //否则上浮，保持有序
    return true;
}

扩容,原大小小于64时翻倍，大于64时1.5倍

private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%，原大小小于64时翻倍，大于64时1.5倍
    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;
}

//

上浮,使用默认比较器或使用指定比较器

private void siftUp(int k, E x) {
     if (comparator != null)
         siftUpUsingComparator(k, x);
     else
         siftUpComparable(k, x);
 }

 @SuppressWarnings("unchecked")
 //默认比较器
 private void siftUpComparable(int k, E x) {
     Comparable<? super E> key = (Comparable<? super E>) x;
     while (k > 0) {
         int parent = (k - 1) >>> 1;  //父节点的位置k/2,忽略符号位右移
         Object e = queue[parent];  
         if (key.compareTo((E) e) >= 0)
             break;
         queue[k] = e;
         k = parent;  
     }
     queue[k] = key;
 }

 @SuppressWarnings("unchecked")
 private void siftUpUsingComparator(int k, E x) {
     while (k > 0) {
         int parent = (k - 1) >>> 1;
         Object e = queue[parent];
         if (comparator.compare(x, (E) e) >= 0)
             break;
         queue[k] = e;
         k = parent;
     }
     queue[k] = x;
 }

删除元素

public E poll() {
    if (size == 0) //如果没有元素，则返回null
        return null;
    int s = --size;
    modCount++;
    E result = (E) queue[0];
    E x = (E) queue[s]; 
    queue[s] = null;
    if (s != 0) //队列中不只有一个元素，用最后一个元素代替根并下沉
        siftDown(0, x);
    return result;
}
    
private void siftDown(int k, E x) {
	if (comparator != null)
	    siftDownUsingComparator(k, x);
	else
	    siftDownComparable(k, x);
}

@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    int half = size >>> 1;        // loop while a non-leaf
    while (k < half) {
        int child = (k << 1) + 1; // assume left child is least
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            c = queue[child = right];
        if (key.compareTo((E) c) <= 0)
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = key;
}


@SuppressWarnings("unchecked")
private void siftDownUsingComparator(int k, E x) {
    int half = size >>> 1; 
    while (k < half) {
        int child = (k << 1) + 1;  //左孩子
        Object c = queue[child];
        int right = child + 1;  //右孩子
        if (right < size &&
            comparator.compare((E) c, (E) queue[right]) > 0)//如果右孩子存在且左孩子比右孩子大
            c = queue[child = right];
        if (comparator.compare(x, (E) c) <= 0)
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = x;
}

堆排序

堆排序分为两个步骤，首先是从最开始混乱的状态构建一个堆有序（非最终有序），构建了有序堆之后利用不断删除堆顶元素来进行排序，删掉的堆顶元素放入到数组中空出的位置。这是个原地排序。

找到N个元素中最大的M个元素

复杂度

排序算法实现：O(NlogN)
调用初级实现的优先队列：O(NM)
调用基于堆实现的优先队列：O(NlogM)