如下圖，將一個(gè)數(shù)組轉(zhuǎn)化堆，有如下性質(zhì)
-
所有父節(jié)點(diǎn)的值小于或等于兩個(gè)子節(jié)點(diǎn)的值(最小堆)
-
如果有左子樹(shù)食绿，那么左子樹(shù)的位置是2i+1，如果有右子樹(shù)公罕，右子樹(shù)的位置是2i+2
-
只有數(shù)組下標(biāo)小于或等于 【數(shù)組長(zhǎng)度 / 2 - 1】 的元素有孩子結(jié)點(diǎn)
堆排序?qū)崿F(xiàn)思想：
不斷構(gòu)造堆器紧，交換堆頂與末尾未排序的每一個(gè)元素，直到全部都排完楼眷。
topK問(wèn)題實(shí)現(xiàn)思想：
創(chuàng)建一個(gè)大小為k的數(shù)組铲汪，對(duì)該數(shù)組構(gòu)造堆熊尉。遍歷數(shù)組中剩余的元素，依次與構(gòu)建好的堆項(xiàng)元素比較掌腰，如果滿(mǎn)足條件(大于或小于)則替換堆頂元素并重新構(gòu)造堆狰住。
public class HeapDemo {
public static void main(String[] args){
//最小堆實(shí)現(xiàn)從大到小排序
int[] arrSort = {90,3,60,6,7,2,89,100,33,5};
MinHeap heap1 = new MinHeap(arrSort);
for(int i = arrSort.length - 1;i > 0; i --){
//把最小的元素移到末尾
heap1.swap(0, i);
//重新構(gòu)造最小堆
heap1.buildHeap(i);
}
//打印排序后的數(shù)組
for(int i = 0; i < arrSort.length;i ++){
System.out.println(arrSort[i]);
}
//最小堆實(shí)現(xiàn)topK
int[] arrTopK = {90,44,60,6,71,2,38,13,33,5};
int k = 3;
//創(chuàng)建一個(gè)大小為k的數(shù)組
int[] data = new int[k];
for(int i = 0; i < k; i ++){
data[i] = arrTopK[i];
}
MinHeap heap = new MinHeap(data);
for(int i = k; i < arrTopK.length; i ++){
//如果大于堆頂?shù)脑貏t替換頂并重新構(gòu)造
if(arrTopK[i] > heap.getRoot()) heap.setRoot(arrTopK[i]);
}
//打印最大的k個(gè)數(shù)
for(int i = 0; i < k; i ++){
System.out.println(data[i]);
}
}
//最小堆類(lèi)
static class MinHeap{
private int[] data;
public MinHeap(int[] data){
this.data = data;
buildHeap(data.length);
}
public void buildHeap(int heapSize){
for(int i = heapSize / 2 - 1; i >= 0;i --){
heapify(i, heapSize);
}
}
public void heapify(int index,int heapSize){
int right = right(index);
int left = left(index);
int min = index;
if(right < heapSize && data[right] < data[min]) min = right;
if(left < heapSize && data[left] < data[min]) min = left;
if(min == index) return;
swap(index,min);
heapify(min,heapSize);
}
private int right(int index){
//右兒子的下標(biāo)
return (index + 1) << 1;
}
private int left(int index){
//左兒子的下標(biāo)
return ((index + 1) << 1) - 1;
}
public void swap(int index1,int index2){
int tmp = data[index1];
data[index1] = data[index2];
data[index2] = tmp;
}
public int getRoot(){
return data[0];
}
public void setRoot(int root){
data[0] = root;
heapify(0, data.length);
}
}
}
參考文章：
http://blog.csdn.net/xiao__gui/article/details/8687982
http://blog.csdn.net/kimylrong/article/details/17150475
