二叉堆

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)

  1. 這里的 是一種數(shù)據(jù)結(jié)構(gòu)砖第,不是指內(nèi)存中,堆一般分為:
  • 二叉堆(Binary Heap环凿,完全二叉堆)梧兼;
  • 多叉堆(D-heap、D-ary Heap);
  • 索引堆(Index Heap);
  • 二項堆(Binomial Heap)拷邢;
  • 斐波那契堆(Fibonacci Heap)袱院;
  • 左傾堆(Leftist Heap);
  • 斜堆(Skew Heap)瞭稼;
  1. 堆的最重要性質(zhì):任意節(jié)點的值總是 \geq 或者 \leq 子節(jié)點的值:
  • 如果任意節(jié)點的值 \geq 子節(jié)點的值忽洛,稱為最大堆、大根堆环肘、大頂堆欲虚;
  • 如果任意節(jié)點的值 \leq 子節(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))
  1. i = 0 , 表示根節(jié)點锈锤;
  2. i > 0 驯鳖,則父節(jié)點索引為floor( (i-1) / 2);
  3. 如果 2i + 1 <= n - 1久免, 它的左子樹索引為 2i + 1 浅辙;
  4. 如果 2*i + 1 > n - 1 ,該節(jié)點無左子樹阎姥;
  5. 如果 2i + 2 <= n -1 ,該節(jié)點的右子節(jié)點索引為 2i + 2;
  6. 如果 2*i + 2 > n - 1记舆,該節(jié)點無右子節(jié)點;
  • 二叉堆的接口設(shè)計
  1. int size(); \qquad //返回二叉堆元素個數(shù)呼巴;
  2. boolean isEmpty(); \qquad //判斷是否為空泽腮;
  3. void clear(); \qquad //清空二叉堆;
  4. void add(E element); \qquad //添加元素伊磺;
  5. E get(); \qquad //獲取堆頂元素盛正;
  6. E remove(); \qquad //刪除堆頂元素;
  7. E replace(E element); \qquad //替換堆頂元素

4. 二叉堆 獲取最大值

獲取堆頂屑埋,就能獲取最大值

public E get() {
        emptyCheck();
        return elements[0];
    }

5. 二叉堆 添加元素

二叉堆添加元素(添加85)
  1. 如果node的值 > 父節(jié)點的值豪筝;
  • 與父節(jié)點交互位置
  1. 如果node的值 <= 父節(jié)點的值,或者node沒有父節(jié)點摘能;
  • 退出循環(huán)
  1. 這個過程叫做上濾(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)像吻。刪除的操作如下:

  1. 將存放堆的數(shù)組最后一個元素,覆蓋堆頂(node)复隆,然后將數(shù)組最后一個元素刪除拨匆;
  2. 如果該節(jié)點(node)的值 < 最大子節(jié)點的值;
  • 將node與子節(jié)點交互位置挽拂;
  1. 如果該節(jié)點(node)的值 >= 最大子節(jié)點的值惭每,或者已經(jīng)沒有子節(jié)點了;
  • 退出循環(huán)亏栈;
  1. 該過程稱為下濾(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);

步驟如下:

  1. 創(chuàng)建一個小頂堆辖源;
  2. 遍歷這n個值蔚携;
  • 先將 k 個值,添加到小頂堆中克饶;
  • 從第k+1個值開始酝蜒,先獲取堆頂元素( heap.get() ),比較矾湃;
  • 如果大于堆頂元素亡脑,替換堆頂,進行下濾操作邀跃;
  • 如果小于等于堆頂元素霉咨,循環(huán)下一個元素;
  1. 遍歷結(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í)行操作崔泵;
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末秒赤,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子憎瘸,更是在濱河造成了極大的恐慌入篮,老刑警劉巖妈候,帶你破解...
    沈念sama閱讀 211,042評論 6 490
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件欠肾,死亡現(xiàn)場離奇詭異话原,居然都是意外死亡临庇,警方通過查閱死者的電腦和手機初婆,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 89,996評論 2 384
  • 文/潘曉璐 我一進店門兢卵,熙熙樓的掌柜王于貴愁眉苦臉地迎上來匙隔,“玉大人琼懊,你說我怎么就攤上這事皱埠“拐剩” “怎么了?”我有些...
    開封第一講書人閱讀 156,674評論 0 345
  • 文/不壞的土叔 我叫張陵边器,是天一觀的道長训枢。 經(jīng)常有香客問我,道長忘巧,這世上最難降的妖魔是什么恒界? 我笑而不...
    開封第一講書人閱讀 56,340評論 1 283
  • 正文 為了忘掉前任,我火速辦了婚禮砚嘴,結(jié)果婚禮上十酣,老公的妹妹穿的比我還像新娘。我一直安慰自己枣宫,他們只是感情好婆誓,可當我...
    茶點故事閱讀 65,404評論 5 384
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著也颤,像睡著了一般洋幻。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上翅娶,一...
    開封第一講書人閱讀 49,749評論 1 289
  • 那天文留,我揣著相機與錄音,去河邊找鬼竭沫。 笑死燥翅,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的蜕提。 我是一名探鬼主播森书,決...
    沈念sama閱讀 38,902評論 3 405
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了凛膏?” 一聲冷哼從身側(cè)響起杨名,我...
    開封第一講書人閱讀 37,662評論 0 266
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎猖毫,沒想到半個月后台谍,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,110評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡吁断,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,451評論 2 325
  • 正文 我和宋清朗相戀三年趁蕊,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片仔役。...
    茶點故事閱讀 38,577評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡掷伙,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出又兵,到底是詐尸還是另有隱情炎咖,我是刑警寧澤,帶...
    沈念sama閱讀 34,258評論 4 328
  • 正文 年R本政府宣布寒波,位于F島的核電站,受9級特大地震影響升熊,放射性物質(zhì)發(fā)生泄漏俄烁。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 39,848評論 3 312
  • 文/蒙蒙 一级野、第九天 我趴在偏房一處隱蔽的房頂上張望页屠。 院中可真熱鬧,春花似錦蓖柔、人聲如沸辰企。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,726評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽牢贸。三九已至,卻和暖如春镐捧,著一層夾襖步出監(jiān)牢的瞬間潜索,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 31,952評論 1 264
  • 我被黑心中介騙來泰國打工懂酱, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留竹习,地道東北人。 一個月前我還...
    沈念sama閱讀 46,271評論 2 360
  • 正文 我出身青樓列牺,卻偏偏與公主長得像整陌,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 43,452評論 2 348

推薦閱讀更多精彩內(nèi)容