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é)點的值忽洛,稱為最大堆、大根堆环肘、大頂堆欲虚;
- 如果任意節(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í)行操作崔泵;