Easy Heap Operations Heaps
In plain English: Turn an unsorted list into a heap structure so the smallest element is always on top.
Bottom-up heapify sifts each non-leaf node down — this is O(n) because most nodes are near the bottom and barely need to move.
Prompt
Convert an arbitrary array into a min-heap in-place using heapq.heapify.
Try to write it from scratch before scrolling down.
Solution
import heapq
def heapify_demo(a):
heapq.heapify(a) # O(n) in-place conversion
return a
# Test: a = [5, 3, 8, 1, 2]; heapify_demo(a); a[0] == 1
# Test: a = [9, 4, 7, 1, 3]; heapify_demo(a); a[0] == 1
def nsmallest_demo(a, k):
heapq.heapify(a)
return [heapq.heappop(a) for _ in range(k)]
# Test: nsmallest_demo([5,3,8,1,2], 3) == [1, 2, 3]