Lesson test: Heaps and priority queues

Sign in

Libre University uses your GitHub account. Signing in is only needed to sit a final test, so the score is kept on your profile.

Heaps and priority queues

1.[2p]
What is the heap property of a binary min-heap?

Every node's key is no larger than both of its children's keys

Correct

Every node's left subtree holds smaller keys and its right subtree larger ones

The answer is: Every node's key is no larger than both of its children's keys

Every level holds keys in ascending order

The answer is: Every node's key is no larger than both of its children's keys

The two children of a node are ordered relative to each other

The answer is: Every node's key is no larger than both of its children's keys

2.[2p]
In an array-based heap indexed from 0, what is the index of the parent of index 40?

CorrectNot quite: 19

3.[2p]
What is the index of the right child of index 12?

CorrectNot quite: 26

4.[2p]
A heap needs balancing machinery to keep its height at $⌊ \log_{2} n ⌋$ .

True

The answer is: False

False

Correct

5.[3p]
During sift-down, a node must be swapped with the smaller of its two children because

swapping with the larger one would leave it above its smaller sibling, breaking the property at once

Correct

the smaller child is always the left one

The answer is: swapping with the larger one would leave it above its smaller sibling, breaking the property at once

it halves the number of comparisons

The answer is: swapping with the larger one would leave it above its smaller sibling, breaking the property at once

otherwise the tree would stop being complete

The answer is: swapping with the larger one would leave it above its smaller sibling, breaking the property at once

6.[3p]
Building a heap costs at most $\frac{n}{2} \sum_{h \geq 0} h / 2^{h}$ swaps. What does that sum $\sum_{h \geq 0} h / 2^{h}$ converge to?

CorrectNot quite: 2

7.[3p]
Which of these are true of heapsort?

Select all that apply

It sorts in place and is guaranteed $Θ (n \log n)$

Correct

It makes about twice as many comparisons as mergesort

Correct

Its access pattern strides further with every level and misses the cache

Correct

It is stable

The answer is: It sorts in place and is guaranteed $\Theta(n\log n)$, It makes about twice as many comparisons as mergesort, Its access pattern strides further with every level and misses the cache

8.[3p]
Finding the 100 largest of a billion items with a size-100 min-heap costs about $n \log_{2} k$ operations. Give that count in billions.

CorrectNot quite: 6.6

9.[3p]
Match each priority queue implementation to the cost of extracting the minimum.

Unsorted array
Sorted array
Binary heap
Balanced search tree

$Θ (\log n)$
$Θ (\log n)$
$Θ (1)$
$Θ (n)$

Show the answer

Unsorted array: $Θ (n)$ Sorted array: $Θ (1)$ Binary heap: $Θ (\log n)$ Balanced search tree: $Θ (\log n)$

1.[2p] What is the heap property of a binary min-heap?

2.[2p] In an array-based heap indexed from 0, what is the index of the parent of index 40?

3.[2p] What is the index of the right child of index 12?

4.[2p] A heap needs balancing machinery to keep its height at ⌊log2n⌋.

5.[3p] During sift-down, a node must be swapped with the smaller of its two children because

6.[3p] Building a heap costs at most n2∑h≥0h/2h swaps. What does that sum ∑h≥0h/2h converge to?

7.[3p] Which of these are true of heapsort?

8.[3p] Finding the 100 largest of a billion items with a size-100 min-heap costs about nlog2k operations. Give that count in billions.

9.[3p] Match each priority queue implementation to the cost of extracting the minimum.

1.[2p]
What is the heap property of a binary min-heap?

2.[2p]
In an array-based heap indexed from 0, what is the index of the parent of index 40?

3.[2p]
What is the index of the right child of index 12?

4.[2p]
A heap needs balancing machinery to keep its height at $⌊ \log_{2} n ⌋$ .

5.[3p]
During sift-down, a node must be swapped with the smaller of its two children because

6.[3p]
Building a heap costs at most $\frac{n}{2} \sum_{h \geq 0} h / 2^{h}$ swaps. What does that sum $\sum_{h \geq 0} h / 2^{h}$ converge to?

7.[3p]
Which of these are true of heapsort?

8.[3p]
Finding the 100 largest of a billion items with a size-100 min-heap costs about $n \log_{2} k$ operations. Give that count in billions.

9.[3p]
Match each priority queue implementation to the cost of extracting the minimum.