2022q1 Homework (quiz15)

contributed by < steven1lung >

do_sift_up

static void do_sift_up(unsigned long idx,
                       unsigned long nr_items,
                       struct heap_item *h)
{
    assert(idx > 0);
    if (idx == 1)
        return;

    uint64_t v = h[idx].key;
    unsigned long pidx = parent(idx);
    uint64_t pv = h[pidx].key;
    if (pv < v)
        return;

    struct heap_item tmp = h[pidx];
    h[pidx] = h[idx];
    h[idx] = tmp;
    do_sift_up(pidx, nr_items, h);
}

這個函式所做的事情就是確認父節點是小於（或大於，看是 min-heap 還是 max-heap）當前的節點，如果是的話就不用變更，如果不是就要將父節點跟現在的節點互換。

因為往上互換後，換完節點的新的父節點又有可能會不符合 heap，所以要繼續檢查，故在最後一行又呼叫 do_sift_up(pidx, nr_items, h)。

拿掉遞回

依照剛剛的想法，我們可以確認要繼續做遞迴的條件就是「父節點大於子節點」，所以我們可以使用一個 while 迴圈只要符合上述的條件就進行互換。

static void do_sift_up(unsigned long idx,
                       unsigned long nr_items,
                       struct heap_item *h)
{
    assert(idx > 0);
    unsigned long pidx = parent(idx);
    while(pidx>=1 && h[pidx].key > h[idx].key)
    {
        struct heap_item tmp = h[pidx];
        h[pidx] = h[idx];
        h[idx] = tmp;
        idx = pidx;
        pidx = parent(idx);
    }
}

在 while 迴圈裡要有上述的條件外（父節點大於子節點），還要確認我們所找的父街點是合法的，所以要多加一個判斷式 parent(idx>=1。

---

修改缺陷

在討論區同學有提到現在這版本的 do_sift_up 是有問題的，會在父節點都比子節點還小時結束執行，導致不會繼續檢查上層的節點。

所以要修改上述的 while 迴圈程式碼：

static void do_sift_up(unsigned long idx,
                       unsigned long nr_items,
                       struct heap_item *h)
{
    assert(idx > 0);
    unsigned long pidx = parent(idx);
    
    while(pidx>=1)
    {
        if(h[pidx].key > h[idx].key){
            struct heap_item tmp = h[pidx];
            h[pidx] = h[idx];
            h[idx] = tmp;
        }
        idx = pidx;
        pidx = parent(idx);
    }
}

改成只要有找到父節點就會繼續執行，如果父節點小於子節點（符合 min-heap）那就會不執行交換，繼續往上找。

但是上述所說的情況只會發生在初始化這個 heap 的時候，如果是正常的 min-heap，原本插入前的 heap 就會是符合 min-heap 的節點了，就只需要判斷父節點跟子節點的大小跟交換後的關係。

如果要減少遞回或是迭代的次數，可以將初始化跟平常所呼叫的 sift_up 區分，讓平常所呼叫的不用繼續執行下去。