ReviseAlgo Logo

Heaps & Priority Queues

Heap Operations & HeapSort

Master Heap operations: bubble-up, bubble-down, O(N) heapify construction, and in-place HeapSort.

Last Updated: August 2, 2026 • 15 min read

1. Introduction

What are Heap Operations & HeapSort?

  • Heap Operations are the procedural updates used to manipulate heaps: insert (adding elements), extract (removing the root), and heapify (converting an arbitrary array into a valid heap).
  • HeapSort is a comparison-based sorting algorithm that uses a Binary Heap to sort elements in-place.

    • Why study them?

    Knowing how to implement these algorithms is crucial. It tests your ability to manipulate array structures representing virtual binary trees, balance shape vs value invariants, and optimize sorting.

    Where is it Used?

  • Priority Schedulers: Dynamically queuing and retrieving tasks by priority.
  • In-Place Sorting: Sorting systems with strictly constrained memory footprints.

    • 2. Mental Models

    Bubble-Up (Sift-Up): Rising Helium Balloon

    Imagine a helium balloon released at the bottom of the tree:
  • If its value is smaller than its parent (in a Min-Heap), it rises by swapping positions with the parent.
  • It continues rising vertically until it reaches a parent with a smaller value or hits the root.

    • Bubble-Down (Sift-Down): Sinking Stone

    Imagine a heavy stone dropped at the root:
  • It sinks down by swapping positions with its smaller child.
  • It continues sinking until both children are larger than it or it hits the leaf level.

    • 3. Core Algorithms & Implementations

    Insertion (Bubble-Up)

    1. Append the new element at the end of the array (maintaining the complete tree shape). 2. Compare the element with its parent. If it violates the heap property, swap them. 3. Repeat step 2 recursively moving up. Takes O(log N) time.

    Extraction (Bubble-Down)

    1. Replace the root element with the last element in the array. 2. Remove the last element (shrinking the active array size). 3. Compare the new root with its children. Swap with the smaller child (for Min-Heap) or larger child (for Max-Heap) if the property is violated. 4. Repeat step 3 recursively moving down. Takes O(log N) time.

    Heapify (O(N) Construction)

    Instead of inserting N elements one-by-one (which takes O(N log N)), we can construct a heap in O(N) time:
  • Start from the last non-leaf node at index (N/2 - 1) and work backwards to index 0, running siftDown at each step.
  • Proof of O(N): Nodes near the bottom of the tree have very small heights and only sift down a few levels. The majority of nodes reside at these lower levels, bounding the sum of heights to O(N) operations.

    • 4. Visual Trace: Sift-Down Extraction

    Extracting root 40 from Max-Heap [40, 15, 30, 10]:

    5. Real-World Examples

  • Priority Job Executors: Processing threads pulling high-importance tasks from priority queues dynamically.
  • Embedded Sort Packages: Microcontrollers utilizing in-place HeapSort due to lack of extra stack/RAM buffers.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test structural knowledge:
  • "Why does building a heap from an array take O(N) time instead of O(N log N)?" -> Explain that sift-down height complexity is proportional to node height. The mathematical sum of heights in a complete tree bounds operations to linear O(N) time.
  • "What are the trade-offs of HeapSort vs MergeSort?" -> HeapSort is in-place (O(1) auxiliary space), whereas MergeSort takes O(N) space. However, HeapSort is unstable and has poor cache locality.

    • Common Mistakes

    Warning: 1. Implementing Heapify with Sift-Up: Building a heap by calling siftUp from index 0 to N takes O(N log N) time. You must use siftDown working backwards from N/2 - 1 to achieve O(N) time.
    > 2. Wrong Swap Targets: During sift-down, swapping with the wrong child. In a Max-Heap, you must swap with the larger child. Swapping with the smaller child violates the heap property.

    7. Summary

  • Sift-Up (Bubble-Up): Used during insertions to restore properties bottom-up.
  • Sift-Down (Bubble-Down): Used during extractions to restore properties top-down.
  • Heapify: Linear O(N) construction sifting down from N/2 - 1 backwards.
  • HeapSort: In-place O(N log N) sorting utilizing max-heaps.

    • 8. Quiz

    Question 1: Why does HeapSort use a Max-Heap to sort an array in ascending order? Answer: Because we swap the root (which is the maximum element) with the last element of the active array. This places the largest elements at the end of the array first, sorting it in ascending order in-place.
    Question 2: What is the last non-leaf node index in an array of size 10? Answer: 4. Calculated as 10 / 2 - 1 = 5 - 1 = 4.
    Question 3: What is the worst-case space complexity of HeapSort? Answer: O(1) auxiliary space, since sorting is performed entirely in-place by swapping elements inside the input array.
    Question 4: True or False: HeapSort is a stable sorting algorithm. Answer: False. Heap operations involve long-distance swaps across child and parent indices, which can change the relative order of duplicate elements.
    Question 5: What is the maximum number of swaps performed during a heap insertion in a heap of size N? Answer: \lfloor log_2 N \rfloor swaps, since the element can bubble up at most from leaf level to root.