Faangprep Logo
Log inStart free
Browse curriculum

Heaps (Priority Queue)

A heap is a specialized tree-based data structure that satisfies the heap property.

Min-heap — every parent is smaller than both children

Show

The array underneath

10

0

15

1

30

2

40

3

50

4

100

5

40

6

Children of index i live at 2i+1 and 2i+2; its parent is at floor((i−1)/2).

Intuition

In a normal queue, items are processed First-In-First-Out (FIFO). But what if some tasks are more important than others?

A Heap (or Priority Queue) is like a to-do list where you always pull the most important (Max-Heap) or smallest (Min-Heap) item first, regardless of when it was added.

Concept

Heap Property:

  • Max-Heap: Every parent node is greater than or equal to its children. The root is the maximum.
  • Min-Heap: Every parent node is smaller than or equal to its children. The root is the minimum.
  • Complete Binary Tree: The tree is completely filled, except possibly for the last level, which is filled from left to right.

How it Works

Heaps are usually implemented using an Array.

  • Root is at index 0.
  • Parent of i is floor((i-1)/2).
  • Left Child of i is 2*i + 1.
  • Right Child of i is 2*i + 2.

Step-by-Step Breakdown

1. Check Root. It's the extremum (min/max).
2. Navigate down using indices.
3. Verify Heap Property at each node.

When to Use

  • Priority Schedulers (OS tasks).
  • Dijkstra's Shortest Path algorithm.
  • Finding Top-K elements (e.g., K largest numbers).

When NOT to Use

  • Searching for an arbitrary element (O(N) time).
  • When strict FIFO/LIFO ordering is needed (use Queue/Stack).

How to Identify

"Get Max/Min efficiently", "Kth largest element", "Schedule tasks by priority".

Preparing for interviews? This topic is also taught as a pattern:

Heap Overview

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Introduction

Next

Heap Operations

Frequently Asked Questions

What is a Binary Heap?

A complete binary tree that satisfies the "Heap Property": in a Max Heap, every node is greater than or equal to its children; in a Min Heap, it is less than or equal.

Heap vs Binary Search Tree (BST)?

A BST is sorted horizontally (left < root < right). A Heap is sorted vertically (parent > child or parent < child) and MUST be a complete tree.

When to use a Heap?

When you need constant O(1) access to the maximum or minimum element in a shifting data set (Priority Queues).