--- date: '2024-02-26' description: assignment on min heap, max heap, and binary search tree construction with step-by-step insertion, removal operations, and double-ended priority queue. id: A5 modified: 2026-06-05 15:08:41 GMT-04:00 tags: - sfwr2c03 title: Min heap and binary search tree created: '2024-02-26' published: '2024-02-26' pageLayout: default slug: thoughts/university/twenty-three-twenty-four/sfwr-2c03/a5/A5 permalink: https://aarnphm.xyz/thoughts/university/twenty-three-twenty-four/sfwr-2c03/a5/A5.md generator: quartz: v4.6.0 hostedProvider: Cloudflare baseUrl: aarnphm.xyz full: https://aarnphm.xyz/llms-full.txt --- ## Problème 1. Consider the following sequence of values $S = [3, 42, 39, 86, 49, 89, 99, 20, 88, 51, 64]$ > \[!note\] Note > > We can represent tree textually via the following representation > > ```text > 13 ( > 11 ( > 8 ( > 2 > 4 > ) > 12 ( > * > 1 > ) > ) > 7 ( > 5 > 6 ( > 99 > * > ) > ) > ) > ``` > > Where we use $*$ as a placeholder for a missing child for those nodes that only have a single child. > \[!question\] P1.1 > > Draw the min heap (as a tree) obtained by adding the values in $S$ in sequence. Show each step 1. $S = [3]$. The root of the heap. ```text 3 ``` 2. $S = [3, 42]$. Added to the left of the root. ```text 3 ( 42 * ) ``` 3. $S = [3, 42, 39]$. Added to the right of the root. ```text 3 ( 42 39 ) ``` 4. $S = [3, 42, 39, 86]$. Added to the left of the left child of the root. (42 < 86) ```text 3 ( 42 ( 86 * ) 39 ) ``` 5. $S = [3, 42, 39, 86, 49]$. Added to the right of 42. ```text 3 ( 42 ( 86 49 ) 39 ) ``` 6. $S = [3, 42, 39, 86, 49, 89]$. Added to the left of 39. ```text 3 ( 42 ( 86 49 ) 39 ( 89 ) ) ``` 7. $S = [3, 42, 39, 86, 49, 89, 99]$. Added to the right of 39. ```text 3 ( 42 ( 86 49 ) 39 ( 89 99 ) ) ``` 8. $S = [3, 42, 39, 86, 49, 89, 99, 20]$. 20 becomes left child of 86. (20 < 86) then swap. (20 < 42) then swap. ```text 3 ( 20 ( 42 ( 86 * ) 49 ) 39 ( 89 99 ) ) ``` 9. $S = [3, 42, 39, 86, 49, 89, 99, 20, 88]$. 88 becomes right of 42 ```text 3 ( 20 ( 42 ( 86 88 ) 49 ) 39 ( 89 99 ) ) ``` 10. $S = [3, 42, 39, 86, 49, 89, 99, 20, 88, 51]$. 51 becomes right of 49 ```text 3 ( 20 ( 42 ( 86 88 ) 49 ( 51 * ) ) 39 ( 89 99 ) ) ``` 11. $S = [3, 42, 39, 86, 49, 89, 99, 20, 88, 51, 64]$. 64 becomes right of 49 ```text 3 ( 20 ( 42 ( 86 88 ) 49 ( 51 64 ) ) 39 ( 89 99 ) ) ``` > \[!question\] P1.2 > > Draw the max heap (as a tree) obtained by adding the values in $S$ in sequence. Show each step 1. $S = [3]$. The root of the heap. ```text 3 ``` 2. $S = [3, 42]$. 42 becomes the root, 3 becomes left child. ```text 42 ( 3 * ) ``` 3. $S = [3, 42, 39]$. 39 becomes right child. ```text 42 ( 3 39 ) ``` 4. $S = [3, 42, 39, 86]$. 86 becomes root. 42 becomes left child, 3 becomes left child of 42. ```text 86 ( 42 ( 3 * ) 39 ) ``` 5. $S = [3, 42, 39, 86, 49]$. 49 becomes left child of 86, swap 42, 42 becomes right child of 49. ```text 86 ( 49 ( 3 42 ) 39 ) ``` 6. $S = [3, 42, 39, 86, 49, 89]$. 89 become routes, swap 86, 49. ```text 89 ( 49 ( 3 42 ) 86 ( 39 * ) ) ``` 7. $S = [3, 42, 39, 86, 49, 89, 99]$. 99 becomes root, swap 89, 49. ```text 99 ( 49 ( 3 42 ) 89 ( 39 86 ) ) ``` 8. $S = [3, 42, 39, 86, 49, 89, 99, 20]$. 20 swap with 3, 3 becomes left child of 20. ```text 99 ( 49 ( 20 ( 3 * ) 42 ) 89 ( 39 86 ) ) ``` 9. $S = [3, 42, 39, 86, 49, 89, 99, 20, 88]$. 88 becomes left child of 99, swap 49, 20. ```text 99 ( 88 ( 49 ( 20 ( 3 * ) * ) 42 ) 89 ( 39 86 ) ) ``` 10. $S = [3, 42, 39, 86, 49, 89, 99, 20, 88, 51]$. 51 becomes right child of 88, swap 42, 20. ```text 99 ( 88 ( 51 ( 42 ( 20 ( 3 * ) ) * ) 49 ) 89 ( 39 86 ) ) ``` 11. $S = [3, 42, 39, 86, 49, 89, 99, 20, 88, 51, 64]$. 64, pushes 49 down. ```text 99 ( 88 ( 51 ( 42 ( 20 ( 3 * ) ) * ) 64 ( 49 * ) ) 89 ( 39 86 ) ) ``` > \[!question\] P1.3 > > Draw the binary search tree obtained by adding the values in $S$ in sequence. Show each step 1. $S = [3]$. The root of the tree. ```text 3 ``` 2. $S = [3, 42]$. 42 becomes the right child of 3. ```text 3 ( * 42 ) ``` 3. $S = [3, 42, 39]$. 39 becomes the left child of 42. ```text 3 ( * 42 ( 39 * ) ) ``` 4. $S = [3, 42, 39, 86]$. 86 becomes the right child of 42. ```text 3 ( * 42 ( 39 86 ) ) ``` 5. $S = [3, 42, 39, 86, 49]$. 49 becomes the left child of 86. ```text 3 ( * 42 ( 39 86 ( 49 * ) ) ) ``` 6. $S = [3, 42, 39, 86, 49, 89]$. 89 becomes the right child of 86. ```text 3 ( * 42 ( 39 86 ( 49 89 ) ) ) ``` 7. $S = [3, 42, 39, 86, 49, 89, 99]$. 99 becomes the right child of 89. ```text 3 ( * 42 ( 39 86 ( 49 89 ( * 99 ) ) ) ) ``` 8. $S = [3, 42, 39, 86, 49, 89, 99, 20]$. 20 becomes the left child of 39. ```text 3 ( * 42 ( 39 ( 20 * ) 86 ( 49 89 ( * 99 ) ) ) ) ``` 9. $S = [3, 42, 39, 86, 49, 89, 99, 20, 88]$. 88 becomes the right child of 86. ```text 3 ( * 42 ( 39 ( 20 * ) 86 ( 49 89 ( 88 99 ) ) ) ) ``` 10. $S = [3, 42, 39, 86, 49, 89, 99, 20, 88, 51]$. 51 becomes the right child of 49. ```text 3 ( * 42 ( 39 ( 20 * ) 86 ( 49 ( * 51 ) 89 ( 88 99 ) ) ) ) ``` 11. $S = [3, 42, 39, 86, 49, 89, 99, 20, 88, 51, 64]$. 64 becomes the left child of 51. ```text 3 ( * 42 ( 39 ( 20 * ) 86 ( 49 ( * 51 ( * 64 ) ) 89 ( 88 99 ) ) ) ) ``` ## Problème 2. Given an ordered list $L$ and value $v$, the `LowerBound` algorithm provide the position $p$ in list $L$ such that $p$ is the first offset in $L$ of a value larger-equal to $v$. Hence, $v \leq L[p]$ (or, if no such offset exists, $p = |L|$). The `LowerBound` algorithm does so in $\Theta(\log_2(|L|))$ comparisons. Argue that `LowerBound` is _worst-case optimal_: any algorithm that finds the correct position $p$ for any inputs $L$ and $v$ using only comparisons will require $\Theta(\log_2(|L|))$ comparisons. _Solution_ For a list of size $|L|$ there are $|L| + 1$ possible outcomes for the position $p$ in the list. The minimum height of a binary tree needed for $|L| + 1$ outcomes is $\log_2(|L| + 1)$ (at most $2^h$ leaves or $2^h \geq |L| + 1 \rightarrow h \geq \log_2(|L| +1)$ From Stirling’s approximation, comparison-based sorting algorithm lower bound is $\Omega(n \log(n))$. Given that the algorithm operates in $\Theta(\log_2(|L|))$ comparisons, it matches with the theoretical lower bound for the search algorithm. Therefore, no comparison-based algorithm can guarantee a better worst-case performance for position $p$, making `LowerBound` the worst-case optimal. ## Problème 3. Min heaps and max heaps allow one to efficiently store values and efficiently look up and remove the _smallest values_ and _largest values_, respectively. One cannot easily remove the largest value from a min heap or the smallest value from a max heap, however. > \[!question\] P3.1 > > Assume a value $v$ is a part of a min heap of at-most $n$ values and that we know v is stored at position $p$ in that heap. Provide an algorithm that can remove $v$ from the heap in worst-case $\mathcal{O}(\log_2(n))$
"\\begin{algorithm}\n\\caption{RemoveValue($heap, p$)}\n\\begin{algorithmic}\n\\Procedure{RemoveValue}{$heap, i$}\n \\State $n \\gets heap.length$\n \\State $temp \\gets heap[p]$\n \\State $heap[p] \\gets heap[n]$\n \\State $heap[n] \\gets temp$\n \\State $heap \\gets heap[:n]$\n \\State $\\text{HeapifyDown}(heap, p)$\n\\EndProcedure\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 23 RemoveValue(heap,pheap, p)

