# Heaps & Priority Queue in DSA
A **Heap** is a specialized tree-based data structure that satisfies the **Heap Property** and is mainly used to implement **Priority Queues** and efficient sorting algorithms like **Heap Sort**.
It is one of the most frequently asked topics in DSA interviews.
* * *
## What is a Heap?
A heap is a **Complete Binary Tree**, which means:
* All levels are completely filled
* The last level is filled from left to right
Heaps are typically implemented using **arrays**, not pointer-based trees.
* * *
## Heap Property
There are two types of heaps:
### 🔹 Min-Heap
* Parent node is **smaller** than its children
* The smallest element is always at the root
### 🔹 Max-Heap
* Parent node is **greater** than its children
* The largest element is always at the root
In Python, the `heapq` module implements a **Min-Heap by default**.
* * *
# Array Representation of Heap
For a node at index `i` (0-based indexing):
* Left child → `2*i + 1`
* Right child → `2*i + 2`
* Parent → `(i - 1) // 2`
This is why heaps are implemented efficiently using arrays.
* * *
# Common Heap Operations & Time Complexity
| Operation | Time Complexity |
| --- | --- |
| Get Min/Max | O(1) |
| Insert | O(log n) |
| Remove Top | O(log n) |
| Heapify (Build Heap) | O(n) |
| Heap Sort | O(n log n) |
* * *
# Using Heap in Python (`heapq`)
* * *
## 1️⃣ Build Min Heap (Heapify)
Time: **O(n)**
Space: **O(1)** (in-place)
```python
import heapq
A = [-4, 3, 1, 0, 2, 5, 10, 8, 12, 9]
heapq.heapify(A) #O(n)
print(A)
```
`heapify()` converts a list into a valid heap in linear time.
⚡ Interview Insight:
Building a heap using repeated insertion takes O(n log n), but `heapify()` does it in O(n).
* * *
## 2️⃣ Insert into Heap
Time: **O(log n)**
```python
heapq.heappush(A, 4)
print(A)
```
* * *
## 3️⃣ Extract Minimum
Time: **O(log n)**
```python
min_val = heapq.heappop(A)
print(A, min_val)
```
* * *
## 4️⃣ Peek Minimum (Without Removing)
Time: **O(1)**
```python
A[0]
```
The smallest element is always at index `0`.
* * *
## 5️⃣ Heappush + Heappop Combined
Time: **O(log n)**
```python
heapq.heappushpop(A, 99)
print(A)
```
More efficient than doing push then pop separately.
* * *
# Heap Sort in Python
Time: **O(n log n)**
Space: **O(n)** (extra list used)
```python
def heapsort(arr):
heapq.heapify(arr)
result = []
while arr:
result.append(heapq.heappop(arr))
return result
print(heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0]))
```
⚠️ Note:
In-place heap sort with O(1) space is possible but more complex to implement manually.
* * *
# Max Heap in Python
Python does not directly support max-heap.
We simulate it by inserting negative values.
```python
B = [-4, 3, 1, 0, 2, 5, 10, 8, 12, 9]
# Convert to negative
B = [-x for x in B]
heapq.heapify(B)
largest = -heapq.heappop(B)
print(largest)
# Insert 7
heapq.heappush(B, -7)
```
⚡ Interview Tip:
This technique is very commonly used in competitive programming.
* * *
# Build Heap from Scratch (Using Insert)
Time: **O(n log n)**
```python
C = [-5, 4, 2, 1, 7, 0, 3]
heap = []
for x in C:
heapq.heappush(heap, x)
print(heap)
```
Repeated insertion is slower than heapify.
* * *
# Using Tuples in Heap
Heaps can store [tuples](https://yashrajxdev.blog/arrays-and-tuple-in-python).
Python compares tuples element by element.
Example: Frequency-based sorting.
```python
from collections import Counter
import heapq
D = [5, 4, 3, 5, 4, 3, 5, 5, 4]
counter = Counter(D)
heap = []
for key, value in counter.items():
heapq.heappush(heap, (value, key))
print(heap)
```
This is used in:
* Top K Frequent Elements
* Frequency Sorting
* Scheduling Problems
* * *
### Priority Queue vs Heap
A **Priority Queue** is an abstract data structure.
A **Heap** is one way to implement it efficiently.
Priority Queue ensures:
* Highest (or lowest) priority element is removed first.
* * *
# Median of Data Stream (Two Heaps Technique)
One of the most popular heap-based interview problems is:
> **Design a data structure that supports adding numbers and finding the median at any time.**
* * *
## Problem Statement
You continuously receive numbers from a data stream.
You must support two operations:
1. `addNum(num)` → Add a number
2. `findMedian()` → Return the median of all inserted numbers
* * *
***Why Sorting Every Time Is Not Good?***
If you sort the array every time:
* Insertion → O(1)
* Sorting → O(n log n)
* Finding median → O(1)
This is inefficient for large streams.
We need something better.
* * *
## Optimal Approach: Two Heaps
We use:
* 🔹 **Max Heap** → Stores the smaller half of numbers
* 🔹 **Min Heap** → Stores the larger half of numbers
### Why Two Heaps?
We divide numbers into two balanced halves:
```plaintext
Max Heap (left side) | Min Heap (right side)
Smaller numbers | Larger numbers
```
This ensures:
* Median is either:
* Top of one heap
* Or average of tops of both heaps
* * *
### Important Rules
1. Size difference between heaps should not exceed 1
2. All elements in max heap ≤ elements in min heap
* * *
## Python Implementation
Since Python only provides a **Min Heap**,
we simulate a **Max Heap** using negative values.
```python
import heapq
class MedianFinder:
def __init__(self):
self.small = [] # Max heap (invert values)
self.large = [] # Min heap
def addNum(self, num):
# Step 1: Push to max heap (invert value)
heapq.heappush(self.small, -num)
# Step 2: Ensure ordering property
if self.small and self.large and (-self.small[0] > self.large[0]):
value = -heapq.heappop(self.small)
heapq.heappush(self.large, value)
# Step 3: Balance sizes
if len(self.small) > len(self.large) + 1:
value = -heapq.heappop(self.small)
heapq.heappush(self.large, value)
if len(self.large) > len(self.small):
value = heapq.heappop(self.large)
heapq.heappush(self.small, -value)
def findMedian(self):
if len(self.small) > len(self.large):
return -self.small[0]
return (-self.small[0] + self.large[0]) / 2
```
* * *
### Time Complexity
| Operation | Time Complexity |
| --- | --- |
| addNum() | O(log n) |
| findMedian() | O(1) |
This is optimal.
* * *
### Example
Input Stream:
```plaintext
1 → median = 1
1, 2 → median = 1.5
1, 2, 3 → median = 2
1, 2, 3, 4 → median = 2.5
```
Heaps internally balance automatically.