mysileng

【什么是堆】
概念：堆是一種特殊的二叉樹，具備以下兩種性質
1）每個節點的值都大于（或者都小于，稱為最小堆）其子節點的值
2）樹是完全平衡的，并且最后一層的樹葉都在最左邊
這樣就定義了一個最大堆。如下圖用一個數組來表示堆：

那么下面介紹二叉堆：二叉堆是一種完全二叉樹，其任意子樹的左右節點（如果有的話）的鍵值一定比根節點大，上圖其實就是一個二叉堆。

你一定發覺了，最小的一個元素就是數組第一個元素，那么二叉堆這種有序隊列如何入隊呢？看圖：

假設要在這個二叉堆里入隊一個單元，鍵值為2，那只需在數組末尾加入這個元素，然后盡可能把這個元素往上挪，直到挪不動，經過了這種復雜度為Ο(logn)的操作，二叉堆還是二叉堆。

那如何出隊呢？也不難，看圖：

出隊一定是出數組的第一個元素，這么來第一個元素以前的位置就成了空位，我們需要把這個空位挪至葉子節點，然后把數組最后一個元素插入這個空位，把這個“空位”盡量往上挪。這種操作的復雜度也是Ο(logn)。

【適用范圍】
海量數據前n大，并且n比較小，堆可以放入內存

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

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

【問題實例】
1)100w個數中找最大的前100個數。
用一個100個元素大小的最小堆即可。

做人要厚道：轉載請注明出處：http://diducoder.com/mass-data-topic-5-heap.html