1:procedure RemoveValue(heap,iheap, i)

2:n←heap.lengthn \gets heap.length

3:temp←heap[p]temp \gets heap[p]

4:heap[p]←heap[n]heap[p] \gets heap[n]

5:heap[n]←tempheap[n] \gets temp

6:heap←heap[:n]heap \gets heap[:n]

7:HeapifyDown(heap,p)\text{HeapifyDown}(heap, p)

8:end procedure

"\\begin{algorithm}\n\\caption{HeapifyDown($heap, p$)}\n\\begin{algorithmic}\n\\Procedure{HeapifyDown}{$heap, i$}\n \\State $n \\gets \\text{size of } heap$\n \\While{$\\text{lchild}(i) \\leq n$}\n \\State $\\text{left} \\gets \\text{lchild}(i)$\n \\State $\\text{right} \\gets \\text{rchild}(i)$\n \\State $\\text{smallest} \\gets i$\n \\If{$\\text{left} \\leq n \\text{ and } heap[\\text{left}] < heap[\\text{smallest}]$}\n \\State $\\text{smallest} \\gets \\text{left}$\n \\EndIf\n \\If{$\\text{right} \\leq n \\text{ and } heap[\\text{right}] < heap[\\text{smallest}]$}\n \\State $\\text{smallest} \\gets \\text{right}$\n \\EndIf\n\n \\If{$\\text{smallest} = i$}\n \\State \\textbf{break}\n \\Else\n \\State $\\text{Swap } heap[i] \\text{ with } heap[\\text{smallest}]$\n \\State $i \\gets \\text{smallest}$\n \\EndIf\n \\EndWhile\n\\EndProcedure\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 24 HeapifyDown(heap,pheap, p)

