數(shù)據(jù)結(jié)構(gòu)-堆

定義

優(yōu)先隊(duì)列:一種特殊的隊(duì)列统台,隊(duì)列中元素出棧的順序是按照元素的優(yōu)先權(quán)大小,而不是元素入隊(duì)的先后順序柱查。

heap

堆的特性:

  • 必須是完全二叉樹(shù)
  • 用數(shù)組實(shí)現(xiàn)
  • 任一結(jié)點(diǎn)的值是其子樹(shù)所有結(jié)點(diǎn)的最大值或最小值
    • 最大值時(shí)掖肋,稱(chēng)為“最大堆”,也稱(chēng)大頂堆逻悠;
    • 最小值時(shí),稱(chēng)為“最小堆”韭脊,也稱(chēng)小頂堆童谒。
最大堆
最小堆

可以看到,對(duì)于堆(Heap)這種數(shù)據(jù)結(jié)構(gòu)沪羔,從根節(jié)點(diǎn)到任意結(jié)點(diǎn)路徑上所有的結(jié)點(diǎn)都是有序的饥伊。

堆的ADT

ADT

堆的實(shí)現(xiàn)

堆是用數(shù)組實(shí)現(xiàn)的完全二叉樹(shù),因此在Java中我們可以使用ArrayList實(shí)現(xiàn),而且向ArrayList中插入元素時(shí)撵渡,當(dāng)數(shù)組容量不足時(shí)融柬,他會(huì)自動(dòng)增長(zhǎng),這樣也免去考慮堆最大容量的問(wèn)題趋距。這里重點(diǎn)描述以上ADT中插入和刪除的操作粒氧。一般來(lái)說(shuō),會(huì)從堆中刪除最大值节腐,其實(shí)也就是最大堆中的第一個(gè)元素外盯。下面的實(shí)現(xiàn)為了普適性,實(shí)現(xiàn)了從堆中刪除任一結(jié)點(diǎn)的操作翼雀。

下面就以最大堆的構(gòu)成為例饱苟,研究一下如何使用數(shù)組實(shí)現(xiàn)堆。

最大堆

插入

堆的插入如何實(shí)現(xiàn)呢狼渊?只要我們謹(jǐn)記的定義箱熬,實(shí)現(xiàn)起來(lái)其實(shí)是很容易的。這里在回顧一下重點(diǎn)

  1. 完全二叉樹(shù)
  2. 任一結(jié)點(diǎn)的值是其左右子樹(shù)的最大值
  3. 用數(shù)組實(shí)現(xiàn)

考慮下圖所示的堆狈邑。

假設(shè)現(xiàn)有元素60需要插入城须,為了維持完全二叉樹(shù)的特性,新插入的元素一定是放在結(jié)點(diǎn)44的右子樹(shù)米苹;同時(shí)為了滿足任一結(jié)點(diǎn)的值要大于左右子樹(shù)的值這一特性糕伐,新插入的元素要和其父結(jié)點(diǎn)作比較,如果比父結(jié)點(diǎn)大蘸嘶,就要把父結(jié)點(diǎn)拉下來(lái)頂替當(dāng)前結(jié)點(diǎn)的位置良瞧,自己則依次不斷向上尋找,找到比自己小的父結(jié)點(diǎn)就拉下來(lái)训唱,直到?jīng)]有符合條件的值為止褥蚯。這樣,到最后就完成了插入操作况增;總結(jié)一下:

  1. 新插入的結(jié)點(diǎn)添加到數(shù)組最后
  2. 和其父結(jié)點(diǎn)比較大小遵岩,如果大于父結(jié)點(diǎn),就用父結(jié)點(diǎn)替換當(dāng)前位置巡通,同時(shí)自己的位置上移。
  3. 直到父結(jié)點(diǎn)不再大于自己或者是位置已近到了數(shù)組第一個(gè)位置舍哄,就找到屬于自己的位置了宴凉。

