Min heap and binary search tree

Problème 1.

Consider the following sequence of values $S = [3, 42, 39, 86, 49, 89, 99, 20, 88, 51, 64]$

Note

We can represent tree textually via the following representation

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.

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.

   3

2. $S = [3, 42]$. Added to the left of the root.

3 (
  42
  *
)

3. $S = [3, 42, 39]$. Added to the right of the root.

3 (
  42
  39
)

4. $S = [3, 42, 39, 86]$. Added to the left of the left child of the root. (42 < 86)

3 (
  42 (
    86
    *
  )
  39
)

5. $S = [3, 42, 39, 86, 49]$. Added to the right of 42.

3 (
  42 (
    86
    49
  )
  39
)

6. $S = [3, 42, 39, 86, 49, 89]$. Added to the left of 39.

3 (
  42 (
    86
    49
  )
  39 (
    89
  )
)

7. $S = [3, 42, 39, 86, 49, 89, 99]$. Added to the right of 39.

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.

3 (
  20 (
    42
      (
        86
        *
      )
    49
  )
  39 (
    89
    99
  )
)

9. $S = [3, 42, 39, 86, 49, 89, 99, 20, 88]$. 88 becomes right of 42

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

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

3 (
  20 (
    42 (
      86
      88
    )
    49 (
      51
      64
    )
  )
  39 (
    89
    99
  )
)

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.

   3

2. $S = [3, 42]$. 42 becomes the root, 3 becomes left child.

42 (
  3
  *
)

3. $S = [3, 42, 39]$. 39 becomes right child.

42 (
  3
  39
)

4. $S = [3, 42, 39, 86]$. 86 becomes root. 42 becomes left child, 3 becomes left child of 42.

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.

86 (
  49 (
    3
    42
  )
  39
)

6. $S = [3, 42, 39, 86, 49, 89]$. 89 become routes, swap 86, 49.

89 (
  49 (
    3
    42
  )
  86 (
    39
    *
  )
)

7. $S = [3, 42, 39, 86, 49, 89, 99]$. 99 becomes root, swap 89, 49.

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.

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.

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.

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.

99 (
  88 (
    51 (
      42 (
        20 (
          3
          *
        )
      )
      *
    )
    64 (
      49
      *
    )
  )
  89 (
    39
    86
  )
)

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.

   3

2. $S = [3, 42]$. 42 becomes the right child of 3.

3 (
  *
  42
)

3. $S = [3, 42, 39]$. 39 becomes the left child of 42.

3 (
  *
  42 (
    39
    *
  )
)

4. $S = [3, 42, 39, 86]$. 86 becomes the right child of 42.

3 (
  *
  42 (
    39
    86
  )
)

5. $S = [3, 42, 39, 86, 49]$. 49 becomes the left child of 86.

3 (
  *
  42 (
    39
    86 (
      49
      *
    )
  )
)

6. $S = [3, 42, 39, 86, 49, 89]$. 89 becomes the right child of 86.

3 (
  *
  42 (
    39
    86 (
      49
      89
    )
  )
)

7. $S = [3, 42, 39, 86, 49, 89, 99]$. 99 becomes the right child of 89.

3 (
  *
  42 (
    39
    86 (
      49
      89 (
        *
        99
      )
    )
  )
)

8. $S = [3, 42, 39, 86, 49, 89, 99, 20]$. 20 becomes the left child of 39.

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.

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.

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.

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.

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, p$)

1:procedure RemoveValue($heap, i$)

2:$n \gets heap.length$

3:$temp \gets heap[p]$

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

5:$heap[n] \gets temp$

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

7:$\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, p$)

1:procedure HeapifyDown($heap, i$)

2:$n \gets \text{size of } heap$

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

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

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

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

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

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

9:end if

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

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

12:end if

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

14:break

15:else

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

17:$i \gets \text{smallest}$

18:end if

19:end while

20:end procedure

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, v$)

1:procedure Insert($heap, v$)

2:$heap.push(v)$

3:$\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($heap$)

1:procedure RemoveMin($heap$)

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

3:$temp \gets heap[1]$

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

5:$heap[n] \gets temp$

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

7:$\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($heap$)

1:procedure RemoveMax($heap$)

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

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

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

5:$\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, i$)

1:procedure Swim($heap, i$)

2:while $i > 1$ do

3:$parent \gets \lfloor i/2 \rfloor$

4:$grandParent \gets \lfloor parent/2 \rfloor$

5:if $(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:$\text{Swap}(heap[i], heap[parent])$

7:end if

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

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

10:end if

11:$i \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, i$)

1:procedure Sink($heap, i$)

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

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

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

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

6:$target \gets i$

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

8:$target \gets left$

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

10:$target \gets left$

11:end if

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

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

14:$target \gets right$

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

16:$target \gets right$

17:end if

18:end if

19:if $target = i$ then

20:break

21:else

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

23:$i \gets target$

24:end if

25:end while

26:end procedure