二叉樹-堆

• 2019 年 12 月 31 日
• 筆記

二叉樹：滿二叉樹、完全二叉樹

滿二叉樹：葉子節點都在最底層，除了葉子節點，其他節點都有左右兩個子節點；

完全二叉樹：葉子節點都在最底下兩層，最後一層的葉子節點都靠左排列，並且除了最後一層，其他層的節點個數都要達到最大；

堆

• 完全二叉樹
• 堆的每個節點都大於等於（或者小於等於）其子樹的中的每個節點
• 每個節點都大於等於其子樹的節點，叫大頂堆，即頂點為樹中最大值

• 每個節點都小於等於其子樹的節點，叫小頂堆，即頂點為樹中最小值

堆的插入（最大堆）

• 按照二叉樹的順序，插入新元素
• 新插入的元素，需要與父節點比較，如果大於父節點，則和父節點交換
• 依次與父節點比較，滿足則完成，否則繼續交換到根
• 時間複雜度為 logN

堆的刪除（最大堆）

• 刪除都是移除根元素，然後為了繼續滿足完全二叉樹的特性，需要將最後一個元素替換到根元素位置
• 然後，從頂向下，做交換操作，直到滿足堆的特性，即父節點為子樹的最大值

Java的實現：PriorityQueue

# 父index 找 子index：  左子：2 * index + 1  右子：2 * index + 2  # 子index 找 父 index：  數學運算：(index-1) / 2  位運算：(index-1) >>> 2

插入

刪除

擴展

>>>與>>區別？  >>>為無符號右移  無論正負，高位都補0，  >>為右移  正數的話，高位補0  負數的話，高位補1    7 >>> 1  7 >> 1  -7 >>> 1  -7 >> 1