這里為了方便,我們直接占用了數(shù)組下標(biāo)為0的位置表悬,在0的位置放置了一個(gè)null弥锄,這樣數(shù)組中實(shí)際有效值的下標(biāo)就和我們完全二叉樹(shù)中層序遍歷的實(shí)際序號(hào)對(duì)應(yīng)了。這樣,完全二叉樹(shù)中籽暇,如果結(jié)點(diǎn)值為n,那么其左子樹(shù)則為2n,右子樹(shù)為2n+1温治;換句話說(shuō),對(duì)于任一結(jié)點(diǎn)n,其父結(jié)點(diǎn)為n/2 取整即可戒悠。

  • 初始化堆
public class MaxHeap<T extends Comparable<T>> {

    private List<T> mHeap;

    public MaxHeap() {
        mHeap = new ArrayList<>();
        // 為了方便熬荆,數(shù)組下標(biāo)為0 的位置,放置一個(gè)空元素绸狐,使得數(shù)組從下標(biāo)為1的位置開(kāi)始
        // 這樣卤恳,完全二叉樹(shù)中,如果結(jié)點(diǎn)值為n,那么其左子樹(shù)則為2n,右子樹(shù)為2n+1
        mHeap.add(0, null);
    }

}

當(dāng)然寒矿,為了保證有序性突琳,我們需要堆內(nèi)元素實(shí)現(xiàn)了Comparable接口。

  • 插入操作
/**
     * 堆的插入操作
     * @param value
     */
    public void insert(T value) {
        //新插入的元素首先放在數(shù)組最后符相,保持完全二叉樹(shù)的特性
        mHeap.add(value);
        // 獲取最后一個(gè)元素的在數(shù)組中的索引位置,注意是從index=1的位置開(kāi)始添加
        int index = mHeap.size() - 1;
        // 其父結(jié)點(diǎn)位置
        int pIndex = index / 2;



        //在數(shù)組范圍內(nèi)拆融,比較這個(gè)插入值和其父結(jié)點(diǎn)的大小關(guān)系,大于父結(jié)點(diǎn)則用父結(jié)點(diǎn)替換當(dāng)前值啊终,index位置上升為父結(jié)點(diǎn)
        while (index > 1) {
            // 插入結(jié)點(diǎn)小于等于其父結(jié)點(diǎn)镜豹,則不用調(diào)整
            if (compare(value, mHeap.get(pIndex)) <= 0) {
                break;
            } else {
                // 依次把父結(jié)點(diǎn)較小的值“降”下來(lái)
                mHeap.set(index, mHeap.get(pIndex));
                // 向上升一層
                index = pIndex;
                // 新的父結(jié)點(diǎn)
                pIndex = index / 2;
            }
        }
        // 最終找到index 的位置,把值放進(jìn)去
        mHeap.set(index, value);


    }

    /**
     *  
     * @param a
     * @param b
     * @return a>b 返回值大于0孕索,反之小于0
     */
    private int compare(T a, T b) {
        return a.compareTo(b);
    }

這里需要注意的是逛艰,當(dāng)插入結(jié)點(diǎn)大于父結(jié)點(diǎn)時(shí),我們并沒(méi)有交換兩個(gè)元素的算法搞旭,而只是把小的元素“降”了下來(lái)散怖,因?yàn)槲覀冏罱K只是想要找到一個(gè)正確的位置而已,交換是不必要肄渗,只需要在最后在合適的位置把值放上去就可以了镇眷。

刪除

理解了插入的實(shí)現(xiàn),刪除也是遵循同樣的規(guī)則翎嫡。

欠动、

假設(shè)要從上圖中刪除結(jié)點(diǎn)58,為了維持完全二叉樹(shù)的特性惑申,我們很容易想到用最后一個(gè)元素31去替代這個(gè)58具伍;然后比較31和其子樹(shù)的大小關(guān)系,如果比左右子樹(shù)腥ν铡(如果存在的話)人芽,就要從左右子樹(shù)中找一個(gè)較大的值替換他,而他自己就要跑到對(duì)應(yīng)子樹(shù)的位置绩脆,再次循環(huán)這種操作萤厅,直到?jīng)]有子樹(shù)比他小就可以了橄抹。在這里,按照以上的思路惕味,44將跑到根節(jié)點(diǎn)的位置楼誓,而他的位置將由31替代,堆依然是堆名挥∨备總結(jié)一下:

  1. 找到要?jiǎng)h除的結(jié)點(diǎn)在數(shù)組中的位置
  2. 用數(shù)組中最后一個(gè)元素替代這個(gè)位置的元素
  3. 當(dāng)前位置和其左右子樹(shù)比較,保證符合最大堆的結(jié)點(diǎn)間規(guī)則
  4. 刪除最后一個(gè)元素
