1. 思考
Top k 問題： 從海量數(shù)據(jù)中獲取前k個 最大值 或 最小值；
比如從 一百萬 個整數(shù)中比勉，獲取最大的1000個整數(shù)劳较；-
設(shè)計一種數(shù)據(jù)結(jié)構(gòu)，用來存放整數(shù)元素浩聋，包括的操作是 獲取最大值观蜗，添加元素，刪除最大值：
各數(shù)據(jù)結(jié)構(gòu)的時間復雜度對比 為了能達到最優(yōu)衣洁，使用 堆：
堆：獲取最大值時間復雜度O(1)墓捻，添加元素時間復雜度O(log n)，刪除最大值時間復雜度O(log n)坊夫；
2. 堆 (Heap)
- 這里的 堆 是一種數(shù)據(jù)結(jié)構(gòu)砖第，不是指內(nèi)存中堆，堆一般分為：
- 二叉堆（Binary Heap环凿，完全二叉堆）梧兼；
- 多叉堆（D-heap、D-ary Heap）;
- 索引堆（Index Heap）;
- 二項堆（Binomial Heap）拷邢；
- 斐波那契堆（Fibonacci Heap）袱院；
- 左傾堆（Leftist Heap）；
- 斜堆（Skew Heap）瞭稼；
- 堆的最重要性質(zhì)：任意節(jié)點的值總是
或者
子節(jié)點的值：
- 如果任意節(jié)點的值
- 如果任意節(jié)點的值
3. 二叉堆 (Binary Heap)
二叉堆 的數(shù)據(jù)結(jié)構(gòu)是一棵完全二叉樹，因此也被稱為完全二叉堆;
鑒于二叉堆的結(jié)構(gòu)梯找，底層可以用 數(shù)組 實現(xiàn)唆阿；
最大二叉堆數(shù)據(jù)結(jié)構(gòu)
- 二叉堆的 索引 規(guī)律（從0開始，與數(shù)組對應(yīng)）
- i = 0 , 表示根節(jié)點锈锤；
- i > 0 驯鳖，則父節(jié)點索引為floor( (i-1) / 2)；
- 如果 2i + 1 <= n - 1久免， 它的左子樹索引為 2i + 1 浅辙；
- 如果 2*i + 1 > n - 1 ，該節(jié)點無左子樹阎姥；
- 如果 2i + 2 <= n -1 ,該節(jié)點的右子節(jié)點索引為 2i + 2;
- 如果 2*i + 2 > n - 1记舆，該節(jié)點無右子節(jié)點；
- 二叉堆的接口設(shè)計
- int size();
//返回二叉堆元素個數(shù)呼巴；
- boolean isEmpty();
- void clear();
- void add(E element);
- E get();
- E remove();
- E replace(E element);
4. 二叉堆 獲取最大值
獲取堆頂屑埋，就能獲取最大值
public E get() {
emptyCheck();
return elements[0];
}
5. 二叉堆 添加元素
二叉堆添加元素（添加85）
- 如果node的值 > 父節(jié)點的值豪筝；
- 與父節(jié)點交互位置
- 如果node的值 <= 父節(jié)點的值，或者node沒有父節(jié)點摘能；
- 退出循環(huán)
- 這個過程叫做上濾(Sift Up)续崖；
- 時間復雜度為 O( log n)
// 添加元素
public void add(E element) {
elementNotNullCheck(element);
ensureCapacity(size + 1);
elements[size++] = element;
siftUp(size - 1);
}
// 上濾
private void siftUp(int index) {
E e = elements[index];
while (index > 0) {
int pindex = (index - 1) >> 1;
E p = elements[pindex];
if (compare(e, p) <= 0) return;
// 交換index、pindex位置的內(nèi)容
E tmp = elements[index];
elements[index] = elements[pindex];
elements[pindex] = tmp;
// 重新賦值index
index = pindex;
}
}
6. 二叉堆 刪除最大值
二叉堆 刪除元素（刪除85）
堆是一種數(shù)據(jù)結(jié)構(gòu)团搞，只能刪除 堆頂 元素严望，所以刪除 最大值，不能刪除其他位置的逻恐，參考棧結(jié)構(gòu)像吻。刪除的操作如下：
- 將存放堆的數(shù)組最后一個元素，覆蓋堆頂（node）复隆，然后將數(shù)組最后一個元素刪除拨匆；
- 如果該節(jié)點（node）的值 < 最大子節(jié)點的值；
- 將node與子節(jié)點交互位置挽拂；
- 如果該節(jié)點（node）的值 >= 最大子節(jié)點的值惭每，或者已經(jīng)沒有子節(jié)點了；
- 退出循環(huán)亏栈；
- 該過程稱為下濾（Shit Down）;
- 時間復雜度為 O( log n)
// 刪除堆頂
public E remove() {
emptyCheck();
int lastIndex = --size;
E root = elements[0];
elements[0] = elements[lastIndex];
elements[lastIndex] = null;
siftDown(0);
return root;
}
// 下濾
private void siftDown(int index) {
E element = elements[index];
int half = size >> 1;
// half 為第一個葉子節(jié)點索引
while (index < half) {
// index的節(jié)點有2種情況
// 1.只有左子節(jié)點
// 2.同時有左右子節(jié)點
// 獲取左子節(jié)點
int childIndex = (index << 1) + 1;
E child = elements[childIndex];
// 獲取右子節(jié)點
int rightIndex = childIndex + 1;
// 選出最大的子節(jié)點
if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
child = elements[childIndex = rightIndex];
}
if (compare(element, child) >= 0) break;
// 將子節(jié)點存放到index位置
elements[index] = child;
// 重新設(shè)置index
index = childIndex;
}
elements[index] = element;
}
6. 二叉堆 替換堆頂元素
替換（replace）和刪除最大值一樣台腥，都是替換堆頂元素宏赘，然后判斷是否大于 最大子節(jié)點，如果大于黎侈，那么進行 下濾察署，直到小于或者是葉子節(jié)點才退出循環(huán)；
public E replace(E element) {
elementNotNullCheck(element);
E root = null;
if (size == 0) {
elements[0] = element;
size++;
} else {
root = elements[0];
elements[0] = element; // 替換堆頂
siftDown(0); //下濾
}
return root;
}
7. 小頂堆的創(chuàng)建
以上所講的都是大頂堆峻汉，小頂堆的創(chuàng)建非常簡單箕母，只要修改compare的函數(shù)就可以。
小頂堆
// 大頂堆的compare
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
// 小頂堆的compare
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
8. 應(yīng)用
1. Top k 問題
- 從n個整數(shù)/浮點數(shù)中俱济，取出k個最大值，其中 k 遠遠小于 n钙勃；
- 可以使用全排序進行來得出最大的k個值蛛碌，但是時間復雜度為O( n log n);
- 使用二叉堆，時間復雜度為 O( n log k);
步驟如下：
- 創(chuàng)建一個小頂堆辖源；
- 遍歷這n個值蔚携；
- 先將 k 個值，添加到小頂堆中克饶；
- 從第k+1個值開始酝蜒，先獲取堆頂元素（ heap.get() ），比較矾湃；
- 如果大于堆頂元素亡脑，替換堆頂，進行下濾操作邀跃；
- 如果小于等于堆頂元素霉咨，循環(huán)下一個元素；
- 遍歷結(jié)束后拍屑，存放k個值的小頂堆途戒，就是存放最大的k個值；
for (int i = 0; i < data.length; i++) {
if (heap.size() < k) { // 前k個數(shù)添加到小頂堆
heap.add(data[i]);
} else if (data[i] > heap.get()) { // 如果是第k + 1個數(shù)僵驰，并且大于堆頂元素
heap.replace(data[i]);
}
}
2. 優(yōu)先級隊列
- 創(chuàng)建一個大頂推喷斋；
- 設(shè)置隊列節(jié)點的優(yōu)先級權(quán)重；
- 以權(quán)重來實現(xiàn)作為compare的判斷條件蒜茴；
- 這樣權(quán)重最大的節(jié)點星爪，被放在堆頂，權(quán)重越小的就放在后面的節(jié)點矮男；
- 在執(zhí)行隊列時移必，會調(diào)用remove()，獲取堆頂?shù)墓?jié)點毡鉴，執(zhí)行操作崔泵；
