# Notes - DAA HT23, Heaps

### 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)?

What is the height of a binary heap with $n$ nodes?

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?

When representing a binary heap as an array $A$, if $i$ is the index of the current node, where is its left child node?

When representing a binary heap as an array $A$, if $i$ is the index of the current node, where is its right child node?

When representing a binary heap as an array $A$, if $i$ is the index of the current node, where is its parent?

What’s the worst-case time complexity of converting an array into a max heap?

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?

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*?

*insertion*?

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

*maximum*(though not extracting it)?

What’s the worst-case time complexity for a priority queue implemented with a max heap for *extracting the maximum*?

*extracting the maximum*?

What’s the worst-case time complexity for a priority queue implemented with a max heap for *increasing priority*?

*increasing priority*?

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)$?

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

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)`

?```
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?

`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.