# 2022q1 quiz15
> [Link](https://hackmd.io/@sysprog/linux2022-quiz15)

---

:::info
`lf` : last level
`lg` of node in same level is equal to `lg` of leftmost node with floor
:::

void minheap_init(unsigned long nr_items, struct heap_item *h)
{
    unsigned long lf = log2_floor(nr_items);
    unsigned long f = (1 << lf) - 1, c = (1 << lf);

    for (unsigned long i = f; i < nr_items; i++)
        do_sift_up(i + 1, nr_items, h);

    c = (c - (nr_items - f)) >> 1;
    for (unsigned long i = parent(nr_items); i < parent(nr_items) + c; i++)
        do_sift_up(i + 1, nr_items, h);
}

---

:::info
`f` : last node of second last level
`c` : first node of last level
:::

unsigned long f = (1 << lf) - 1, c = (1 << lf);


---

:::info
for `i` = `f` -> `nr_items`
:::

for (unsigned long i = f; i < nr_items; i++)
  do_sift_up(i + 1, nr_items, h);

heapify starts from `i+1`, which means to loop would do from `c` to `last` (inclusive),
`root` starts from `1`, hence `h[0]` is empty (for `parent()`, `lchild()`, `rchild()`)

`do_sift_up` would heapify all ancestor recursively


The uncolored half of tree is left untouched

---

:::info
`nr_items - f` : number of nodes in the bottommost level, which would be notated as `d`

Index of the left most node would be the maximum number of nodes in current level
:::

c = (c - (nr_items - f)) >> 1;
/* Change to (c - d) / 2 for readability */

`c = 8` means at most `8` nodes could reside in level `lf`
`c / 2` means number of nodes at the layer preciding `lf`

The remaining number of nodes would be

\begin{array}{c}
\dfrac{c}{2} - \lceil \dfrac{d}{2} \rceil &=& \dfrac{c}{2}+\lfloor -\dfrac{d}{2} \rfloor\\
&=& \lfloor \dfrac{c-d}{2} \rfloor
\end{array}

:::info
for `i` = `parent(nr_items)` -> `parent(nr_items) + c`

start from `parent(nr_items)`, loop `c` times
:::

for (unsigned long i = parent(nr_items); i < parent(nr_items) + c; i++)
  do_sift_up(i + 1, nr_items, h);


`do_sift_up` would then heapify the remaining nodes


And so, all nodes would do heapify at least once