數據結構 9 基礎數據結構 二叉堆 了解二叉堆的元素插入、刪除、構建二叉堆的代碼方式_網頁設計公司

※如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站,提高曝光率!

以設計的實用美學觀點,規劃出舒適、美觀的視覺畫面,有效提昇使用者的心理期待,營造出輕鬆、愉悅的網站瀏覽體驗。

是否記得我們在之前的學習中有學習到二叉樹 忘記的小夥伴們請查看:完全二叉樹的定義。

https://blogs.chaobei.xyz/archives/shuju2

二叉堆

二叉堆其實就是一個完全二叉樹 一起複習一下吧:關於二叉樹和滿二叉樹以及完全二叉樹的基本概念。

二叉樹

  • 每個節點下掛元素不超過2
  • 並且元素都是按照一定規律排列的

二叉樹規律

按照前人的總結,我們可以得出以下結論。

  • 一個深度為K 的二叉樹,最多包含節點數 2的k次方-1
  • 二叉樹指定n 層級所包含的節點數為 2的n-1次方

滿二叉樹

從字面意思我們可以理解到:這個二叉樹它是一種飽和的狀態,顧名思義稱作是滿二叉樹。

完全二叉樹

除去二叉樹的恭弘=叶 恭弘子節點,所有節點都包含有兩個節點,並且節點都是按照一定順序排列的,這樣的二叉樹被稱作是完全二叉樹

二叉堆類型

在上面我們已經提到過。二叉堆就是一種完全二叉樹、二叉樹的概念也已經了解到了。當然,現在應該分析二叉堆有有哪些性質

  • 最大堆
  • 最小堆

最大堆

最大堆的父節點元素的值都大於等於其兩個子元素的值

最小堆

反之,最小堆父節點元素的值,都小於等於其兩個子元素的值

二叉堆的堆頂部 則是這個堆序列最大或者最小的元素。

二叉堆的自我調整

二叉堆的自我調整,有以下幾種情況:

  • 新元素的插入
  • 元素的刪除
  • 構建二叉堆

我們以最上面的最小堆為例,講述如何將一個元素插入二叉堆、如何刪除一個元素、如何來構建一個二叉堆。

插入一個節點

按照上面最小堆的順序,我這裏再插入幾個其他元素方便觀察。假設這裏我插入一個元素1

元素1<元素6 進行上浮。子節點與父節點進行調換位置

元素1<元素3 進行上浮。子節點與父節點進行調換位置

元素1<元素2 進行上浮。到達堆頂部。

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

網站的第一印象網頁設計,決定了客戶是否繼續瀏覽的意願。台北網動廣告製作的RWD網頁設計,採用精簡與質感的CSS語法,提升企業的專業形象與簡約舒適的瀏覽體驗,讓瀏覽者第一眼就愛上它。

刪除一個元素

當前元素與子節點中最小元素進行比較、大於則交換位置下沉

假設我們刪除最頂層的元素1

二叉堆為了保證樹的結構、將二叉堆裏面尾部元素6填充到被刪除的位置。

當前元素6 與兩個子元素裏面最小元素 進行比較。大於則下沉

當前元素6 > 3 進行調換位置。元素6到達尾部。

規律:二叉堆的刪除元素和新增元素剛好是相反的

構建一個二叉堆

構建二叉堆、其實就是將一個原有的、無序的、完全二叉樹給他構建成有序的二叉堆。

假設我們來構建一個最小堆 我們這裏拿到一個無序的完全二叉樹如圖:

划重點:構建最小堆就是將非恭弘=叶 恭弘子節點進行下沉

1、操作元素5 元素5小於元素8 不進行移動

2、操作元素1 元素1小於元素5 不進行移動

3、操作元素7 省略步驟。最終結果如下:

4、操作元素3 省略步驟。最終結果如下:

至此,我們的無序完全二叉樹已經變成了一個有序的二叉最小堆

代碼實現

二叉堆雖然是一顆完全二叉樹,但是其存儲方式是順序存儲,使用的是數組、而不是鏈式指針。

我們可以發現如下規律:

  • 父元素左邊子元素位置 = 2*父元素下標 + 1
  • 父元素右邊子元素位置 = 2*父元素下標 + 2
public static void main(String[] args) {
        int[] array = {7, 1, 3, 5, 6, 4, 2, 8, 9};
        buildBinaryHeap(array);
        System.out.println(Arrays.toString(array));
    }

    public static void buildBinaryHeap(int[] array) {
        //除去恭弘=叶 恭弘子節點、將每個節點進行下沉操作
        for (int i = (array.length - 2) / 2; i >= 0; i--) {
            sinking(array, i);
        }
    }

    /**
     * 構建二叉堆、讓當前元素下沉
     *
     * @param array     被操作的數組
     * @param itemIndex 當前元素下標
     */
    public static void sinking(int[] array, int itemIndex) {
        //數組長度
        int length = array.length - 1;
        //父節點值
        int parent = array[itemIndex];

        //默認操作的是左孩子
        int childIndex = 2 * itemIndex + 1;

        while (childIndex < length) {

            //存在右邊子元素、並且右邊子元素值小於左邊
            if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
                //切換到右邊元素
                childIndex++;
            }

            //小於等於則無需交換
            if (parent <= array[childIndex]) break;

            //無需交換、只需要將子元素移動到父元素位置即可
            array[itemIndex] = array[childIndex];
            itemIndex = childIndex;

            //改變左右子元素的下標
            childIndex = 2 * itemIndex + 1;
        }
        //最終將父元素移動到指定位置即可。
        array[itemIndex] = parent;
    }

代碼示例

https://gitee.com/mrc1999/Data-structure

小結

通過本節的學習,應該需要掌握二叉堆這個重要的數據結構、如何將一個完全二叉樹構建成一個二叉堆、並且二叉堆在插入元素、和刪除元素時候如何將原來的結構保持不變的。這該是我們學習的。
下一節將繼續學習二叉堆的堆排序、我們一起加油!

參考

https://mp.weixin.qq.com/s/cq2EhVtOTzTVpNpLDXfeJg

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

※綠能、環保無空污,成為電動車最新代名詞,目前市場使用率逐漸普及化

台中景泰電動車行只是一個單純的理由,將來台灣的環境,出門可以自由放心的深呼吸,讓空氣回歸自然的乾淨,減少污染,留給我們下一代有好品質無空污的優質環境

您可能也會喜歡…