Heap Deletion

Given a valid min-heap stored as an array, remove the minimum (the root) and return the resulting heap array. Implement the sift-down yourself.

heapDelete(heap)

Removing the root: move the last element to index 0, drop the last slot, then sift the new root down by swapping with its smaller child until the heap property holds.

Input format: the heap array (a valid min-heap). Output the heap after one removal.

Examples

[1, 3, 8, 5]   // → [3, 5, 8]
[1]            // → []
[2, 4, 3]      // → [3, 4]

Walkthrough

Thinking it through

A min-heap's whole point is the smallest element sits at the root, readable in O(1). The hard part: once you remove the root, what fills the hole, and how do you restore order cheaply?

Why not just shift everything?

Removing the root and shifting every remaining element up a slot (like deleting the first element of a plain array) would scramble parent/child relationships completely and cost O(n).

The actual trick: move the last element into the gap

Take the last element (the most recently added leaf), drop it into the empty root position, shrink the array by one — O(1), no shifting. This new root is essentially random, so the heap property is very likely broken at the top.

Restoring order: sift down

Repair just the one spot that's wrong:

Look at the current node's children.
Find the smaller child.
If that child is less than the current node, swap them.
Move to that child's position and repeat.
Stop when the node is smaller than or equal to both children, or it has no children.

This walks the misplaced value down a single path, swapping below anything smaller, until it settles. Everything else in the tree was already valid — only one path needs fixing, mirroring insertion.

Why this is efficient

The tree stays complete, so its height is about log₂(n). Sift-down touches at most one node per level — O(log n), far better than re-sorting or shifting. Notice the trade with a sorted array: sorted gives O(1) minimum removal but O(n) insertion. A heap trades a slightly costlier lookup structure for O(log n) on both insertion and deletion — a better balance when you're repeatedly inserting and removing.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.