/**
     * 堆的任意值的刪除操作
     * @param value
     * @return
     */
    public boolean delete(T value) {
        if (mHeap.isEmpty()) {
            return false;
        }
        // 得到數(shù)組中這個(gè)元素的下標(biāo)
        int index = mHeap.indexOf(value);
        if (index == -1) { // 被刪除元素不在數(shù)組中躺同,即刪除元素不在堆中
            return false;
        }

        // 獲取最后一個(gè)元素的在數(shù)組中的索引位置,注意是從index=1的位置開(kāi)始添加
        int lastIndex = mHeap.size() - 1;

        T temp = mHeap.get(lastIndex);
        // 用最后一個(gè)元素替換被刪除的位置
        mHeap.set(index, temp);


        int parent;
        for (parent = index; parent * 2 <= mHeap.size()-1; parent = index) {
            //當(dāng)前結(jié)點(diǎn)左子樹(shù)下標(biāo)
            index = parent * 2;
            // 左子樹(shù)下標(biāo)不等于數(shù)組長(zhǎng)度阁猜,因此必然有右子樹(shù) ,則左右子樹(shù)比較大小,這里-1 是因?yàn)閿?shù)組下標(biāo)=1 開(kāi)始
            if (index != mHeap.size()-1 && compare(mHeap.get(index), mHeap.get(index + 1))<0) {
                // 如果右子樹(shù)大蹋艺,則下標(biāo)指向右子樹(shù)
                index=index+1;
            }

            if (compare(temp, mHeap.get(index)) > 0) {
                //當(dāng)前結(jié)點(diǎn)大于其左右子樹(shù)剃袍,則不用調(diào)整,直接退出
                break;
            }else {
                // 子樹(shù)上移捎谨,替換當(dāng)前結(jié)點(diǎn)
                mHeap.set(parent, mHeap.get(index));
            }


        }
        // parent 就是替換結(jié)點(diǎn)最終該處的位置
        mHeap.set(parent, temp);
        // 移除數(shù)組最后一個(gè)元素
        mHeap.remove(lastIndex);
        return true;


    }

關(guān)于刪除操作民效,需要注意的一點(diǎn)就是,由于我們的數(shù)組相當(dāng)于是從下標(biāo)=1 的位置開(kāi)始涛救,因此需要注意數(shù)組邊界值和其長(zhǎng)度的關(guān)系畏邢。

下面就來(lái)測(cè)試一下最大堆的實(shí)現(xiàn):

測(cè)試類(lèi)
    private static Integer[] arrays = new Integer[]{10, 8, 3, 12, 9, 4, 5, 7, 1, 11, 17};

    private static void MaxHeapTest() {
        MaxHeap<Integer> mMaxHeap = new MaxHeap<>();
        for (int i = 0; i < arrays.length; i++) {
            mMaxHeap.insert(arrays[i]);
        }

        mMaxHeap.printHeap();
        System.out.printf("delete value %d from maxHeap isSuccess=%b \n", 17, mMaxHeap.delete(17));
        mMaxHeap.printHeap();
        System.out.printf("delete value %d from maxHeap isSuccess=%b \n", 1, mMaxHeap.delete(1));
        mMaxHeap.printHeap();
        System.out.printf("delete value %d from maxHeap isSuccess=%b \n", 12, mMaxHeap.delete(12));
        mMaxHeap.printHeap();
        System.out.printf("insert value %d to maxHeap \n", 16);
        mMaxHeap.insert(16);
        mMaxHeap.printHeap();

    }

printHeap() 的實(shí)現(xiàn)可以參考以下最小堆完整源碼

輸出:

17 12 5 8 11 3 4 7 1 9 10 
delete value 17 from maxHeap isSuccess=true 
12 11 5 8 10 3 4 7 1 9 
delete value 1 from maxHeap isSuccess=true 
12 11 5 8 10 3 4 7 9 
delete value 12 from maxHeap isSuccess=true 
11 10 5 8 9 3 4 7 
insert value 16 to maxHeap 
16 11 5 10 9 3 4 7 8 

