Bo2SS

課程內容#

回顧 [完全二叉樹]#

• 

• 完全二叉樹預設從 1 開始編號

  • 這樣可以確保左孩子、右孩子編號簡潔
  • [否則] 左孩子編號需為 2 * i + 1，右孩子編號需為 2 * i + 2

• 可編號的性質→可用順序結構存儲，而不需要保存下一個結點的地址

  • 
  • 二叉樹→數組的轉換
  • 按層序遍歷的順序存儲在數組中，每一層的結點存儲是連續的
  • 這裡是從 0 號存儲的，也🆗，但不🆒

堆 [優先隊列]#

本質思想是優先隊列，但堆只是優先隊列的一種實現方式；堆是在完全二叉樹的基礎上維護的

結構定義#

• 結構與完全二叉樹一樣，但多維護了一種性質👇
  • 大頂堆：對於任意三元組，根結點值最大
  • 小頂堆：對於任意三元組，根結點值最小

結構操作#

一切操作都要維護自己的性質！

• 尾部插入【+ 調整】
  • 在尾部插入該元素，再自下向上調整，最遠調整到根結點
    • 在三元組裡不斷調整，依次與父結點比較，只要交換了就不停止，直到到達根結點
    • 交換時只會改變交換元素的相對大小，整個結構的相對大小關係不變
  • 比較的編號其實就是 i 与 i / 2
  • 時間複雜度：O (log [2] N)，即樹高
• 頭部彈出【+ 調整】
  • 將最後一個元素拿到堆頂，再自上向下調整，直到該元素沒有子結點
    • 在三元組裡不斷調整，依次與孩子結點比較，只要交換了就不停止，直到沒有孩子
    • 為什麼選擇最後一個元素放到堆頂？
    • 因為，如果拿其他位置的元素，誰來補這個元素的缺口呢
  • 比較的編號其實就是 i、2 * i 与 2 * i + 1
  • 時間複雜度：同為樹高
• [PS]
  • 大頂堆：方便查找第 1 大和第 2 大的元素 [根結點、第二層中]
    • 找第 3 大、第 4 大... 就不那麼簡單，不方便確定所在層數
  • ❗ 上面這個過程
    • 隊尾進元素，隊首出元素👉同隊列
    • 而出隊的元素是最值👉又名優先隊列

堆排序#

• 根據其性質，全部彈出，將得到一個排好序的序列
• ⭐思維轉變：堆頂元素的彈出操作 ==> 堆頂元素與堆尾元素交換
  • 【如此操作】
  • 大頂堆的元素全部彈出👉原數組存儲了一個從小到大的排序序列
  • [至此，從大頂堆，得到一個特殊的小頂堆，因為一般將彈出元素放在原數組尾部]
• 時間複雜度：O (NlogN)
  • 消耗的時間在於調整操作，每次調整的時間複雜度是 O (logN)，共 N 個元素，需調整 N - 1 次
  • 彈出操作的時間複雜度是 O (1) 的
  • 時間效率一定不會退化

建堆#

【若要使用堆排序，首先需要維護一個堆，也就是用普通的序列建堆，下面有 2 種思路】

常規思路#

又叫插入建堆法

• 按照前述尾部插入的調整方法：自下向上
  • 從第 0 層 [默認根結點在第 0 層] 開始，計算每一層的最多調整次數：
  • 
  • 第 i 層元素的調整次數為 i，第 i 層的結點數為 2 ^ i→ 第 i 層的總調整次數為 i * (2 ^ i)
• 最壞的建堆時間複雜度 O (NlogN)，計算過程如下：
  • 總的調整次數 S = (n - 1) * 2 ^ (n + 1) + 1，過程如下：
    • 
    • 利用裂項相消法
  • 上面的 n 對應【層數 - 1】 [從第 0 層開始，到第 n 層，層數為 n+1]，若令總的結點數為 N，则 n ≈ log [2] N
  • ❗【層數 n→結點數 N 的換算】將 n ≈ log [2] N 代入 S，得到 S ≈ Nlog [2] N
  • 即最壞的時間複雜度為：O (NlogN)

線性思路⭐#

也就是【線性建堆法】

• 

• 如圖所示

  • 常規思路：越到下面層，需要的調整次數越多，也就是權重越大
  • ❗ 那是否可以思維反轉，把大權重放到前面，讓下面結點數多的層的權重減小
  • 線性思路：可以！從倒數第二層開始排，【自上向下】調整

• 🆒最壞的建堆時間複雜度 O (N)

  • 同樣利用裂項相消法得到總的調整次數 S = 2 ^ (n + 1) - 2 - n
  • 把層數 n 換算到結點數 N，得到 S ≈ 2N - 2 - log [2] N
  • 即最壞的時間複雜度為：O (N)

• ⭐推薦視頻Linear Time BuildHeap——Youtube

  • 比較了常規建堆和線性建堆兩種思路，並有直觀的動畫演示，加深印象

代碼演示#

堆 [優先隊列]#

• 
• 

• 調整操作，巧妙使用變量 ind，還有 temp、l、r

  • ind 到一定條件就停止調整
  • 注意判斷 ind [入堆、出堆]、r [出堆] 是否存在

線性建堆法#

• 
• 

• 這裡的【堆排序】考慮了【建堆】+【排序】

  • O(N) + O(NlogN) = O(NlogN)

• 沒有定義堆結構，用數組模擬堆

• 第 33 行：堆結點編號從 1 開始更方便，所以這裡 arr-1 是讓數組的索引統一向左偏移 1 個 int 大小

• 封裝了自上向下的調整方法，從下圖可以看出最先調整的位置，來自前面的推薦視頻Linear Time BuildHeap——Youtube

• 

思考點#

• ❌n 層循環對應的時間複雜度就是 O (N^n)，要摒棄固化的思維，分析本質！
• 

提示#

課程速記#