堆可以理解成用數(shù)組實(shí)現(xiàn)的完全二叉樹(shù)結(jié)構(gòu)
完全二叉樹(shù)中如果每課子樹(shù)的最大值都在頂部就是大根堆
完全二叉樹(shù)中如果每棵子樹(shù)的最小值都在頂部就是小根堆
堆結(jié)構(gòu)的heapInsert與heapify操作
堆結(jié)構(gòu)的增大與減少
優(yōu)先級(jí)隊(duì)列結(jié)構(gòu)，就是堆結(jié)構(gòu)
public class HeapSort {
public static void sort(int [] arr) {
if(arr == null || arr.length <2) {
return;
}
for(int i=0; i<arr.length;i++) {
//從0下標(biāo)開(kāi)始逐漸擴(kuò)充成大根堆
heapInsert(arr,i);
}
int size = arr.length;
swap(arr,0,--size);
while(size > 0) {
heapify(arr,0,size);
swap(arr,0,--size);
}
}
public static void heapInsert(int[] arr, int index) {
while(arr[index] > arr[(index -1 ) / 2]) {
swap(arr, index, (index-1)/2);
// -0.5 取 0
index = (index -1)/2;
}
}
//堆化：相當(dāng)于給根部元素定位置
public static void heapify(int[] arr, int index, int size) {
int left = index*2 + 1;//左孩子的下標(biāo)
while(left < size) {//下方還有孩子節(jié)點(diǎn)
int largestIndex = left + 1 < size && arr[left + 1] > arr[left] ? left+1 : left;
largestIndex = arr[largest] > arr[index] ? largest : index;
if(largest == index) {
break;
}
swap(arr, largest,index);
index = largest;
left = index * 2 +1;
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
算法流程：
最大堆插入，堆頂為最大值鲁驶。
交換頭尾处窥，數(shù)組大小減一巷懈，再交換頭和尾--的值
依次類(lèi)推白群，得到堆排序的結(jié)果
堆排序擴(kuò)展問(wèn)題：
已知一個(gè)幾乎有序的數(shù)組，幾乎有序是指缆蝉，如果把數(shù)組拍好順序的話揪荣，每個(gè)元素移動(dòng)的距離可以不超過(guò)K筷黔，并且K相對(duì)于數(shù)組來(lái)說(shuō)比較小，請(qǐng)選擇一個(gè)合適的排序算法針對(duì)這個(gè)數(shù)據(jù)進(jìn)行排序
public void sortedArrDistanceLessK(int[] arr, int k) {
//Default is min-heap
PriorityQueue<Integer> heap = new PriorityQueue<>();
int index = 0;
//build heap size K
for(; index < Math.min(arr.length, k);index++) {
heap.add(arr[index]);
}
int i =0;
for(; index < arr.length;i++,index++) {
heap.add(arr[index]);
arr[i] = heap.poll();
}
while(!heap.isEmpty()) {
arr[i++] = heap.poll();
}
}