1:procedure HeapifyDown(heap,iheap, i)

2:n←size of heapn \gets \text{size of } heap

3:while lchild(i)≤n\text{lchild}(i) \leq n do

4:left←lchild(i)\text{left} \gets \text{lchild}(i)

5:right←rchild(i)\text{right} \gets \text{rchild}(i)

6:smallest←i\text{smallest} \gets i

7:if left≤n and heap[left]<heap[smallest]\text{left} \leq n \text{ and } heap[\text{left}] < heap[\text{smallest}] then

8:smallest←left\text{smallest} \gets \text{left}

9:end if

10:if right≤n and heap[right]<heap[smallest]\text{right} \leq n \text{ and } heap[\text{right}] < heap[\text{smallest}] then

11:smallest←right\text{smallest} \gets \text{right}

12:end if

13:if smallest=i\text{smallest} = i then

14:break

15:else

16:Swap heap[i] with heap[smallest]\text{Swap } heap[i] \text{ with } heap[\text{smallest}]

17:i←smallesti \gets \text{smallest}

18:end if

19:end while

20:end procedure

> \[!question\] P3.2 > > Provide a data structure that allows one to efficiently store values and efficiently look up and remove _both_ the smallest and the largest values: all three of these operations should be supported in $\Theta(\log_2(n))$ We will implement a Double-ended Priority Queue (DEPQ), which is a min-max heap.
"\\begin{algorithm}\n\\caption{Insert($heap, v$)}\n\\begin{algorithmic}\n\\Procedure{Insert}{$heap, v$}\n \\State $heap.push(v)$\n \\State $\\text{Swim}(heap, \\text{size}(heap))$\n\\EndProcedure\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 25 Insert(heap,vheap, v)

