A heap is a data structure that always gives you the smallest (or largest) element instantly. It powers priority queues, scheduling systems, and some of the most common interview patterns like “top K elements.” In this article, you will learn how heaps work, how to implement them, and how to use them in coding interviews.
We show every example in Kotlin, Python, and Go.
What is a Heap?
A heap is a complete binary tree that satisfies the heap property:
- Min-heap: every parent is smaller than or equal to its children. The root is the smallest element.
- Max-heap: every parent is larger than or equal to its children. The root is the largest element.
“Complete binary tree” means every level is fully filled except possibly the last level, which is filled from left to right.
Min-heap: Max-heap:
1 9
/ \ / \
3 5 7 8
/ \ / \
7 8 3 5
Why Use an Array?
Because a heap is a complete binary tree, we can store it efficiently in an array. No pointers needed. The parent-child relationship is defined by index math:
- Parent of index i:
(i - 1) / 2 - Left child of index i:
2 * i + 1 - Right child of index i:
2 * i + 2
For the min-heap above, the array is: [1, 3, 5, 7, 8]
Heap Operations
Insert (Push)
- Add the new element at the end of the array.
- Bubble up: compare it with its parent. If it is smaller (min-heap), swap them. Repeat until the heap property is restored.
Time complexity: O(log n) — at most we travel from the bottom to the root.
Extract Min/Max (Pop)
- The root is the answer (smallest or largest element).
- Replace the root with the last element in the array.
- Bubble down: compare the new root with its children. Swap with the smaller child (min-heap). Repeat until the heap property is restored.
Time complexity: O(log n).
Peek
Return the root element without removing it. Time complexity: O(1).
Building a Min-Heap from Scratch
Let’s implement a min-heap with an array.
Kotlin:
class MinHeap {
private val data = mutableListOf<Int>()
fun size() = data.size
fun peek() = data.first()
fun push(value: Int) {
data.add(value)
bubbleUp(data.size - 1)
}
fun pop(): Int {
val min = data[0]
val last = data.removeAt(data.size - 1)
if (data.isNotEmpty()) {
data[0] = last
bubbleDown(0)
}
return min
}
private fun bubbleUp(index: Int) {
var i = index
while (i > 0) {
val parent = (i - 1) / 2
if (data[i] < data[parent]) {
data[i] = data[parent].also { data[parent] = data[i] }
i = parent
} else break
}
}
private fun bubbleDown(index: Int) {
var i = index
while (2 * i + 1 < data.size) {
var smallest = 2 * i + 1
val right = 2 * i + 2
if (right < data.size && data[right] < data[smallest]) {
smallest = right
}
if (data[i] > data[smallest]) {
data[i] = data[smallest].also { data[smallest] = data[i] }
i = smallest
} else break
}
}
}
Python:
class MinHeap:
def __init__(self):
self.data = []
def size(self):
return len(self.data)
def peek(self):
return self.data[0]
def push(self, value):
self.data.append(value)
self._bubble_up(len(self.data) - 1)
def pop(self):
min_val = self.data[0]
last = self.data.pop()
if self.data:
self.data[0] = last
self._bubble_down(0)
return min_val
def _bubble_up(self, index):
while index > 0:
parent = (index - 1) // 2
if self.data[index] < self.data[parent]:
self.data[index], self.data[parent] = self.data[parent], self.data[index]
index = parent
else:
break
def _bubble_down(self, index):
while 2 * index + 1 < len(self.data):
smallest = 2 * index + 1
right = 2 * index + 2
if right < len(self.data) and self.data[right] < self.data[smallest]:
smallest = right
if self.data[index] > self.data[smallest]:
self.data[index], self.data[smallest] = self.data[smallest], self.data[index]
index = smallest
else:
break
Go:
type MinHeap struct {
data []int
}
func (h *MinHeap) Size() int { return len(h.data) }
func (h *MinHeap) Peek() int { return h.data[0] }
func (h *MinHeap) Push(value int) {
h.data = append(h.data, value)
h.bubbleUp(len(h.data) - 1)
}
func (h *MinHeap) Pop() int {
min := h.data[0]
last := h.data[len(h.data)-1]
h.data = h.data[:len(h.data)-1]
if len(h.data) > 0 {
h.data[0] = last
h.bubbleDown(0)
}
return min
}
func (h *MinHeap) bubbleUp(index int) {
for index > 0 {
parent := (index - 1) / 2
if h.data[index] < h.data[parent] {
h.data[index], h.data[parent] = h.data[parent], h.data[index]
index = parent
} else {
break
}
}
}
func (h *MinHeap) bubbleDown(index int) {
for 2*index+1 < len(h.data) {
smallest := 2*index + 1
right := 2*index + 2
if right < len(h.data) && h.data[right] < h.data[smallest] {
smallest = right
}
if h.data[index] > h.data[smallest] {
h.data[index], h.data[smallest] = h.data[smallest], h.data[index]
index = smallest
} else {
break
}
}
}
Heapify: Build a Heap in O(n)
You can build a heap from an unsorted array in O(n) time. The trick is to start from the last non-leaf node and bubble down each element. This is faster than inserting elements one by one (which takes O(n log n)).
Python:
def heapify(arr):
n = len(arr)
# Start from the last non-leaf node
for i in range(n // 2 - 1, -1, -1):
bubble_down(arr, i, n)
def bubble_down(arr, index, size):
while 2 * index + 1 < size:
smallest = 2 * index + 1
right = 2 * index + 2
if right < size and arr[right] < arr[smallest]:
smallest = right
if arr[index] > arr[smallest]:
arr[index], arr[smallest] = arr[smallest], arr[index]
index = smallest
else:
break
Using Built-in Priority Queues
In practice, you rarely implement a heap from scratch. Every major language has a built-in priority queue.
Python — heapq (min-heap by default):
import heapq
nums = [5, 3, 8, 1, 2]
heapq.heapify(nums) # Convert list to min-heap in O(n)
heapq.heappush(nums, 4) # Push a value
smallest = heapq.heappop(nums) # Pop the smallest: 1
# For max-heap, negate values:
max_heap = [-x for x in [5, 3, 8, 1, 2]]
heapq.heapify(max_heap)
largest = -heapq.heappop(max_heap) # 8
Kotlin — PriorityQueue (min-heap by default):
import java.util.PriorityQueue
val minHeap = PriorityQueue<Int>()
minHeap.add(5)
minHeap.add(3)
minHeap.add(8)
val smallest = minHeap.poll() // 3
// For max-heap, use reverseOrder:
val maxHeap = PriorityQueue<Int>(reverseOrder())
maxHeap.add(5)
maxHeap.add(3)
maxHeap.add(8)
val largest = maxHeap.poll() // 8
Go — container/heap (requires implementing the heap.Interface):
import (
"container/heap"
)
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
// Usage:
h := &IntHeap{5, 3, 8, 1, 2}
heap.Init(h)
heap.Push(h, 4)
smallest := heap.Pop(h).(int) // 1
Go’s heap interface requires more code, but it gives you full control over the comparison logic.
Interview Problem: Kth Largest Element
Given an array of integers and an integer k, return the kth largest element. This is LeetCode #215.
Strategy: Use a min-heap of size k. The root will always be the kth largest element.
Python:
import heapq
def find_kth_largest(nums, k):
min_heap = nums[:k]
heapq.heapify(min_heap)
for num in nums[k:]:
if num > min_heap[0]:
heapq.heapreplace(min_heap, num)
return min_heap[0]
# Example:
print(find_kth_largest([3, 2, 1, 5, 6, 4], 2)) # Output: 5
Kotlin:
import java.util.PriorityQueue
fun findKthLargest(nums: IntArray, k: Int): Int {
val minHeap = PriorityQueue<Int>()
for (num in nums) {
minHeap.add(num)
if (minHeap.size > k) {
minHeap.poll()
}
}
return minHeap.peek()
}
Go:
func findKthLargest(nums []int, k int) int {
h := &IntHeap{}
heap.Init(h)
for _, num := range nums {
heap.Push(h, num)
if h.Len() > k {
heap.Pop(h)
}
}
return (*h)[0]
}
Time complexity: O(n log k). Space complexity: O(k).
Interview Problem: Top K Frequent Elements
Given an array and an integer k, return the k most frequent elements. This is LeetCode #347.
Strategy: Count frequencies with a hash map, then use a min-heap of size k.
Python:
import heapq
from collections import Counter
def top_k_frequent(nums, k):
count = Counter(nums)
return heapq.nlargest(k, count.keys(), key=count.get)
print(top_k_frequent([1, 1, 1, 2, 2, 3], 2)) # Output: [1, 2]
Kotlin:
import java.util.PriorityQueue
fun topKFrequent(nums: IntArray, k: Int): List<Int> {
val count = mutableMapOf<Int, Int>()
for (num in nums) count[num] = count.getOrDefault(num, 0) + 1
val minHeap = PriorityQueue<Int>(compareBy { count[it] })
for (key in count.keys) {
minHeap.add(key)
if (minHeap.size > k) minHeap.poll()
}
return minHeap.toList()
}
Go:
// FreqHeap is a min-heap of [2]int{frequency, number}
type FreqHeap [][2]int
func (h FreqHeap) Len() int { return len(h) }
func (h FreqHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h FreqHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *FreqHeap) Push(x interface{}) { *h = append(*h, x.([2]int)) }
func (h *FreqHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
func topKFrequent(nums []int, k int) []int {
count := make(map[int]int)
for _, num := range nums {
count[num]++
}
h := &FreqHeap{}
heap.Init(h)
for num, freq := range count {
heap.Push(h, [2]int{freq, num})
if h.Len() > k {
heap.Pop(h)
}
}
result := make([]int, h.Len())
for i := len(result) - 1; i >= 0; i-- {
result[i] = heap.Pop(h).([2]int)[1]
}
return result
}
Time Complexity Summary
| Operation | Time |
|---|---|
| Insert (push) | O(log n) |
| Extract min/max (pop) | O(log n) |
| Peek | O(1) |
| Heapify (build heap) | O(n) |
| Search | O(n) |
Why Interviewers Ask Heap Questions
Heap questions test:
- Knowing when to use a heap — recognizing “top K,” “kth largest/smallest,” or “merge K” patterns
- Understanding trade-offs — why a heap is better than sorting the entire array for top K problems
- Priority queue usage — can you use your language’s built-in heap correctly?
Practice Problems
Try these on LeetCode:
- Kth Largest Element in an Array (#215) — min-heap of size k
- Top K Frequent Elements (#347) — frequency map + heap
- Merge K Sorted Lists (#23) — push all list heads into a heap
- Find Median from Data Stream (#295) — two heaps: max-heap + min-heap
- Last Stone Weight (#1046) — max-heap simulation
What’s Next?
In the next article, we cover Graphs — one of the most versatile data structures in computer science. You will learn adjacency lists, BFS, DFS, cycle detection, and topological sort.
Next: DSA Tutorial #7: Graphs — Representation, BFS, and DFS
Full series: DSA from Zero to Interview Ready