Heap Insert (Bubble Up)

Intuition

Think of a company org chart with one rule: every manager earns more than the people who report directly to them. A new hire always joins at the first open seat on the bottom level. If they negotiated a salary higher than their manager's, the two swap seats, and the check repeats one level up until the newcomer reports to someone who earns more, or becomes the CEO. That climb is bubble-up, also called sift-up or swim.

A max-heap only promises that each parent is at least as large as its children, so the largest value sits at the root. It says nothing about the order between siblings or cousins. That weak promise is cheap to maintain: one insert touches only the nodes on a single root-to-leaf path, and a complete binary tree with n nodes has height about log2 n.

Array index math

Because the tree is complete (every level full except possibly the last, which fills left to right) it can be stored level by level in an array with no pointers. With 0-based indexing, the node at index i has its parent at (i - 1) / 2 using integer division, its left child at 2 * i + 1 and its right child at 2 * i + 2. Some textbooks use 1-based arrays where the formulas become i / 2, 2 * i and 2 * i + 1; pick one and stay consistent. The last element is always at index size - 1, which is the next free leaf position minus one.

How insert works step by step

1. If the backing array is full, grow it (for example by doubling).
2. Write the new value at index size and increment size. The shape is still a complete tree, but the order property may be broken at that one position.
3. Let i be the new index. Compute parent = (i - 1) / 2.
4. If i > 0 and heap[parent] < heap[i], swap them and set i = parent.
5. Repeat step 4 until the parent is at least as large or i reaches 0, the root.
6. Peek is now just heap[0], an O(1) read of the maximum.

Dry run: inserting 45 then 60

Start from the valid max-heap [50, 30, 40, 10, 20, 35]. Root 50 has children 30 and 40; 30 has children 10 and 20; 40 has child 35.

The second insert is the worst case: a new maximum climbs the full height of the tree. Even then it only touched indices 7, 3, 1 and 0, four positions out of eight. Removing the maximum from this exact heap is the starting point of the Extract-Max and sift-down lesson.

Code

import java.util.Arrays;
import java.util.NoSuchElementException;

public class MaxHeap {
    private int[] heap = new int[8];
    private int size = 0;

    public void insert(int value) {
        if (size == heap.length) heap = Arrays.copyOf(heap, size * 2);
        heap[size] = value;
        bubbleUp(size);
        size++;
    }

    // Shift smaller parents down instead of swapping; place the value once at the end.
    private void bubbleUp(int i) {
        int value = heap[i];
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (heap[parent] >= value) break;
            heap[i] = heap[parent];
            i = parent;
        }
        heap[i] = value;
    }

    public int peek() {
        if (size == 0) throw new NoSuchElementException("heap is empty");
        return heap[0];
    }

    public int size() { return size; }
}

class MaxHeap:
    def __init__(self):
        self.a = []

    def push(self, value):
        a = self.a
        a.append(value)               # new leaf at index len(a) - 1
        i = len(a) - 1
        while i > 0:
            parent = (i - 1) // 2
            if a[parent] >= a[i]:
                break
            a[parent], a[i] = a[i], a[parent]
            i = parent

    def peek(self):
        if not self.a:
            raise IndexError("peek from empty heap")
        return self.a[0]


h = MaxHeap()
for x in [50, 30, 40, 10, 20, 35, 45, 60]:
    h.push(x)
print(h.a)        # [60, 50, 45, 30, 20, 35, 40, 10]
print(h.peek())   # 60

# The standard library heap is a min-heap; negate values for max-heap behaviour.
import heapq
pq = []
for x in [5, 1, 8]:
    heapq.heappush(pq, -x)
print(-pq[0])     # 8

The Java version uses the hole technique: it moves parents down into the gap and writes the new value once, which halves the number of array writes compared with swapping. In Java production code you would normally reach for PriorityQueue with Collections.reverseOrder() for a max-heap.

Time and space complexity

Edge cases

• First insert into an empty heap: index 0, no parent, the loop never runs.
• Duplicates: use >= (stop when the parent is equal) so equal values do not swap pointlessly.
• Inserting a value smaller than every existing one: zero swaps; it stays as a leaf.
• Array growth: in a fixed-capacity heap, decide whether a full heap throws or evicts, as in top-K problems.
• Integer.MIN_VALUE in Java: negating it to simulate a max-heap overflows; prefer a reverse comparator.

Common mistakes

• Using i / 2 as the parent in a 0-based array. For index 2 that gives 1, but the real parent is 0.
• Bubbling down after an insert instead of up. Insert repairs upward; removal repairs downward.
• Forgetting that Python's heapq and Java's default PriorityQueue are min-heaps.
• Assuming the array is sorted. Only the root is guaranteed; [60, 50, 45, 30, 20, 35, 40, 10] is a valid heap but not sorted.
• Comparing with the sibling during bubble-up. Only the parent matters on the way up.

Variations and when to use it

Any time data arrives over time and you repeatedly need the current largest or smallest item, a heap with O(log n) insert is the tool: event schedulers, streaming top-K, running medians with two heaps, and Dijkstra's frontier. A min-heap is identical with the comparison flipped. A bounded heap of size k keeps the k largest values seen so far by using a min-heap and popping whenever it grows past k. If you plan to insert everything up front and then remove in order, building the heap in one pass and repeatedly extracting is exactly Heap Sort.

Related LeetCode problems

• #215 Kth Largest Element in an Array — push into a size-k min-heap; its root is the answer.
• #2336 Smallest Number in Infinite Set — added-back numbers are inserted into a min-heap alongside a counter.
• #703 Kth Largest Element in a Stream — every add is a heap insert plus an optional pop to keep size k.
• #295 Find Median from Data Stream — insert into one of two heaps and rebalance so their roots straddle the median.
• #347 Top K Frequent Elements — insert (frequency, value) pairs into a bounded heap.
• #1834 Single-Threaded CPU — tasks are inserted into a heap as their start time arrives.

FAQ