1:procedure Insert(heap,vheap, v)

2:heap.push(v)heap.push(v)

3:Swim(heap,size(heap))\text{Swim}(heap, \text{size}(heap))

4:end procedure

"\\begin{algorithm}\n\\caption{RemoveMin($heap$)}\n\\begin{algorithmic}\n\\Procedure{RemoveMin}{$heap$}\n \\State $n \\gets \\text{size}(heap)$\n \\State $temp \\gets heap[1]$\n \\State $heap[1] \\gets heap[\\text{size}(heap)]$\n \\State $heap[n] \\gets temp$\n \\State $heap \\gets heap[:n]$\n \\State $\\text{Sink}(heap, 1)$\n\\EndProcedure\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 26 RemoveMin(heapheap)

1:procedure RemoveMin(heapheap)

2:n←size(heap)n \gets \text{size}(heap)

3:temp←heap[1]temp \gets heap[1]

4:heap[1]←heap[size(heap)]heap[1] \gets heap[\text{size}(heap)]

5:heap[n]←tempheap[n] \gets temp

6:heap←heap[:n]heap \gets heap[:n]

7:Sink(heap,1)\text{Sink}(heap, 1)

8:end procedure

"\\begin{algorithm}\n\\caption{RemoveMax($heap$)}\n\\begin{algorithmic}\n\\Procedure{RemoveMax}{$heap$}\n \\State $maxPos \\gets \\text{argmax}\\{heap[2], heap[3]\\}$\n \\State $heap[maxPos] \\gets heap[\\text{size}(heap)]$\n \\State $\\text{remove last el from} heap$\n \\State $\\text{Sink}(heap, maxPos)$\n\\EndProcedure\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 27 RemoveMax(heapheap)

1:procedure RemoveMax(heapheap)

2:maxPos←argmax{heap[2],heap[3]}maxPos \gets \text{argmax}\{heap[2], heap[3]\}

3:heap[maxPos]←heap[size(heap)]heap[maxPos] \gets heap[\text{size}(heap)]

4:remove last el fromheap\text{remove last el from} heap

5:Sink(heap,maxPos)\text{Sink}(heap, maxPos)

6:end procedure

