Insert the keys 5, 3, 8, 1, 9, 2 into an initially empty min-heap by push-ing one at a time. What is the resulting array layout (1-indexed by level), and which sift direction is each insert?

What is the time complexity of building a heap from an unsorted array of n elements using heapify (Floyd's bottom-up method), and why is it not O(n log n)?

Using Python's heapq (a min-heap), implement a function that returns the K smallest elements of a stream of size n in O(n log k) time.

Examples

Example 1:

Input: stream = [4, 2, 7, 1, 9, 3], k = 3
Output: [1, 2, 3]
Explanation: A max-heap of size 3 keeps the 3 smallest seen so far by evicting its root whenever a smaller value arrives. After scanning the stream the heap holds {1, 2, 3}, returned sorted.

Example 2:

Input: stream = [5, 1, 2], k = 0
Output: []
Explanation: k = 0 short-circuits to an empty result.

Given the array-backed heap below (1-indexed), what are the indices of the parent, left child, and right child of node i? Confirm with the indices of node 5.

Examples

Example 1:

Input: 1-indexed heap [_, 1, 3, 2, 5, 9, 8], node i = 5 (value 9)
Output: parent index = 2 (value 3); left child index = 10 (out of bounds); right child index = 11 (out of bounds)
Explanation: For a 1-indexed heap, parent(i) = i / 2, left(i) = 2 * i, right(i) = 2 * i + 1. Node 5's parent is at index 2 (value 3). The heap only has 6 elements, so indices 10 and 11 fall past the end.

Why does peek on a max-heap cost O(1) but extractMax cost O(log n)? Sketch the extractMax algorithm.