ReviseAlgo Logo

Heaps & Priority Queues

Heap Fundamentals

Master Heap foundations: complete binary tree properties, array index mappings, and Min-Heap vs Max-Heap invariants.

Last Updated: August 2, 2026 • 15 min read

1. Introduction

What is a Binary Heap?

A Binary Heap is a specialized, partially-ordered binary tree that satisfies two criteria: 1. Shape Property: It is a complete binary tree (all levels are completely filled except possibly the last level, which is filled from left to right). 2. Heap Property: The value of each node is compared relative to its children: - In a Min-Heap, parent keys are ≤ their children's keys. The smallest key is at the root. - In a Max-Heap, parent keys are ≥ their children's keys. The largest key is at the root.

Why is it Important?

Heaps allow you to find the minimum or maximum element in O(1) time and insert or delete elements in O(log N) time. Unlike binary search trees, heaps can be stored efficiently in contiguous arrays without any pointer memory overhead.

Where is it Used?

  • Priority Queues: Backing priority queues to dispatch tasks by importance.
  • Graph Algorithms: Finding shortest paths using Dijkstra's algorithm.

    • 2. Mental Model: The Corporate Hierarchy

    Think of a Max-Heap as a strict corporate reporting structure:

  • The CEO sits at the root peak and receives the highest salary.
  • Each manager reports to a supervisor who makes at least as much money as they do.
  • Individual contributors report to managers who earn more than them.
  • Partially Ordered: There is no rule comparing salaries across different departments (e.g. the left subtree and right subtree have no sorted ordering relative to each other). We only care about vertical parent-child lines of command.

    • 3. Core Array Representation Invariants

    Because a heap is a complete binary tree, we can map its nodes directly into a single 1D array. For any node stored at index i (0-indexed):

  • Parent: (i - 1) / 2 (using integer division)
  • Left Child: 2 i + 1
  • Right Child: 2 i + 2

    • Parent-Child Index Helper Functions

    4. Visualizing Array to Tree Mapping

    Below is the mapping trace showing how a Min-Heap tree layout aligns with index indices:

    5. Real-World Examples

  • Operating System Task Triager: Schedulers assigning higher priority execution slots to CPU processes.
  • Bandwidth Traffic Shapers: Router queues prioritizing real-time VoIP audio packets over background file downloads.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test index arithmetic:
  • "Given an array, verify if it represents a valid Min-Heap." -> Loop through the array from 0 to (N - 2) / 2. Check if data[i] <= data[2i + 1] and (if present) data[i] <= data[2i + 2].
  • "Why are heaps preferred over sorted arrays to implement Priority Queues?" -> Inserting into a sorted array takes O(N) shift operations. Heaps insert in O(log N) time, offering superior scaling.

    • Common Mistakes

    Warning: 1. Assuming Heaps are Sorted: A common mistake is assuming that a heap's array representation is sorted. It is not. For example, [10, 30, 15] is a valid Min-Heap, but 30 appears before 15 in the array.
    > 2. Index Bounds Overflow: Attempting to read child indices 2i + 1 or 2i + 2 without checking if these values are less than the active size of the array.

    7. Summary

  • Shape Property: Heap is a complete binary tree.
  • Representation: Stored in a flat 1D array using arithmetic child indices.
  • Min-Heap: Parent ≤ children. Max-Heap: Parent ≥ children.
  • Complexities: Peek takes O(1) time; search takes O(N) time (since there is no horizontal sorting).

    • 8. Quiz

    Question 1: What is the index of the parent of a node stored at index 9? Answer: 4. Calculated as (9 - 1) / 2 = 8 / 2 = 4.
    Question 2: What is the left child index of a node stored at index 3? Answer: 7. Calculated as 2 * 3 + 1 = 6 + 1 = 7.
    Question 3: Why does heap search take O(N) time? Answer: Because heaps only enforce vertical relationships (parent-child), not horizontal ones. Left and right subtrees have no sorted relationship. To find an arbitrary element, you must perform a full linear scan of the array.
    Question 4: True or False: Every sorted array in descending order represents a valid Max-Heap. Answer: True. Since the array is sorted in descending order, any element at index i is guaranteed to be larger than or equal to subsequent elements, satisfying the parent >= children Max-Heap property.
    Question 5: What is the maximum height of a binary heap of size N? Answer: \lfloor log_2 N \rfloor. Because a heap is a complete binary tree, its height is guaranteed to scale logarithmically.