前言
眾所周知堆排序就是個二叉堆减途，其實本質(zhì)上就是個完全二叉樹,我其實是想講堆排序的敬察，可為什么會和優(yōu)先隊列扯上關(guān)系呢，而優(yōu)先隊列又為何和jdk扯上關(guān)系呢笼痹。看完你就明白的
優(yōu)先隊列
優(yōu)先隊列顧名思義酪穿，是帶有優(yōu)先級的隊列凳干，普通隊列是怎么樣的(先進先出),那么優(yōu)先級隊列呢肯定是優(yōu)先級最大的先出，這有什么好處被济？
我們可以通過它來得到最大數(shù)或者最小數(shù)救赐，也能插入數(shù)字
映射到現(xiàn)實中來說某一天你跟室友去吃飯，外面有很多家餐館只磷。你們一開始沒有任何的計劃经磅，只是心中確定了幾家自己平時較常來的餐館。A餐館價格高钮追，非常好吃预厌；B餐館價格便宜，好吃畏陕；C餐館價格一般配乓，比較好吃。那么根據(jù)你們當天的心情就會有不同的選擇。比如說月底了大家都沒錢可想吃好吃的犹芹，那么B餐館的優(yōu)先級別肯定是最大的崎页。當然新開了一家不錯的餐館也有可能加入計劃行列中來。
我們可能沒什么思路去實現(xiàn)一個優(yōu)先隊列腰埂，那么怎么辦呢飒焦，jdk源碼就是很好的學(xué)習(xí)地方
找到j(luò)ava.util.PriorityQueue這個類我們發(fā)現(xiàn)幾個關(guān)鍵成員變量。
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數(shù)組維持一個優(yōu)先隊列的
3.size記錄它的大小
4.comparator肯定是意味著靠它來比較優(yōu)先級大小
接下來我們就徹底懵圈了屿笼，我們該怎么看牺荠？我們可以先從
add(E e)這個一般隊列都有的方法為突破口。發(fā)現(xiàn)add(E e)實際上調(diào)用了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;
}
我們可以發(fā)現(xiàn)以下幾點:
1.參數(shù)不能為null
2.當size大小大于等于隊列長度會自動擴容(隊列長度小于64擴容至size的2倍是大小反之增加原來的50%)
3.我們發(fā)現(xiàn)一個特別的方法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是插入位置的父節(jié)點的位置肝断，(k-1)/2杈曲，如果它比它的父親節(jié)點大就賦值在這個位置k，反之循環(huán)胸懈，直到循環(huán)結(jié)束再賦值担扑。
這個循環(huán)十分精妙精妙在哪里，精妙在如果在循環(huán)內(nèi)部交換n次的話的話會賦值3n次趣钱，但是拿出來就不一樣了涌献，總共需要n+2次。我們其實可以發(fā)現(xiàn)這個數(shù)組最小的默認在第一個首有。而且父親結(jié)點都是比孩子節(jié)點小的燕垃。
有沒有發(fā)現(xiàn)這個數(shù)組的結(jié)構(gòu)很熟悉，其實它就是個完全二叉樹(二叉堆)
當然上圖只是舉例子說明樣子绞灼。
當然對應(yīng)的我們照貓畫虎可以自己實現(xiàn)個簡單的優(yōu)先隊列
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對應(yīng)源碼的siftUp,sink對應(yīng)siftDown(當然沒有優(yōu)化過方便理解)
假設(shè)在小頂堆中插入操作相當于插在隊列最后再不斷上升直到不能再小了利术，而刪除最小操作則是拿根節(jié)點的值跟最后面的值交換呈野，再把最后的值設(shè)為null低矮，再size減小。
堆排序
思路很簡單我們想要一個升序的序列
1.先構(gòu)建一個大頂堆
2.不斷從大頂堆的根節(jié)點跟最后面的值交換被冒，然后不設(shè)置為null军掂，只是讓size減小，那么逐漸變得有序昨悼。(我們無法去比較左右葉子節(jié)點的大小)
實現(xiàn)如下：
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蝗锥，已經(jīng)到底一次了
}
}
private static <T> void show(Comparable<T>[] a) {
for(int i=0;i<a.length;i++) {
System.out.print(a[i]+" ");
}
}