可以看到检吆,當(dāng)我們第一次完成遍歷插入后舒萎,將構(gòu)建出如下所示的一顆完全二叉樹(shù),很顯然這也是最大堆蹭沛。當(dāng)我們一次刪除元素或插入元素時(shí)臂寝,根據(jù)輸出結(jié)果對(duì)應(yīng)的堆,可以看到我們的插入和刪除操作都是正確的摊灭。

畫(huà)歪的樹(shù)

這棵樹(shù)畫(huà)歪了咆贬,湊合看吧,o(╯□╰)o帚呼。

后面幾個(gè)輸出對(duì)應(yīng)的樹(shù)掏缎,感興趣的同學(xué)可以手動(dòng)畫(huà)一下,學(xué)二叉樹(shù)手動(dòng)畫(huà)樹(shù)真是一個(gè)好方法煤杀。

最小堆

最小堆眷蜈,每一個(gè)結(jié)點(diǎn)的值都小于其左右子樹(shù)的值,因此很容易的我們可以想到沈自,在構(gòu)建最大樹(shù)時(shí)把所有判斷大小的邏輯取反就可以實(shí)現(xiàn)了端蛆。事實(shí)上也的確就是這么簡(jiǎn)單,下面給出完整最小堆實(shí)現(xiàn)的完整代碼酥泛,就不具體分析了今豆。

public class MinHeap<T extends Comparable<T>> {
    private List<T> mHeap;
    //堆內(nèi)當(dāng)前元素個(gè)數(shù)
    public int size;

    public MinHeap() {
        mHeap = new ArrayList<>();
        // 為了方便,數(shù)組下標(biāo)為0 的位置柔袁,放置一個(gè)空元素呆躲,使得數(shù)組從下標(biāo)為1的位置開(kāi)始
        // 這樣,完全二叉樹(shù)中捶索,如果結(jié)點(diǎn)值為n,那么其左子樹(shù)則為2n,右子樹(shù)為2n+1
        mHeap.add(0, null);
    }

    public void insert(T value) {
        //新插入的元素首先放在數(shù)組最后插掂,保持完全二叉樹(shù)的特性
        mHeap.add(value);
        // 獲取最后一個(gè)元素的在數(shù)組中的索引位置,注意是從index=1的位置開(kāi)始添加,因此最后一個(gè)元素的位置是size-1
        int index = mHeap.size() - 1;
        // 其父結(jié)點(diǎn)位置
        int pIndex = index / 2;



        //在數(shù)組范圍內(nèi)腥例,比較這個(gè)插入值和其父結(jié)點(diǎn)的大小關(guān)系辅甥,小于父結(jié)點(diǎn)則用父結(jié)點(diǎn)替換當(dāng)前值,index位置上升為父結(jié)點(diǎn)
        while (index > 1) {
            // 插入結(jié)點(diǎn)大于等于其父結(jié)點(diǎn)燎竖,則不用調(diào)整
            if (compare(value, mHeap.get(pIndex)) >= 0) {
                break;
            } else {
                // 依次把父結(jié)點(diǎn)較大的值“將”下來(lái),把小的值升上去
                mHeap.set(index, mHeap.get(pIndex));
                // 向上升一層
                index = pIndex;
                // 新的父結(jié)點(diǎn)
                pIndex = index / 2;
            }
        }
        // 最終找到index 的位置璃弄,把值放進(jìn)去
        mHeap.set(index, value);


    }


