前言
众所周知堆排序就是个二叉堆，其实本质上就是个完全二叉树,我其实是想讲堆排序的，可为什么会和优先队列扯上关系呢，而优先队列又为何和jdk扯上关系呢。看完你就明白的
优先队列
优先队列顾名思义，是带有优先级的队列，普通队列是怎么样的(先进先出),那么优先级队列呢肯定是优先级最大的先出，这有什么好处？
我们可以通过它来得到最大数或者最小数，也能插入数字
映射到现实中来说某一天你跟室友去吃饭，外面有很多家餐馆。你们一开始没有任何的计划，只是心中确定了几家自己平时较常来的餐馆。A餐馆价格高，非常好吃；B餐馆价格便宜，好吃；C餐馆价格一般，比较好吃。那么根据你们当天的心情就会有不同的选择。比如说月底了大家都没钱可想吃好吃的，那么B餐馆的优先级别肯定是最大的。当然新开了一家不错的餐馆也有可能加入计划行列中来。
我们可能没什么思路去实现一个优先队列，那么怎么办呢，jdk源码就是很好的学习地方
找到java.util.PriorityQueue这个类我们发现几个关键成员变量。
private static final int DEFAULT_INITIAL_CAPACITY = 11;
transient Object[] queue;
private int size = 0;
private final Comparator<? super E> comparator;
1.第一个不用说了默认初始化大小为11
2.很神奇它是靠一个Object数组维持一个优先队列的
3.size记录它的大小
4.comparator肯定是意味着靠它来比较优先级大小
接下来我们就彻底懵圈了，我们该怎么看？我们可以先从
add(E e)这个一般队列都有的方法为突破口。发现add(E e)实际上调用了offer(E e)这个方法
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}
我们可以发现以下几点:
1.参数不能为null
2.当size大小大于等于队列长度会自动扩容(队列长度小于64扩容至size的2倍是大小反之增加原来的50%)
3.我们发现一个特别的方法private void siftUp(int k, E x),而其中在是否传入comparator作出了两个方法分别的选择，我们简单起见看private void siftUpComparable(int k, E x)这个方法
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
可能看不明白，我稍微敏感一下，parent是插入位置的父节点的位置，(k-1)/2，如果它比它的父亲节点大就赋值在这个位置k，反之循环，直到循环结束再赋值。
这个循环十分精妙精妙在哪里，精妙在如果在循环内部交换n次的话的话会赋值3n次，但是拿出来就不一样了，总共需要n+2次。我们其实可以发现这个数组最小的默认在第一个。而且父亲结点都是比孩子节点小的。
有没有发现这个数组的结构很熟悉，其实它就是个完全二叉树(二叉堆)
当然上图只是举例子说明样子。
当然对应的我们照猫画虎可以自己实现个简单的优先队列
public class PriorityQueue<T> {
private Comparable<T>[] keys;
private int size;
@SuppressWarnings("unchecked")
public PriorityQueue (int max) {
keys = new Comparable[max+1];
size = 0;
}
public int getSize() {
return size;
}
public void insert(Comparable<T> a) {
keys[++size] = a;
swim(size);
}
public Comparable<T> delMax() {
Comparable<T> max = keys[1];
exch(1, size);
keys[size] = null;
size--;
sink(1);
return max;
}
public void exch(int i, int j) {
Comparable<T> temp = keys[i];
keys[i] = keys[j];
keys[j] = temp;
}
@SuppressWarnings("unchecked")
public boolean less(int i, int j) {
if (keys[i].compareTo((T)keys[j]) < 0)
return true;
return false;
}
public void swim(int k) {
Comparable<T> key = keys[k];
while(k>1) {
if(less(k/2 , k))
exch(k, k/2);
k = k/2;
}
}
public boolean isEmpty() {
return size==0;
}
public void sink(int k) {
while(2*k<=size) {
int j=2*k;
if(less(j, j+1)) j++;
if(!less(k, j)) break;
else exch(k, j);
k=j;
}
}
}
我的swim对应源码的siftUp,sink对应siftDown(当然没有优化过方便理解)
假设在小顶堆中插入操作相当于插在队列最后再不断上升直到不能再小了，而删除最小操作则是拿根节点的值跟最后面的值交换，再把最后的值设为null，再size减小。
堆排序
思路很简单我们想要一个升序的序列
1.先构建一个大顶堆
2.不断从大顶堆的根节点跟最后面的值交换，然后不设置为null，只是让size减小，那么逐渐变得有序。(我们无法去比较左右叶子节点的大小)
实现如下：
public class HeapSort {
private static <T>void sink(Comparable<T>[] a, int k, int len) {
while(2*k<len) {
int j=2*k;
if(j<len&&less(a, j, j+1)) j++;
if(less(a, j, k)) break;
exch(a, j, k);
k = j;
}
}
private static <T>void exch(Comparable<T>[] a, int i, int j) {
Comparable<T> temp = a[i-1];
a[i-1] = a[j-1];
a[j-1] = temp;
}
@SuppressWarnings("unchecked")
private static <T> boolean less(Comparable<T>[] a, int i, int j) {
return a[i-1].compareTo((T)a[j-1])<0;
}
private static <T> void sort(Comparable<T>[] a) {
int len = a.length;
for(int i=len/2;i>=1;i--) {
sink(a, i, len);//0123->1234(操作exch和less index即可)
}
while(len>1) {
exch(a, 1, len--);
sink(a, 1, len);//=1变0，已经到底一次了
}
}
private static <T> void show(Comparable<T>[] a) {
for(int i=0;i<a.length;i++) {
System.out.print(a[i]+" ");
}
}
