Heaps & Priority Queues — Chapter Quiz · Data Structures & Algorithms

Question 1

1

Which two properties together define a valid binary max-heap?

ASorted order and O(1) random accessBShape property (complete binary tree) and heap property (parent ≥ both children)CBST property (left < root < right) and balanced heightDAll leaves at the same depth and root holds the minimum

A heap must be a complete binary tree (shape property) so it can be stored compactly in an array. The heap property (parent ≥ children for a max-heap) ensures the maximum is always at the root.

Question 2

2

In an array-backed binary heap, if a node is at index i (0-indexed), where are its children?

A2i and 2i + 1B2i + 1 and 2i + 2Ci + 1 and i + 2Di / 2 and i / 2 + 1

With 0-indexed arrays the left child of node i is at 2i + 1 and the right child at 2i + 2. The parent of node i is at Math.floor((i - 1) / 2).

Question 3

3

What is the time complexity of building a heap from an unsorted array of n elements using Floyd's algorithm (the heapify-all approach)?

AO(n log n)BO(n²)CO(n)DO(log n)

Floyd's build-heap calls sift-down on each non-leaf, starting from the last internal node. The total work sums to O(n) because most nodes are near the bottom and sift-down costs O(h) per node — not O(log n) on average.

Question 4

4

What is the most efficient approach to find the top k largest elements in an unsorted array of n elements?

ASort the array (O(n log n)) and slice the last k elementsBMaintain a min-heap of size k: iterate the array, pushing each element, and pop when the heap exceeds size kCInsert all elements into a max-heap then pop k times: O(n + k log n)DUse two binary searches to find the kth largest

A size-k min-heap keeps the k largest seen so far. Each push/pop is O(log k). Total: O(n log k), which beats O(n log n) when k ≪ n. The heap root is the kth largest element at the end.

Question 5

5

The two-heap technique for finding the running median uses:

ATwo min-heaps of equal sizeBA max-heap for the lower half and a min-heap for the upper half, kept balanced in sizeCTwo sorted arrays merged on each queryDA single max-heap with a pointer to the median position

The max-heap top gives the largest of the lower half; the min-heap top gives the smallest of the upper half. The median is the average of both tops (even count) or the top of the larger heap (odd count). Each insertion is O(log n).

Question 6

6

Inserting a new element into a heap (sift-up) always takes O(log n) time in the worst case.

TTrueFFalse

The new element is placed at the next available leaf position. It may need to bubble up through O(log n) levels until the heap property is restored. Each level requires one comparison and one swap.

Question 7

7

A heap can be used to implement a ___ queue, a data structure that always dequeues the element with the highest (or lowest) priority.

The heap root always holds the extreme element (max or min). Dequeue pops the root (O(log n)) and enqueue inserts a new element (O(log n)), making heaps the natural backing structure for priority queues.

Question 8

8

Which operations run in O(log n) on a binary heap? (Select all that apply)

Select all that apply.

AInsert (push)BExtract-max / Extract-minCPeek at the max/min elementDDecrease-key (update an existing element)

Insert (sift-up) and extract (sift-down) are both O(log n). Decrease-key requires sifting the updated element up or down — also O(log n) with an index map. Peeking at the root is O(1).

Test what you learned.

Heaps — Chapter Quiz