算法筆記-二叉堆

MrZONT 發(fā)布于2019-08-15 18:09 / 1359人閱讀

摘要：二叉堆的概念二叉堆是一種特殊的二叉樹(shù)。二叉堆分為兩種最大堆和最小堆，最大堆的父節(jié)點(diǎn)一定大于其子節(jié)點(diǎn)根節(jié)點(diǎn)最大，最小堆的父節(jié)點(diǎn)小于其子節(jié)點(diǎn)根節(jié)點(diǎn)最小。這是我對(duì)二叉堆的理解，如有不對(duì)，歡迎指正，我會(huì)立即修改，謝謝。

二叉堆的概念

二叉堆是一種特殊的二叉樹(shù)。二叉樹(shù)是每個(gè)節(jié)點(diǎn)只有兩個(gè)子節(jié)點(diǎn)的樹(shù)（應(yīng)該都懂吧）。二叉堆分為兩種：最大堆和最小堆，最大堆的父節(jié)點(diǎn)一定大于其子節(jié)點(diǎn)（根節(jié)點(diǎn)最大），最小堆的父節(jié)點(diǎn)小于其子節(jié)點(diǎn)（根節(jié)點(diǎn)最小）。

下面是一個(gè)二叉樹(shù)：

我們用一維數(shù)組將二叉樹(shù)初始化，例如：我們有{1，2，3，4，5，6，7}七個(gè)數(shù)要放入堆中，第一步初始化數(shù)組的長(zhǎng)度大于8，array[0]為null，array[1]~array[7]放入數(shù)字。

為什么array[0]為null呢？因?yàn)橐孟聵?biāo)值找到它的子節(jié)點(diǎn)和父節(jié)點(diǎn)，比如a[1]=1,a[2]=2,a[3]。我們知道a[1]的子節(jié)點(diǎn)是a[2],a[3],由于是二叉樹(shù)，a[k]的子節(jié)點(diǎn)一定是a[2k]和a[2k+1],a[k]的父節(jié)點(diǎn)一定是a[k/2]。花個(gè)20秒思考一下吧。

圖示：

將一個(gè)二叉樹(shù)變成二叉堆

我以最大堆為例，最大堆的定義是：父節(jié)點(diǎn)的value一定要大于子節(jié)點(diǎn)的value。

1.子節(jié)點(diǎn)的value大于父節(jié)點(diǎn)的value的情況

此時(shí)T大于P，違反了最大堆的平衡性，所以要將T和其父節(jié)點(diǎn)對(duì)調(diào)

但是T移動(dòng)到了P的位置后，它的值依然比其父節(jié)點(diǎn)要大，還要上浮

最終T移動(dòng)到了根節(jié)點(diǎn)，最大堆平衡了

代碼如下：


public void swim(int k) {
        while (k > 1 && less(k / 2, k)) {
            exch(k / 2, k);
            k = k / 2;
        }
    }

2. 父節(jié)點(diǎn)的value小于子節(jié)點(diǎn)的value的情況

此時(shí)，H比子節(jié)點(diǎn)要小，H要下沉，先比較P和S誰(shuí)比較大，跟大的換位置

跟S換之后，發(fā)現(xiàn)依然比子節(jié)點(diǎn)要小，還是要下浮，最后

下沉的代碼如下：

public void sink(int k) {
//判斷是否超過(guò)數(shù)組最大長(zhǎng)度
    while (2 * k < N) {
    //找到子節(jié)點(diǎn)
        int j = 2 * k;
        //兩個(gè)子節(jié)點(diǎn)進(jìn)行比較，選大的
        if (j < N && less(j, j + 1)) j++;
        //沒(méi)有比子節(jié)點(diǎn)小，就跳出循環(huán)
        if (!less(k, j)) break;
        exch(k, j);
        k = j;
    }
}

上浮和下沉的應(yīng)用（敲黑板，重點(diǎn)）

向數(shù)組插入value會(huì)用到上浮

每次向隊(duì)尾插入一個(gè)value時(shí)，都要檢查是否違反最大堆的平衡性。

刪除根節(jié)點(diǎn)時(shí)，會(huì)用到下沉

每次想刪除根節(jié)點(diǎn)，第一步是要將跟節(jié)點(diǎn)與最后一個(gè)節(jié)點(diǎn)互換位置后，將其刪除，此時(shí)最后一個(gè)節(jié)點(diǎn)作為根節(jié)點(diǎn)，一定會(huì)比子節(jié)點(diǎn)要小，違反平衡性，那就下浮

堆排序

很簡(jiǎn)單，最大堆為例，根節(jié)點(diǎn)是最大的節(jié)點(diǎn)，每次將根節(jié)點(diǎn)和最后一個(gè)子節(jié)點(diǎn)對(duì)調(diào)位置，此時(shí)數(shù)組的最后一位即為最大，待其最大堆再次平衡時(shí)，再將根節(jié)點(diǎn)和最后一個(gè)子節(jié)點(diǎn)對(duì)調(diào)，即為排序。例如：

    數(shù)組元素為{a,b,c,d,e},假設(shè)二叉堆已經(jīng)平衡，a為根節(jié)點(diǎn)，也就是最大的節(jié)點(diǎn),將a和e對(duì)調(diào)，
    {e,b,c,d,a},數(shù)組的長(zhǎng)度此時(shí)應(yīng)該減一，將數(shù)組的前四位進(jìn)行二叉堆的平衡，e肯定要下沉到相應(yīng)位置，然后再將根節(jié)點(diǎn)和長(zhǎng)度減一后的最后一個(gè)節(jié)點(diǎn)對(duì)調(diào)位置。

這是我對(duì)二叉堆的理解，如有不對(duì)，歡迎指正，我會(huì)立即修改，謝謝。