How to Insert in Heap: Step-by-Step Guide

To insert in a heap, add the new element at the end of the heap (usually an array), then "bubble up" or "heapify up" to restore the heap property by swapping with its parent until the order is correct. This maintains the heap structure efficiently.

Syntax

Insertion in a heap involves two main steps:

• Add the element: Place the new element at the end of the heap array.
• Heapify up: Compare the new element with its parent and swap if needed, repeating until the heap property is restored.

javascript

function insert(heap, value) {
  heap.push(value); // Add at the end
  let index = heap.length - 1;
  while (index > 0) {
    let parentIndex = Math.floor((index - 1) / 2);
    if (heap[parentIndex] <= heap[index]) break; // Min-heap condition
    [heap[parentIndex], heap[index]] = [heap[index], heap[parentIndex]]; // Swap
    index = parentIndex;
  }
}

Example

This example shows inserting values into a min-heap represented as an array. After each insertion, the heap property is maintained by bubbling the new element up.

javascript

function insert(heap, value) {
  heap.push(value);
  let index = heap.length - 1;
  while (index > 0) {
    let parentIndex = Math.floor((index - 1) / 2);
    if (heap[parentIndex] <= heap[index]) break;
    [heap[parentIndex], heap[index]] = [heap[index], heap[parentIndex]];
    index = parentIndex;
  }
}

const heap = [];
insert(heap, 10);
insert(heap, 5);
insert(heap, 14);
insert(heap, 2);
console.log(heap);

Output

[2, 5, 14, 10]

Common Pitfalls

Common mistakes when inserting into a heap include:

• Not adding the new element at the end before heapifying up.
• Failing to correctly calculate the parent index.
• Not stopping the heapify up process when the heap property is restored.
• Mixing min-heap and max-heap conditions.

javascript

/* Wrong: swapping without checking heap property */
function wrongInsert(heap, value) {
  heap.push(value);
  let index = heap.length - 1;
  while (index > 0) {
    let parentIndex = Math.floor((index - 1) / 2);
    // Missing condition to stop swapping
    [heap[parentIndex], heap[index]] = [heap[index], heap[parentIndex]];
    index = parentIndex;
  }
}

/* Correct: stops when heap property is satisfied */
function correctInsert(heap, value) {
  heap.push(value);
  let index = heap.length - 1;
  while (index > 0) {
    let parentIndex = Math.floor((index - 1) / 2);
    if (heap[parentIndex] <= heap[index]) break;
    [heap[parentIndex], heap[index]] = [heap[index], heap[parentIndex]];
    index = parentIndex;
  }
}

Quick Reference

Heap Insertion Steps:

• Add element at the end of the heap array.
• Calculate parent index: parent = Math.floor((index - 1) / 2).
• Compare and swap if heap property is violated.
• Repeat until heap property is restored or root is reached.

Key Takeaways

Insert new elements at the end of the heap array before restoring order.

Use "heapify up" by swapping with parent until the heap property holds.

Correctly calculate parent index as (index - 1) divided by 2.

Stop heapify up when the parent is in correct order relative to the new element.

Be consistent with min-heap or max-heap rules during insertion.