Course contentsShow
← Computer Science
Lesson 587 of 2,87214. Heaps and Priority QueuesFree lesson

Implementing Heap Insert

Step-by-step implementation of insert operation with index calculations for parent navigation.

Implementing Heap Insert

What you'll learn: You'll learn how to code the insertion operation for a binary heap using index arithmetic to navigate the array-based tree structure.

The Core Mechanism

When inserting a new element into a heap, you add it at the next available position (maintaining the complete binary tree property), then "bubble it up" by repeatedly swapping with its parent until the heap order property is restored. The key is using the parent-child index formulas you've already learned.

Step-by-Step Implementation

Given an array-based heap with the next insertion index n:

  1. Place the new value at index n (the next open spot)
  2. Set current index i = n
  3. Calculate parent index: parent = (i - 1) // 2 (integer division)
  4. Compare heap[i] with heap[parent]
  5. If heap order violated (e.g., in a min-heap, child < parent):
    • Swap heap[i] and heap[parent]
    • Set i = parent
    • Repeat from step 3
  6. Stop when heap order is satisfied or you reach the root (i == 0)

Example (Min-Heap)

Inserting 5 into heap [10, 15, 20, 30, 25]:

  • Place 5 at index 5: [10, 15, 20, 30, 25, 5]
  • Parent of index 5 is (5-1)//2 = 2 (value 20)
  • 5 < 20, so swap: [10, 15, 5, 30, 25, 20]
  • Now at index 2, parent is (2-1)//2 = 0 (value 10)
  • 5 < 10, so swap: [5, 15, 10, 30, 25, 20]
  • At index 0 (root), stop

Key Takeaway: Heap insert uses the parent formula (i - 1) // 2 to bubble the new element upward through swaps until the heap order property is satisfied, maintaining both shape and order invariants.