Insert the given values one at a time into an initially empty min-heap (stored as an array), and return the final heap array. Implement the sift-up yourself.
heapInsert(values)
The array layout: index 0 is the root; node i has parent (i-1)/2, children 2i+1
and 2i+2.
Input format: space-separated values to insert in order. Output the heap array.
insert 5, 3, 8, 1 // → [1, 3, 8, 5]
insert 1, 2, 3 // → [1, 2, 3]
insert 4 // → [4]
A min-heap answers one question fast, repeatedly: what's the smallest value right now? A fully sorted array answers that too, but keeping it sorted after every insertion is expensive — inserting into the middle means shifting everything after it, O(n) per insertion.
A heap trades full ordering for cheap insertion. It only guarantees one weaker property — every parent is less than or equal to both children — and doesn't care how children compare to each other or how far-apart elements relate. That weaker guarantee is what makes it fast to maintain.
The heap is conceptually a binary tree, but stored compactly in an array: node i has children at 2i+1 and 2i+2, parent at (i-1)/2. Since the tree is always kept complete (filled level by level, left to right, no gaps), a new element always appends at the end and lands in a known tree position — no pointer rewiring.
A complete tree's height is always about log₂(n) — doubling the elements adds one level. Sifting up walks from a leaf toward the root, touching at most one node per level — O(log n), far cheaper than O(n) array shifting.
This stays correct because sifting up only fixes the single path from the new leaf to the root — every other parent-child relationship was already valid, and the new element only disturbs its own ancestors. Restore order along one path, not everywhere.
The cost: the array isn't sorted. Finding the minimum is O(1) (always the root), but finding the 5th smallest or checking membership isn't efficient. A heap is specialized — great at repeated insert-and-extract-extreme, poor at general queries.
def heap_insert(values):
heap = []
for v in values:
heap.append(v)
i = len(heap) - 1
while i > 0:
parent = (i - 1) // 2
if heap[parent] <= heap[i]:
break
heap[parent], heap[i] = heap[i], heap[parent]
i = parent
return heap
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.