當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

2021-10-21 二叉堆恋上数据结构笔记

發布時間：2025/3/20 编程问答 15 豆豆

生活随笔收集整理的這篇文章主要介紹了 2021-10-21 二叉堆恋上数据结构笔记小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

二叉堆（以最大堆為例）的原理：是一棵每個結點都大于其子結點的完全二叉樹0

二叉堆的實現：二叉堆是通過動態數組的形式實現的，其中動態數組存儲結點的順序和層序遍歷相同。

首先你要知道二叉堆通過動態數組實現，且排列順序與層序遍歷順序相同

其次，二叉堆是一個每個結點都大于其左右子結點的樹

那么，我們如何保證二叉堆每添加一個新元素，而二叉堆還能保持這個性質呢？而且在動態數組中我們添加時應該如何處理新元素的位置呢？如下圖向一顆二叉堆中添加80

樹中具體原理：添加新元素時，新元素初始位置在完全二叉樹的尾部（就是層序遍歷的最后一個結點后），然后與父結點比較大小，如果大于父結點，就和父結點交換位置，如此反復，直到小于父結點或者沒有父結點了。

動態數組中的具體原理：聯想樹中原理，轉化為動態數組就需要定位父結點在動態數組中的位置，也就是下面這些性質，如果根結點是0，新結點是i，則父結點就是i-1/2 向下取余，根結點是1，新結點是i，則父結點就是i/2 向下取余。知道了父結點的位置，剩下的和樹中操作相同
8.

二叉堆的刪除和添加類似，但是最大堆只在堆頂（根）處進行刪除

首先把數組末尾的元素替換掉數組的第一個元素，即覆蓋根結點

新的小根結點與其兩個子結點進行比較，與其中較大的那一個交換位置

不斷重復比較和交換的過程，直到沒有子結點或者大于所有子結點為止

相當于一個一個添加 (自上而下的上濾)

不完全等同于一個一個刪除，但是過程類似

以上是生活随笔為你收集整理的2021-10-21 二叉堆恋上数据结构笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。