profile pic
⌘ '
raccourcis clavier
Search

Min heap and binary search tree

  • Étiquette

    • publié à

    • modifié à

    • durée

      11 min de lecture

    • source

      llms.txt

    Problème 1.

    Consider the following sequence of values S=[3,42,39,86,49,89,99,20,88,51,64]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 SS in sequence. Show each step

    1. S=[3]S = [3]. The root of the heap.

      3

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

    3 (
  42
  *
)
    1. S=[3,42,39]S = [3, 42, 39]. Added to the right of the root.
    3 (
  42
  39
)
    1. S=[3,42,39,86]S = [3, 42, 39, 86]. Added to the left of the left child of the root. (42 < 86)
    3 (
  42 (
    86
    *
  )
  39
)
    1. S=[3,42,39,86,49]S = [3, 42, 39, 86, 49]. Added to the right of 42.
    3 (
  42 (
    86
    49
  )
  39
)
    1. S=[3,42,39,86,49,89]S = [3, 42, 39, 86, 49, 89]. Added to the left of 39.
    3 (
  42 (
    86
    49
  )
  39 (
    89
  )
)
    1. S=[3,42,39,86,49,89,99]S = [3, 42, 39, 86, 49, 89, 99]. Added to the right of 39.
    3 (
  42 (
    86
    49
  )
  39 (
    89
    99
  )
)
    1. S=[3,42,39,86,49,89,99,20]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
  )
)
    1. S=[3,42,39,86,49,89,99,20,88]S = [3, 42, 39, 86, 49, 89, 99, 20, 88]. 88 becomes right of 42
    3 (
  20 (
    42 (
      86
      88
    )
    49
  )
  39 (
    89
    99
  )
)
    1. S=[3,42,39,86,49,89,99,20,88,51]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
  )
)
    1. S=[3,42,39,86,49,89,99,20,88,51,64]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 SS in sequence. Show each step

    1. S=[3]S = [3]. The root of the heap. 
      3
    2. S=[3,42]S = [3, 42]. 42 becomes the root, 3 becomes left child.
    42 (
  3
  *
)
    1. S=[3,42,39]S = [3, 42, 39]. 39 becomes right child.
    42 (
  3
  39
)
    1. S=[3,42,39,86]S = [3, 42, 39, 86]. 86 becomes root. 42 becomes left child, 3 becomes left child of 42.
    86 (
  42 (
    3
    *
  )
  39
)
    1. S=[3,42,39,86,49]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
)
    1. S=[3,42,39,86,49,89]S = [3, 42, 39, 86, 49, 89]. 89 become routes, swap 86, 49.
    89 (
  49 (
    3
    42
  )
  86 (
    39
    *
  )
)
    1. S=[3,42,39,86,49,89,99]S = [3, 42, 39, 86, 49, 89, 99]. 99 becomes root, swap 89, 49.
    99 (
  49 (
    3
    42
  )
  89 (
    39
    86
  )
)
    1. S=[3,42,39,86,49,89,99,20]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
  )
)
    1. S=[3,42,39,86,49,89,99,20,88]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
  )
)
    1. S=[3,42,39,86,49,89,99,20,88,51]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
  )
)
    1. S=[3,42,39,86,49,89,99,20,88,51,64]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 SS in sequence. Show each step

    1. S=[3]S = [3]. The root of the tree.

      3

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

    3 (
  *
  42
)
    1. S=[3,42,39]S = [3, 42, 39]. 39 becomes the left child of 42.
    3 (
  *
  42 (
    39
    *
  )
)
    1. S=[3,42,39,86]S = [3, 42, 39, 86]. 86 becomes the right child of 42.
    3 (
  *
  42 (
    39
    86
  )
)
    1. S=[3,42,39,86,49]S = [3, 42, 39, 86, 49]. 49 becomes the left child of 86.
    3 (
  *
  42 (
    39
    86 (
      49
      *
    )
  )
)
    1. S=[3,42,39,86,49,89]S = [3, 42, 39, 86, 49, 89]. 89 becomes the right child of 86.
    3 (
  *
  42 (
    39
    86 (
      49
      89
    )
  )
)
    1. S=[3,42,39,86,49,89,99]S = [3, 42, 39, 86, 49, 89, 99]. 99 becomes the right child of 89.
    3 (
  *
  42 (
    39
    86 (
      49
      89 (
        *
        99
      )
    )
  )
)
    1. S=[3,42,39,86,49,89,99,20]S = [3, 42, 39, 86, 49, 89, 99, 20]. 20 becomes the left child of 39.
    3 (
  *
  42 (
    39 (
      20
      *
    )
    86 (
      49
      89 (
        *
        99
      )
    )
  )
)
    1. S=[3,42,39,86,49,89,99,20,88]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
      )
    )
  )
)
    1. S=[3,42,39,86,49,89,99,20,88,51]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
      )
    )
  )
)
    1. S=[3,42,39,86,49,89,99,20,88,51,64]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 LL and value vv, the LowerBound algorithm provide the position pp in list LL such that pp is the first offset in LL of a value larger-equal to vv. Hence, v≤L[p]v \leq L[p] (or, if no such offset exists, p=∣L∣p = |L|). The LowerBound algorithm does so in Θ(log⁡2(∣L∣))\Theta(\log_2(|L|)) comparisons. Argue that LowerBound is worst-case optimal: any algorithm that finds the correct position pp for any inputs LL and vv using only comparisons will require Θ(log⁡2(∣L∣))\Theta(\log_2(|L|)) comparisons.

    Solution

    For a list of size ∣L∣|L| there are ∣L∣+1|L| + 1 possible outcomes for the position pp in the list. The minimum height of a binary tree needed for ∣L∣+1|L| + 1 outcomes is log⁡2(∣L∣+1)\log_2(|L| + 1) (at most 2h2^h leaves or 2h≥∣L∣+1→h≥log⁡2(∣L∣+1)2^h \geq |L| + 1 \rightarrow h \geq \log_2(|L| +1)

    From Stirling’s approximation, comparison-based sorting algorithm lower bound is Ω(nlog⁡(n))\Omega(n \log(n)). Given that the algorithm operates in Θ(log⁡2(∣L∣))\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 pp, 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 vv is a part of a min heap of at-most nn values and that we know v is stored at position pp in that heap. Provide an algorithm that can remove vv from the heap in worst-case O(log⁡2(n))\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 28 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 29 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

    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 Θ(log⁡2(n))\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 30 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 31 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 32 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 33 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 34 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

    Vous pourriez aimer ce qui suit

  • confirmation bias
  • Expenses
  • reason
  • Stability and natural responses.
  • Fork and threads
  • dialectics
  • Autograd