"\\begin{algorithm}\n\\caption{Swim($heap, i$)}\n\\begin{algorithmic}\n\\Procedure{Swim}{$heap, i$}\n \\While{$i > 1$}\n \\State $parent \\gets \\lfloor i/2 \\rfloor$\n \\State $grandParent \\gets \\lfloor parent/2 \\rfloor$\n \\If{$(i \\mod 2 = 0 \\text{ and } heap[i] < heap[parent]) \\text{ or } (i \\mod 2 \\neq 0 \\text{ and } heap[i] > heap[parent])$}\n \\State $\\text{Swap}(heap[i], heap[parent])$\n \\EndIf\n \\If{$grandParent \\geq 1 \\text{ and } (heap[i] < heap[grandParent] \\text{ or } heap[i] > heap[grandParent])$}\n \\State $\\text{Swap}(heap[i], heap[grandParent])$\n \\EndIf\n \\State $i \\gets parent$\n \\EndWhile\n\\EndProcedure\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 28 Swim(heap,iheap, i)

1:procedure Swim(heap,iheap, i)

2:while i>1i > 1 do

3:parent←⌊i/2⌋parent \gets \lfloor i/2 \rfloor

4:grandParent←⌊parent/2⌋grandParent \gets \lfloor parent/2 \rfloor

5:if (imod  2=0 and heap[i]<heap[parent]) or (imod  2≠0 and heap[i]>heap[parent])(i \mod 2 = 0 \text{ and } heap[i] < heap[parent]) \text{ or } (i \mod 2 \neq 0 \text{ and } heap[i] > heap[parent]) then

6:Swap(heap[i],heap[parent])\text{Swap}(heap[i], heap[parent])

7:end if

8:if grandParent≥1 and (heap[i]<heap[grandParent] or heap[i]>heap[grandParent])grandParent \geq 1 \text{ and } (heap[i] < heap[grandParent] \text{ or } heap[i] > heap[grandParent]) then

9:Swap(heap[i],heap[grandParent])\text{Swap}(heap[i], heap[grandParent])

10:end if

11:i←parenti \gets parent

12:end while

13:end procedure

"\\begin{algorithm}\n\\caption{Sink($heap, i$)}\n\\begin{algorithmic}\n\\Procedure{Sink}{$heap, i$}\n \\State $n \\gets \\text{size}(heap)$\n \\While{$\\text{lchild}(i) \\leq n$}\n \\State $left \\gets \\text{lchild}(i)$\n \\State $right \\gets \\text{rchild}(i)$\n \\State $target \\gets i$\n\n \\If{$\\text{on min level and } heap[left] < heap[target]$}\n \\State $target \\gets left$\n \\ElsIf{$\\text{on max level and } heap[left] > heap[target]$}\n \\State $target \\gets left$\n \\EndIf\n \\If{$right \\leq \\text{size}(heap)$}\n \\If{$\\text{on min level and } heap[right] < heap[target]$}\n \\State $target \\gets right$\n \\ElsIf{$\\text{on max level and } heap[right] > heap[target]$}\n \\State $target \\gets right$\n \\EndIf\n \\EndIf\n\n \\If{$target = i$}\n \\State \\textbf{break}\n \\Else\n \\State $\\text{Swap}(heap[i], heap[target])$\n \\State $i \\gets target$\n \\EndIf\n \\EndWhile\n\\EndProcedure\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 29 Sink(heap,iheap, i)

1:procedure Sink(heap,iheap, i)

2:n←size(heap)n \gets \text{size}(heap)

3:while lchild(i)≤n\text{lchild}(i) \leq n do

4:left←lchild(i)left \gets \text{lchild}(i)

5:right←rchild(i)right \gets \text{rchild}(i)

6:target←itarget \gets i

7:if on min level and heap[left]<heap[target]\text{on min level and } heap[left] < heap[target] then

8:target←lefttarget \gets left

9:else if on max level and heap[left]>heap[target]\text{on max level and } heap[left] > heap[target] then

10:target←lefttarget \gets left

11:end if

12:if right≤size(heap)right \leq \text{size}(heap) then

13:if on min level and heap[right]<heap[target]\text{on min level and } heap[right] < heap[target] then

14:target←righttarget \gets right

15:else if on max level and heap[right]>heap[target]\text{on max level and } heap[right] > heap[target] then

16:target←righttarget \gets right

17:end if

18:end if

19:if target=itarget = i then

20:break

21:else

22:Swap(heap[i],heap[target])\text{Swap}(heap[i], heap[target])

23:i←targeti \gets target

24:end if

25:end while

26:end procedure