Introduction to Heaps Resource

Introduction to Heaps Resource - aloalgo

A heap is a tree-based data structure that satisfies the heap property. It's commonly used to implement a priority queue, where you need quick access to the minimum or maximum element.

Imagine you need to repeatedly find and remove the smallest (or largest) element from a collection. Common scenarios:

Find the K largest elements in a stream
Process tasks by priority
Find the median of a data stream
Merge K sorted lists efficiently

An array can find the min in O(n), but a heap does it in O(1) and maintains order after removals in O(log n).

A heap is a complete binary tree where each parent satisfies the heap property relative to its children. "Complete" means every level is fully filled except possibly the last, which is filled from left to right. This structure guarantee is what allows heaps to be stored as a flat array with no wasted space and no need for explicit pointers between nodes.The array representation uses simple arithmetic to navigate the tree. Given a node at index i, its parent is at index (i - 1) // 2, its left child is at 2 * i + 1, and its right child is at 2 * i + 2. This compact representation makes heaps very cache-friendly compared to pointer-based tree implementations.

Min-heap: Every parent is smaller than or equal to its children. The root is the minimum.Max-heap: Every parent is larger than or equal to its children. The root is the maximum.

Operation	Array	Sorted Array	Heap
Get min/max	O(n)	O(1)	O(1)
Insert	O(1)	O(n)	O(log n)
Remove min/max	O(n)	O(1)	O(log n)

Heaps provide the best balance for problems requiring frequent min/max access with insertions. A sorted array gives O(1) access to the min or max but O(n) insertions because elements must be shifted. A regular unsorted array gives O(1) insertion but O(n) for finding the min or max. The heap provides O(log n) for both operations, making it ideal for dynamic data where elements are continuously added and removed.

Insert (push): Add the new element at the end of the array (maintaining the complete tree property), then "bubble up" by swapping it with its parent repeatedly until the heap property is restored. This takes O(log n) time because the tree height is log n.Extract min/max (pop): Remove the root element (the min or max), move the last element to the root position, then "bubble down" by swapping it with the smaller (or larger) child until the heap property is restored. This also takes O(log n) time.

Kth Largest Element: Maintain a min-heap of size K
Merge K Sorted Lists: Use a heap to track the smallest element across lists
Find Median from Data Stream: Use two heaps (min and max)
Task Scheduler: Process highest priority tasks first

Was this helpful?

Study plan All problems

Resources Cheat Sheet DSA Glossary

Introduction to Heaps

What Problem Does a Heap Solve?

Heap Structure

The Heap Property

Why Use a Heap?

How Heap Operations Work

Common Interview Problems

Company

Practice

Learn