Chapter 8 Heap - Ian-Liu-1990/Data-Structure GitHub Wiki

１. 優先權佇列與堆積種類

  1. 優先權佇列(Priority Queues)
  2. 最大堆積(Max Heaps)
  3. 最小堆積(Min Heaps)
  4. 最小最大堆積(Min-Max Heaps)
    1. 一層min-heap-一層max-heap
    2. 在min-heap的節點要與其他min-heap層的節點關係符合min-heap[反之max-heap也是]
  5. 兩頭堆積(Deaps)，左min - 右Max
  6. SMMH對稱最小最大堆積，每一層保持左節點<右節點

２. 優先權佇列

３. 堆積定義與特徵(重要)

  • 堆積是二元樹-包含二元樹所有特徵

  1. 最小堆積必備３條件

    1. 最小堆積是一顆完整二元樹-包含完整二元樹所有特徵，高度[(LogN)取下限(基數2)]+1
    2. 最小堆積是一顆最小樹(min tree)
    3. 最小樹是一顆二元樹，且每個節點的Key值不大於其子節點的Key值

  2. 最大堆積必備３條件

    1. 最大堆積是一顆完整二元樹-包含完整二元樹所有特徵，高度[(LogN)取下限(基數2)]+1
    2. 最大堆積是一顆最大樹(Max Tree)
    3. 最大樹是一顆二元樹，且每個節點的Key值不大於其子節點的Key值

  3. 最小-最大堆積或最大-最小堆積

    1. 完整二元樹
    2. 堆積中min層與max層間隔出現，且Root為min層
    3. 假設X為某一棵子樹樹根
      1. 若x在min層，則x為子樹中最小key
      2. 若x在max層，則x為子樹中最大key

  4. Deep兩頭堆積

    1. 一顆完整二元樹，可為空
    2. Root根不儲存Key
    3. 左子樹min-heap, 右子樹max-heap
    4. 若右子樹不為空，則左子樹上每一個節點L都可以對應到右子樹R的節點，必須滿足 L < R
    5. 若右子樹對應節點不存在，則取對應節點的父節點必須滿足 L < R

  5. SMMH對應最小最大堆積

    1. 完全二元樹
    2. Root為空，N個元素有N+1個節點
    3. 令element(N)，以N為樹根
      1. N的左子樹是element(N)中最小元素
      2. N的右子樹是element(N)中最大元素

４. 堆積主要用途

  • 堆積排序 : 建立空堆積時間複雜度影響排序法時間複雜度，被用來改善選擇排序法(每次選最大或最小排序)
  • 建立優先權佇列: 使用最大堆積(Max Heap)支援插入刪除運算，使兩個運算假設N筆資料下皆在O(logN)完成
  • 是一顆完整二元樹，有效降低二元樹(一般樹，二元搜尋樹)一維陣列空間的浪費率
  • 同組資料決定的Heap非唯一

５. 堆積樹在一維陣列表示法a[N]

堆積時間複雜度

  • 一N筆資料
操作 描述 時間複雜度
Build 建立空堆積 O(n)
Insert 堆積插入調整步驟不超過Heap樹高，完整二元樹高[(LogN)取下限(基數2)]+1 O(logN)
Delete 堆積刪除調整步驟不超過Heap樹高，完整二元樹高[(LogN)取下限(基數2)]+1 O(logN)
Get 取得Root值 O(1)
Sort 堆積排序 O(NlogN)

調整堆積演算法

Ａ. 最大堆積和最小堆積

  • 狀況一-空堆積 : 給一序列或一棵二元樹
  1. 假設節點N個，[從N/2取下限]開始往上調整
  2. 比較左右子節點是否小於父節點
  3. 若有子節點大於父節點則子節點和父節點互換
  • 狀況二-插入 : [需搭配程式碼(阿強)]
  1. 每次將新插入節點至於最後的節點，陣列最後的位置
  2. 由下往上調整，直至到Root
  3. 只會調整插入的某一棵子樹，不會影響並調整另一棵子樹
