Notes - DAA HT23, Heaps

Created: February 02, 2023

Flashcards

What is the “height” of a tree?

The longest downward path to a leaf.

What is the maximum possible height of a tree with $n$ nodes (in the most general case)?
\[n-1\]

What is the height of a binary heap with $n$ nodes?
\[\lfloor \log_2 n\rfloor\]

What is the max-heap property of a max heap?

Every child is less than or equal to its parent.

When representing a heap as an array $A$, where is the root element?
\[A[0]\]

When representing a binary heap as an array $A$, if $i$ is the index of the current node, where is its left child node?
\[A[(2i)+1]\]

When representing a binary heap as an array $A$, if $i$ is the index of the current node, where is its right child node?
\[A[(2i)+2]\]

When representing a binary heap as an array $A$, if $i$ is the index of the current node, where is its parent?
\[A\left[\left\lfloor \frac{i-1}{2} \right\rfloor\right]\]

What’s the worst-case time complexity of converting an array into a max heap?
\[\Theta(n)\]

What’s the worst-case time complexity for adjusting a node in a heap with two children that satisfy the max-heap property into a max heap overall?
\[\Theta(\log n)\]

When implementing heapsort, its necessary to remove the max element (i.e. the one at the root) and then recreate the heap. What array element is used in this case?

The last element in the array.

What’s the worst-case time complexity for a priority queue implemented with a max heap for insertion?
\[\Theta(\log n)\]

What’s the worst-case time complexity for a priority queue implemented with a max heap for finding the maximum (though not extracting it)?
\[\Theta(1)\]

What’s the worst-case time complexity for a priority queue implemented with a max heap for extracting the maximum?
\[\Theta(\log n)\]

What’s the worst-case time complexity for a priority queue implemented with a max heap for increasing priority?
\[\Theta(\log n)\]

Can you give pseudocode for the $\text{Max-Heapify}(A, i)$, which will “fix” a heap given an index $i$ assuming that its two children are max heaps?

 
MAX-HEAPIFY(A, i)
	l = LEFT(i)
	r = RIGHT(i)
	
	if l <= A.heap-size and A[l] > A[i]
		largest = l
	else
		largest = i
	
	if r <= A.heap-size and A[r] > A[largest]
		largest = r
		
	if largest != i
		swap A[i] and A[largest]
		MAX-HEAPIFY(A, largest)

Assuming you’ve defined $\text{Max-Heapify}$, can you give psuedocode for a function $\text{Build-Max-Heap}(A, n)$?

 
BUILD-MAX-HEAP(A, n):
	A.heap-size = n
	for i = floor(n/2) downto 1:
		MAX-HEAPIFY(A, i)

Can you quickly justify that the order of the $\text{Build-Max-Heap}$ algorithm given by

BUILD-MAX-HEAP(A, n):
	A.heap-size = n
	for i = floor(n/2) downto 1:
		MAX-HEAPIFY(A, i)

will be $O(n)$?

Let $c$ be the cost of making one swap in $\text{Max-Heapify}$. Note then that there are $\left\lceil \frac{n}{2^{h+1}\,} \right\rceil$ nodes of height $h$, and each one requires $h$ swaps in the worst case. Then

\[\begin{aligned} \sum^{\lfloor \log n \rfloor}\_{h=0} \left\lceil \frac{n}{2^{h+1}\\,} \right\rceil ch &\le \sum^{\lfloor \log n \rfloor}\_{h=0} \frac{n}{2^h} ch \\\\ &= cn \sum^{\lfloor \log n \rfloor}\_{h=0} \frac{h}{2^h} \\\\ &\le \sum^{\infty}\_{h=0} \frac{h}{2^h} \\\\ &\le cn \frac{1/2}{(1-1/2)^2} \\\\ &= O(n) \end{aligned}\]

Can you give the pseudocode for INCREASE-KEY(A, x, k)?

 
INCREASE-KEY(A, x, k):
	if k < x.key:
		error "new key is smaller than current key"

	x.key = k
	find the index i in the array A where x occurs
	while i > 0 and A[Parent(i)].key < A[i].key:
		exchange A[i] with A[Parent[i]]
		i = Parent(i)

Assuming the existence of a INCREASE-KEY procedure, can you give the pseudocode for INSERT for a max heap?

 
INSERT(A, x, n):
	if A.heapSize == n
		error "heap overflow"
	A.heapSize += 1
	k = x.key
	x.key = -infinity
	A[A.heapSize] = x
	map x to index heapSize
	INCREASE-KEY(A, x, k)

Proofs/Algorithms

Program a worst-case $\Theta(n)$ algorithm for converting an array into a binary max-heap.

Todo.



Related posts