Introduction

Deletion in a heap is different from deletion in a binary search tree. A heap is optimized for quickly accessing the highest-priority element, not for searching arbitrary positions by key.

Because of that, the usual delete operation removes the root and then restores the heap property. If you want to remove an element at some other index, the process is similar but you must first know where that element is stored.

What Delete Means in a Heap

In a max heap, the root is the largest element. In a min heap, the root is the smallest. Removing that root is efficient because the data structure is already organized around it.

The standard algorithm is:

1. Save the root value.
2. Move the last element in the array to the root position.
3. Shrink the heap by one element.
4. Sift the new root down until the heap property is restored.

This runs in O(log n) time because the replacement element travels down at most one tree height.

A Runnable Max-Heap Example

The code below stores the heap in a Python list. That keeps the implementation compact and makes the parent and child indices easy to compute.

1class MaxHeap:
2    def __init__(self):
3        self.data = []
4
5    def push(self, value):
6        self.data.append(value)
7        self._sift_up(len(self.data) - 1)
8
9    def delete_max(self):
10        if not self.data:
11            raise IndexError("heap is empty")
12
13        max_value = self.data[0]
14        last = self.data.pop()
15
16        if self.data:
17            self.data[0] = last
18            self._sift_down(0)
19
20        return max_value
21
22    def delete_at(self, index):
23        if index < 0 or index >= len(self.data):
24            raise IndexError("index out of range")
25
26        removed = self.data[index]
27        last = self.data.pop()
28
29        if index < len(self.data):
30            self.data[index] = last
31            parent = (index - 1) // 2
32
33            if index > 0 and self.data[index] > self.data[parent]:
34                self._sift_up(index)
35            else:
36                self._sift_down(index)
37
38        return removed
39
40    def _sift_up(self, index):
41        while index > 0:
42            parent = (index - 1) // 2
43            if self.data[parent] >= self.data[index]:
44                break
45            self.data[parent], self.data[index] = self.data[index], self.data[parent]
46            index = parent
47
48    def _sift_down(self, index):
49        size = len(self.data)
50
51        while True:
52            left = 2 * index + 1
53            right = 2 * index + 2
54            largest = index
55
56            if left < size and self.data[left] > self.data[largest]:
57                largest = left
58            if right < size and self.data[right] > self.data[largest]:
59                largest = right
60
61            if largest == index:
62                break
63
64            self.data[index], self.data[largest] = self.data[largest], self.data[index]
65            index = largest
66
67
68heap = MaxHeap()
69for value in [20, 12, 18, 7, 9, 15]:
70    heap.push(value)
71
72print(heap.data)
73print(heap.delete_max())
74print(heap.data)
75print(heap.delete_at(2))
76print(heap.data)

That program shows both common forms of deletion. The first call removes the maximum element. The second removes whatever is currently stored at index 2.

Deleting an Arbitrary Value

People often ask how to delete "the value 15" from a heap. The answer is that a heap does not support fast arbitrary search. If you do not know the index, you usually have to scan the array to find it, which costs O(n).

After you find the index, the repair step is still O(log n), but the total operation becomes O(n) because of the search.

If you frequently need both:

• fast priority access
• fast deletion by key

then a plain heap may not be enough on its own. A common improvement is to maintain a map from key to heap index so lookups are faster. That adds bookkeeping because every swap must update the map as well.

Why the Last Element Is Moved First

The heap is stored as a complete binary tree. Removing an interior element without backfilling its position would break that shape property. Moving the last element into the gap preserves the complete-tree layout, and then a sift step restores ordering.

Sometimes the replacement element should move up, and sometimes it should move down. That is why delete_at in the example checks the parent before choosing _sift_up or _sift_down.

Common Pitfalls

• Assuming heap deletion means deleting any value efficiently. Efficient deletion is guaranteed only when the index is known.
• Forgetting to restore the heap property after replacing the removed element.
• Always sifting down after an arbitrary delete. Sometimes the replacement element belongs above its parent.
• Confusing a heap with a sorted array. A heap only guarantees local parent-child ordering.
• Failing to handle the single-element case, which is simpler than the general algorithm.

Summary

• Root deletion in a heap is an O(log n) operation.
• The standard method is replace-with-last, then sift.
• Deleting by arbitrary value usually needs an O(n) search first.
• For indexed deletion, decide whether to sift up or down after replacement.
• Use a heap when priority access matters, not when arbitrary lookup is the main operation.