void InsertHeap(Type_Heap heap[], data x, int &n){
    int i;
    heap[i = ++n] = data; // 加入最後項

    while( i != 1){ // 開始往Root位置heap[1]調整
    if(heap[i] <= heap[i/2]) // 這是MAX heap;父節點>=子節點
      i = 1; // 不用調整
    else{
      swap(heap[i], heap[i/2]()); // 最後節點和父節點互換
      i /= 2;  // i來到父節點所在位置!!!
    }
 }
}
  • 狀況三-刪除 : [需搭配程式碼(阿強)]
  1. 將堆積樹最後一個節點即陣列最後一個與根節點互換，[泛論只要刪除節點，就拿堆積樹最後一個Node根他換]
  2. 輸出最後一個節點(即最大)
  3. 將根節點由上往下調整，只會調整某一棵子樹，不會影響並調整另一棵子樹
void deleteHeap(data_type heap[], data &x, int &n){
  int i, j;
  if (n==0)
    return ;
  
  x = heap[1]; // 將根即最大值填入X
  heap[1] = heap[n--]; // 根改由最後一項填入
  i = 1; // 根位置
  j = 2; // 根的左子
  while( j <= n){ // 直到陣列最大元素
   if(j < n)
     if(heap[j] < heap[ j + 1]) //左子小於右子
        j++;  // j由左子位置跳到右子位置; 否則不用換; 簡而言之，代表所在位置的值是左右節點中最大
     
     if(heap[i] >= heap[j]) // 父節點與最大值作比較
        j = n+1; // 若父比較大則直接將j 設為n+1跳出迴圈
     else{
         swap(heap[i], heap[j]) // 父與最大值互換位置
         i = j;  // i到新位置，也就是原本最大值位置
         j = 2*j; // 父的左子位置
      } 
  }
}

Ｂ. 最大-最小堆積或最小-最大堆積

  • 狀況一-插入 :
  1. 將節點插入最小-最大堆積樹的最後一個節點
  2. 將插入點調整至正確的min層和max層
  3. 調整至正確的層後，min層與min層再調整至符合min層或者max層與max層再調整至符合max層
  • 狀況二-刪除最小節點 :
  1. 將最小-最大堆積樹的根刪除
  2. 將最小-最大堆積樹的最後一個節點填補刪除根節點
  3. 被刪除節點有子或孫子找最小節點Min(子，孫子)，將最小節點與填補節點比較，若填補>最小節點，則互換
  4. 將填補節點調整至正確的min層和max層
  5. 調整至正確的層後，min層與min層再調整至符合min層或者max層與max層再調整至符合max層

Ｃ. Deep兩頭堆積左min-heap，右max-heap

  • 狀況一-插入
  1. 插入樹最後一個位置，左子樹節點鍵值必須小於相應右子樹節點或相應右子樹父節點鍵值，若無則交換
  2. 若互換或插入最後位置在左子樹min-heap 則按min-heap調整至正確位置，在右子樹max-heap，則按max-heap調整至正確位置
  • 狀況一-刪除
  1. 被刪除的節點，都要以最後一個節點來取代
  2. 取代的節點插入在左子樹min-heap 則按min-heap調整至正確位置，在右子樹max-heap，則按max-heap調整至正確位置
  3. 插入樹最後一個位置，左子樹節點鍵值必須小於相應右子樹節點或相應右子樹父節點鍵值，若無則交換

Ｄ. SMMH對稱最小最大

  1. 每次插入樹最後一個位置Ｅ，先檢查條件(１)有無兄弟，是否違反左<=右，違反則兄弟互換
  2. 位置Ｅ有無祖父，有，檢查條件(２)祖父左子<=E，違反則祖父左子與Ｅ互換
  3. 或無違反(２)，檢查條件(３)祖父右子>=Ｅ，違反則祖父右子與Ｅ互換
  4. 反覆2.和3.無違反後將Key值置入Ｅ
  • 狀況一-刪除
  1. 被刪除的節點，都要以最後一個節點ｘ來取代
  2. 被刪除節點位置Ｅ，找Min{位置Ｅ的左節點, 位置Ｅ兄弟的左節點}＝ｙ
  3. 若ｙ>ｘ，ｘ放入位置Ｅ
  4. 若ｙ<ｘ，swap(ｘ，ｙ)
  5. 返滬2. 3. 4.直到無違反後將Key值置入Ｅ