    public boolean remove(T value) {
        if (mHeap.isEmpty()) {
            return false;
        }
        // 得到數(shù)組中這個(gè)元素的下標(biāo)
        int index = mHeap.indexOf(value);
        if (index == -1) { // 被刪除元素不在數(shù)組中,即刪除元素不在堆中
            return false;
        }

        // 獲取最后一個(gè)元素的在數(shù)組中的索引位置,注意是從index=1的位置開(kāi)始添加构回,因此最后一個(gè)元素的位置是size-1
        int lastIndex = mHeap.size() - 1;

        T temp = mHeap.get(lastIndex);
        // 用最后一個(gè)元素替換被刪除的位置
        mHeap.set(index, temp);


        int parent;
        for (parent = index; parent * 2 <= mHeap.size()-1; parent = index) {
            //當(dāng)前結(jié)點(diǎn)左子樹(shù)下標(biāo)
            index = parent * 2;
            // 左子樹(shù)下標(biāo)不等于數(shù)組長(zhǎng)度夏块,因此必然有右子樹(shù) ,則左右子樹(shù)比較大小
            if (index != mHeap.size()-1 && compare(mHeap.get(index), mHeap.get(index + 1))>0) {
                // 如果右子樹(shù)小,則下標(biāo)指向右子樹(shù)
                index=index+1;
            }

            if (compare(temp, mHeap.get(index)) < 0) {
                //當(dāng)前結(jié)點(diǎn)小于其左右子樹(shù)纤掸,則不用調(diào)整脐供,直接退出
                break;
            }else {
                // 子樹(shù)上移,替換當(dāng)前結(jié)點(diǎn)
                mHeap.set(parent, mHeap.get(index));
            }


        }
        // parent 就是替換結(jié)點(diǎn)最終該處的位置
        mHeap.set(parent, temp);
        // 移除數(shù)組最后一個(gè)元素
        mHeap.remove(lastIndex);
        return true;


    }

    private int compare(T a, T b) {
        return a.compareTo(b);
    }

    public void printHeap(){
        StringBuilder sb = new StringBuilder();
        for(int i=1;i<mHeap.size();i++) {
            sb.append(mHeap.get(i)).append(" ");
        }

        System.out.println(sb.toString());
    }
}

測(cè)試類(lèi)就不在這里占篇幅了借跪,有興趣的同學(xué)可以直接看源碼.


好了政己,堆的實(shí)現(xiàn)就到這里了。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末掏愁,一起剝皮案震驚了整個(gè)濱河市歇由,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌托猩,老刑警劉巖印蓖,帶你破解...
    沈念sama閱讀 222,681評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異京腥,居然都是意外死亡赦肃,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門(mén)公浪,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)他宛,“玉大人,你說(shuō)我怎么就攤上這事欠气√鳎” “怎么了?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,421評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵预柒,是天一觀的道長(zhǎng)队塘。 經(jīng)常有香客問(wèn)我袁梗,道長(zhǎng),這世上最難降的妖魔是什么憔古? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,114評(píng)論 1 300
  • 正文 為了忘掉前任遮怜,我火速辦了婚禮,結(jié)果婚禮上鸿市,老公的妹妹穿的比我還像新娘锯梁。我一直安慰自己,他們只是感情好焰情,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布陌凳。 她就那樣靜靜地躺著,像睡著了一般内舟。 火紅的嫁衣襯著肌膚如雪合敦。 梳的紋絲不亂的頭發(fā)上,一...
    開(kāi)封第一講書(shū)人閱讀 52,713評(píng)論 1 312
  • 那天谒获,我揣著相機(jī)與錄音蛤肌,去河邊找鬼。 笑死批狱,一個(gè)胖子當(dāng)著我的面吹牛裸准,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播赔硫,決...
    沈念sama閱讀 41,170評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼炒俱,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了爪膊?” 一聲冷哼從身側(cè)響起权悟,我...
    開(kāi)封第一講書(shū)人閱讀 40,116評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎推盛,沒(méi)想到半個(gè)月后峦阁,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,651評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡耘成,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評(píng)論 3 342
  • 正文 我和宋清朗相戀三年榔昔,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片瘪菌。...
    茶點(diǎn)故事閱讀 40,865評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡撒会,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出师妙,到底是詐尸還是另有隱情诵肛,我是刑警寧澤,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布默穴,位于F島的核電站怔檩,受9級(jí)特大地震影響褪秀,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜薛训,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評(píng)論 3 336
  • 文/蒙蒙 一溜歪、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧许蓖,春花似錦、人聲如沸调衰。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,699評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)嚎莉。三九已至米酬,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間趋箩,已是汗流浹背赃额。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,814評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留叫确,地道東北人跳芳。 一個(gè)月前我還...
    沈念sama閱讀 49,299評(píng)論 3 379
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像竹勉,于是被迫代替她去往敵國(guó)和親飞盆。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評(píng)論 2 361

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