課程名稱：資料結構 CS203 A
授課教師：林基成
發放時間：2020-09-22
截止時間：2020-09-29

題目說明

完成 Priority_queue 中使用到的 heap 中的部分函式。

解題思路

這次作業的結構主要是用陣列來模擬的二元樹，若樹節點比下面的樹節點的值都大為 max heap，若比下面的樹節點都小為 min heap，first 為陣列開頭的指標，pred 為比較的方法，若 perd 為 less 則為 max heap，若為 greater 則為 min heap。

下面是依照我寫的順序來排序的。

  1. inline void pushHeapByIndex(RanIt first, ptrdiff_t hole, ptrdiff_t top, Ty& val, Pr pred)

    • 函式功能： 從 hole 開始，找到 val 應該填入的正確位置。
    • 參考作法： 定義 i 為當前 hole 的 parent，接著判斷若是 hole > top 且 pred(first[i], val)，表示 parent 的值需要往下移，最後更新使 hole = i 以及 i = (hole - 1) / 2 接著再繼續做，最後將 val 放入 first[hole] 即可。
    • 參考解法：
      1
      2
      3
      4
      5
      6
      7
      template< typename RanIt, typename Ty, typename Pr >
      inline void pushHeapByIndex(RanIt first, ptrdiff_t hole, ptrdiff_t top, Ty& val, Pr pred)
      {
          auto i = (hole - 1) / 2; // parent
          while (hole > top && pred(first[i], val)) first[hole] = first[i], i = ((hole = i) - 1) / 2;
          first[hole] = val;
      }

  2. inline void popHeapHoleByIndex(RanIt first, ptrdiff_t hole, ptrdiff_t bottom, Ty &val, Pr pred)

    • 函式功能： 從 hole 開始往下挑選較大的 child 放到 hole 直到到底為止。( 若兩個 child 相等則選擇右邊的 child )
    • 參考作法： 定義 i 為當前 hole 的 right child，接著判斷，若是 left child 大於 right child 則 i--，終止條件為 i < bottom，此時若是 i == bottom 則代表最後一層還有 left child，則直接將 left child 放入，最後再呼叫 pushHeapByIndex() 將 val 放入即可。
    • 參考解法：
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      template< typename RanIt, typename Ty, typename Pr >
      inline void popHeapHoleByIndex( RanIt first, ptrdiff_t hole, ptrdiff_t bottom, Ty &val, Pr pred )
      {
          auto top = hole, i = hole * 2 + 2; // i -> right child
          for (; i < bottom; i = (hole = i) * 2 + 2)
              first[hole] = first[pred(first[i], first[i - 1]) ? --i : i];
          // if only have left child
          if (i-- == bottom) first[hole] = first[i], hole = i;
          pushHeapByIndex(first, hole, top, val, pred);
      }