国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

算法筆記-二叉堆

MrZONT / 1349人閱讀

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

二叉堆的概念

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

下面是一個二叉樹：

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

為什么array[0]為null呢？因為要用下標值找到它的子節(jié)點和父節(jié)點，比如a[1]=1,a[2]=2,a[3]。我們知道a[1]的子節(jié)點是a[2],a[3],由于是二叉樹，a[k]的子節(jié)點一定是a[2k]和a[2k+1],a[k]的父節(jié)點一定是a[k/2]。花個20秒思考一下吧。

圖示：

將一個二叉樹變成二叉堆

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

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

此時T大于P，違反了最大堆的平衡性，所以要將T和其父節(jié)點對調

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

最終T移動到了根節(jié)點，最大堆平衡了

代碼如下：


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

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

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

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

下沉的代碼如下：

public void sink(int k) {
//判斷是否超過數(shù)組最大長度
    while (2 * k < N) {
    //找到子節(jié)點
        int j = 2 * k;
        //兩個子節(jié)點進行比較，選大的
        if (j < N && less(j, j + 1)) j++;
        //沒有比子節(jié)點小，就跳出循環(huán)
        if (!less(k, j)) break;
        exch(k, j);
        k = j;
    }
}
上浮和下沉的應用（敲黑板，重點）

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

每次向隊尾插入一個value時，都要檢查是否違反最大堆的平衡性。

刪除根節(jié)點時，會用到下沉

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

堆排序

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

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

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69648.html

相關文章

  • 數(shù)據(jù)結構與算法學習筆記 - 優(yōu)先隊列、二叉堆、左式堆

    摘要：模型優(yōu)先隊列是允許至少下列兩種操作的數(shù)據(jù)結構以及找出返回并刪除優(yōu)先隊列中最小的元素。左式堆也是二叉樹，左式堆和二叉堆的唯一區(qū)別是左式堆不是理想平衡，而實際上趨向于非常不平衡。事實上，沿左式堆的右路徑是該堆中的最短路徑。 6.1 模型 優(yōu)先隊列是允許至少下列兩種操作的數(shù)據(jù)結構：insert 以及 deleteMin（找出、返回并刪除優(yōu)先隊列中最小的元素）。 insert 操作等價于 en...

    SunZhaopeng 評論0 收藏0

  • 【閱讀筆記】——什么是二叉堆

    摘要：構建二叉樹構建二叉樹，就是把一個無序的完全二叉樹調整為二叉堆，本質上就是讓所有非葉子節(jié)點一次下沉上浮構建最大堆節(jié)點大的上浮，小的下沉構建最小堆節(jié)點小的上浮，大的下沉文章什么是二叉堆 什么是二叉堆 二叉堆的本質是一種完全二叉樹，它分為兩種類型：最大堆和最小堆 最大堆任何一個父節(jié)點的值，都大于等于它左右孩子的值，最小堆正好與之相反 showImg(https://segmentfault....

    big_cat 評論0 收藏0

  • JavaScript數(shù)據(jù)結構與算法（十一）二叉堆

    摘要：二叉堆數(shù)據(jù)結構是一種特殊的二叉樹，他能高效快速的找出最大值和最小值，常應用于優(yōu)先隊列和著名的堆排序算法中。 二叉堆數(shù)據(jù)結構是一種特殊的二叉樹，他能高效、快速的找出最大值和最小值，常應用于優(yōu)先隊列和著名的堆排序算法中。 二叉堆 二叉堆有以下兩個特性： 是一顆完全二叉樹，表示數(shù)的每一層都有左側和右側子節(jié)點（除最后一層的葉節(jié)點），并且最后一層的葉節(jié)點盡可能是左側子節(jié)點 二叉堆不是最小堆就是...

    MartinHan 評論0 收藏0

  • Python數(shù)據(jù)結構——二叉堆的實現(xiàn)

    摘要：二叉堆的有趣之處在于，其邏輯結構上像二叉樹，卻是用非嵌套的列表來實現(xiàn)。二叉堆結構性質為了更好地實現(xiàn)堆，我們采用二叉樹。圖完全二叉樹有意思的是我們用單個列表就能實現(xiàn)完全樹。下列所示的代碼是完全二叉堆的實現(xiàn)。 優(yōu)先隊列的二叉堆實現(xiàn) 在前面的章節(jié)里我們學習了先進先出（FIFO）的數(shù)據(jù)結構：隊列（Queue）。隊列有一種變體叫做優(yōu)先隊列（Priority Queue）。優(yōu)先隊列的出隊（Dequ...

    stackfing 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<