---
tags: Linux Kernel
---

# 2022q1 Homework (quiz15)
contributed by < [steven1lung](https://github.com/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`。

---

### 修改缺陷
:warning: 在[討論區](https://hackmd.io/@sysprog/H1AlR9PU9)同學有提到現在這版本的 `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` 區分，讓平常所呼叫的不用繼續執行下去。