How to Delete from Heap: Simple Steps and Example

To delete from a heap, replace the element to delete with the last element in the heap, remove the last element, then restore the heap property by heapify (sift down or sift up). This ensures the heap remains a valid min-heap or max-heap after deletion.

Syntax

Deleting an element from a heap involves these steps:

• Replace the target element with the last element in the heap.
• Remove the last element (now duplicated).
• Heapify the heap to restore the heap property by sifting the replaced element down or up.

This process maintains the heap's structure and order.

javascript

function deleteFromHeap(heap, index) {
  // Replace element at index with last element
  heap[index] = heap[heap.length - 1];
  heap.pop();

  // Restore heap property by sifting down
  heapifyDown(heap, index);
}

function heapifyDown(heap, index) {
  let left = 2 * index + 1;
  let right = 2 * index + 2;
  let smallest = index;

  if (left < heap.length && heap[left] < heap[smallest]) {
    smallest = left;
  }
  if (right < heap.length && heap[right] < heap[smallest]) {
    smallest = right;
  }

  if (smallest !== index) {
    [heap[index], heap[smallest]] = [heap[smallest], heap[index]];
    heapifyDown(heap, smallest);
  }
}

Example

This example shows how to delete the root element (minimum) from a min-heap represented as an array.

javascript

function deleteFromHeap(heap, index) {
  heap[index] = heap[heap.length - 1];
  heap.pop();
  heapifyDown(heap, index);
}

function heapifyDown(heap, index) {
  let left = 2 * index + 1;
  let right = 2 * index + 2;
  let smallest = index;

  if (left < heap.length && heap[left] < heap[smallest]) {
    smallest = left;
  }
  if (right < heap.length && heap[right] < heap[smallest]) {
    smallest = right;
  }

  if (smallest !== index) {
    [heap[index], heap[smallest]] = [heap[smallest], heap[index]];
    heapifyDown(heap, smallest);
  }
}

// Initial min-heap array
let heap = [2, 5, 3, 10, 7];
console.log('Before deletion:', heap);

// Delete root element (index 0)
deleteFromHeap(heap, 0);
console.log('After deletion:', heap);

Output

Before deletion: [2,5,3,10,7]
After deletion: [3,5,7,10]

Common Pitfalls

Common mistakes when deleting from a heap include:

• Not replacing the deleted element with the last element, which breaks the heap structure.
• Forgetting to heapify after deletion, causing the heap property to be violated.
• Using only sift down or only sift up without checking which is needed.

Always replace, remove last, then restore heap property properly.

javascript

function wrongDelete(heap, index) {
  // Incorrect: just remove element without replacement
  heap.splice(index, 1);
  // Heap property is broken now
}

// Correct way is shown in previous example

Quick Reference

Steps to delete from a heap:

• Replace target with last element
• Remove last element
• Heapify down (or up if needed)

This keeps the heap valid and efficient.

Key Takeaways

Always replace the element to delete with the last heap element before removing it.

Restore the heap property by heapifying down or up after deletion.

Skipping heapify breaks the heap structure and order.

Deleting from a heap is efficient because it avoids full reordering.

Use sift down for min-heap deletion starting at the replaced index.