最（大）小堆的性質：

（1）是一顆完全二叉樹，遵循完全二叉樹的所有性質。

（2）父節點的鍵值（大于）小于等于子節點的鍵值

??

堆的存儲

一般都用數組來表示堆，i結點的父結點下標就為(i – 1) / 2。它的左右子結點下標分別為2 * i + 1和2 * i + 2。如第0個結點左右子結點下標分別為1和2。

?海量數據前n大，并且n比較小，堆可以放入內存

【基本原理及要點】
????????? 最大堆求前n小，最小堆求前n大。方法，比如求前n小，我們比較當前元素與最大堆里的最大元素，如果它小于最大元素，則應該替換那個最大元 素。這樣最后得到的n個元素就是最小的n個。適合大數據量，求前n小，n的大小比較小的情況，這樣可以掃描一遍即可得到所有的前n元素，效率很高。

【擴展】
??????????雙堆，一個最大堆與一個最小堆結合，可以用來維護中位數。

建立堆

? ? ? ? /**
* 將建立堆的過程看作是每次向堆中插入一個數據
* 每次插入數據都是在插入堆的尾部，然后進行堆調整
* 說明：每次調整的時候，只需要向上調整即可，由于每次調整之后的子節點的值總是大于父節點
* ? ? 當前插入放入節點向上一層一層調整時，始終保持子堆依然是最小堆結構
* ? ? 如 ? ? ?10
* ? ? ? ? ? ? / ? ? \
* ? ? ? ? ? 14 ? ? 17
* ? ? ? ? ?/ ? \ ? ? / ? \
* ? ? ? 18 ?15 20 ? 37
* ? ? ?插入節點13時，13為18的子節點，需交換，此時13為父節點，同時由于13小于14，再次交換 ? ? ? ? ?* ? ? ?注意這里不要調整13的子樹的結構，因為13的子樹都是向上調整子最小堆得來，因此13的子樹本身滿足最小堆結構
*/
?java代碼實現 void minHeapBuild(int[] num,int index){ //num[0,1..index-1]為已經實現的最小堆，index為插入num[index]值，建立新的堆int length=num.length;if(length<=0)return;int p=parent(index); while(p>=0&&index!=0){if(num[index]>=num[p])break;else{//交換節點int tmp=num[index]; num[index]=num[p]; num[p]=tmp;//重定位當前節點index=p;p=parent(index);}}}

堆的刪除

? ? ? ? ?/** 堆的刪除，每次都是刪除堆頂的元素，刪除后對堆進行調整* 具體做法是用堆尾部的元素代替堆頂元素，然后調整堆*/

java代碼實現 void minHeapDelete(int[] num, int len){int length=num.length;if(len>=length||len==0)return;int p=0;int child=leftChild(p);num[p]=num[len-1];//堆尾元素置于堆頂while(child<len){//找到左右子節點的較小值if(child+1<len && num[child]>num[child+1])child+=1;if(num[p]<=num[child])break;else{//交換節點int tmp=num[child]; num[child]=num[p]; num[p]=tmp;//重定位當前父節點p=child;child=leftChild(p);}}}
int parent(int i){return (i-1)/2;} int leftChild(int i){return 2*i+1;}
部分參考：http://blog.163.com/xychenbaihu@yeah/blog/static/132229655201351984231220/ ? ? ? ? ? ? ? ? ?http://blog.csdn.net/morewindows/article/details/6709644/

轉載于:https://www.cnblogs.com/wennian/p/5036912.html

總結

以上是生活随笔為你收集整理的堆排序 海量数据求前N大的值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。