堆排序（二）

把數(shù)組從零開始連續(xù)的一段 = 完全二叉樹 size

i 左 son 2*1+1

i 右 son 2*1+2

父 (i-1) / 2

堆是完全二叉樹，分為大根堆和小根堆

在完全二叉樹里，每一棵子數(shù)最大的值是頭節(jié)點(diǎn)的值，就是大根堆

同理，在完全二叉樹里，每一棵子數(shù)最小的值是頭節(jié)點(diǎn)的值，就是小根堆

大根堆排序，插入的值 和 父節(jié)點(diǎn)比較，如果比父節(jié)點(diǎn)大，和它交換，直到最大，就停止，通過(guò)這樣的調(diào)整，得到的一定是大根堆。這個(gè)過(guò)程，我們叫做 heapInsert

public static void heapInsert(int [] arr, int index) {while (arr[index] > arr[(index - 1) / 2]) {// 和父節(jié)點(diǎn)交換值  并且把當(dāng)前下標(biāo)移動(dòng)到父節(jié)點(diǎn)swap(arr, index, (index - 1) / 2); index = (index - 1) / 2; }
}

從一堆數(shù)中找出最大值，移除它，保持還是大根堆，我們管這個(gè)過(guò)程叫做heapify

public static void heapify(int [] arr, int index, int heapSize) {int left = index * 2 + 1; // 左孩子的下標(biāo)while (left < heapSize) { // 下方還有孩子 (左孩子越界，那么就沒(méi)有右孩子了。)// 倆個(gè)孩子中，誰(shuí)的值大，把下標(biāo)給誰(shuí) （先找出孩子中最大的）int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1:left;// 父和孩子之間，誰(shuí)的值大，把下標(biāo)給誰(shuí) （較大的孩子和父節(jié)點(diǎn)找出最大的）largest = arr[largest] > arr[index] ? largest : index;if (largest == index) { // 如果當(dāng)前節(jié)點(diǎn)就是最大的 跳出break;}swap(arr, largest, index); // 交換位置index = largest; // 繼續(xù)比較left = index * 2 + 1; // 找左孩子繼續(xù) while}
}

題目：

已知一個(gè)幾乎有序的數(shù)組，幾乎有序是指，如果把數(shù)組排好順序的話，每個(gè)元素移動(dòng)的距離可以不超過(guò)K，并且K相對(duì)于數(shù)組來(lái)說(shuō)比較小。請(qǐng)選擇一個(gè)合適的排序算法針對(duì)這個(gè)數(shù)據(jù)進(jìn)行排序。

假如K = 6 ，建立一個(gè)heapSize = 7 的小根堆 （這樣小根堆的最小值一定是數(shù)組的最小值）

把最小的彈出，保持小根堆，新加入的數(shù)字做heapfiy，

繼續(xù)上面的步驟，直到全部彈出。

public static void main(String[] args) {PriorityQueue<Integer> heap = new PriorityQueue<>();heap.add(8);heap.add(4);heap.add(10);heap.add(3);while(!heap.isEmpty) {System.out.println(heap.poll());}
}