AlgorithmsHeap & Priority Queue

📚 Heap & Priority Queue

Master the heap data structure: min/max heaps, heap sort, priority queues, and their applications in algorithms.

Overview

ℹ️

What is a Heap?

A heap is a complete binary tree where each node is ≤ (min-heap) or ≥ (max-heap) its children. Heaps efficiently maintain the minimum or maximum element. Used for priority queues, heap sort, and top-k problems.

Key Heap Algorithms

Min Heap Operations

Build and operate on min heap (smallest element on top)

Time: O(log n) push/popSpace: O(n)

Max Heap Operations

Build and operate on max heap (largest element on top)

Time: O(log n) push/popSpace: O(n)

Heap Sort

Sort array using heap data structure

Time: O(n log n)Space: O(1)

Kth Largest Element

Find kth largest element in array efficiently

Time: O(n log k)Space: O(k)

Merge K Sorted Lists

Merge k sorted linked lists into one sorted list

Time: O(n log k)Space: O(k)

Interactive Visualizer

Heap Visualization

📚

Min Heap Operations Heap Visualizer

Watch elements bubble up and down during heap operations, maintaining the heap property.

Deep Dive: Min Heap Operations

Time Complexity

Time: O(log n) push/pop

Space Complexity

Space: O(n)

Heap Property

Parent ≤ Children

💡

How It Works

Push: Add element at end, bubble up until heap property restored. Pop: Remove root, move last element to root, bubble down. Root is always smallest.

python

import heapq

# Min heap (default in Python)
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
smallest = heapq.heappop(heap)  # 3

# Build heap from list
nums = [5, 3, 7, 1, 9]
heapq.heapify(nums)
# nums is now [1, 3, 7, 5, 9]

Initialize Heap

Create empty heap or heapify existing array in O(n).

Push/Pop

Add elements with heappush, remove with heappop. Both O(log n).

Access Root

Read heap[0] for minimum (min-heap) or maximum (max-heap with negatives).

Maintain Size

For top-k problems, keep heap at size k, always removing smallest (min-heap) or largest (max-heap).

Real-World Applications

Priority Queues

Task scheduling with priorities, Dijkstra's algorithm

Median Finding

Maintain running median with two heaps (min + max)

Top K Elements

Find top K frequent elements using min-heap of size k

CPU Scheduling

Process scheduling based on priority levels

Event Simulation

Discrete event simulation with timestamps as priorities

Data Compression

Huffman coding uses min-heap to build optimal prefix tree

Interview Questions

How is heap different from binary search tree?

Heap: parent is min/max of subtree, no ordering between siblings. BST: left < root < right for all nodes. Heap: O(log n) min/max access. BST: O(log n) any value search.

What is heapify and why is it O(n)?

Heapify builds a heap from an unsorted array in O(n). It applies bubble-down from the last non-leaf node to root. Most elements are near leaves and need few swaps, giving O(n) total.

How would you find median of streaming data?

Use two heaps: max-heap for left half, min-heap for right half. Maintain size difference ≤1. Median is root of larger heap or average of both roots. O(log n) per insert.

Knowledge Check

1. What is the time complexity of heap push?

2. How do you implement max heap in Python?

3. What is heapify time complexity?

4. Time complexity of Heap Sort?

5. What is space complexity of finding Kth largest with heap?

What's Next?

Advanced Topics

Continue your learning: