What is a Binary Heap?
A binary heap is a complete binary tree, where the root is either the minimum value (min-heap) or the maximum value (max-heap).
This guide walks you through everything you need to know about the binary heap data structure, with clear, commented code samples.
- When to use a binary heap
- Big O time complexity of operations
- Pros and cons of binary heaps
- Implementing a heap
- Implement a min heap in Python
- Implement a max heap in Python
Binary Heap Properties:
- A complete binary tree
- To maintain heap order: Insert – Heapify Up, Extract – Heapify Down.
- Good for priority queues, shortest path, scheduling, etc.
- Left to right insertion
- Duplicates are allowed, unlike in a Binary Search Tree
Min-heap:
- Heap Property: Each node is smaller than its children
- Root is the minimum element in the tree
- Smallest key always at the front of a queue
- Able to extract min with O(1) time complexity
Max-heap:
- Heap Property: Each node is larger than its children
- Root is the maximum element in the tree
- Largest key always at the front of a queue
- Able to extract max with O(1) time complexity
When to Use a Binary Heap
Due to the heap property, and priority nature of heaps, they’re one of the best data structures to use in the following scenarios:
- Comparitive operations. e.g. Keep all values greater than X
- Priority Queues
Big O Time Complexity of Operations
Min-heap:
- Find min: O(1)
- Add item: O(log n) to heapify up
- Delete min: O(log n) to heapify down
Max-heap:
- Find max: O(1)
- Add item: O(log n) to heapify up
- Delete max: O(log n) to heapify down
For heap sort, the time complexity is O(n log n), as we’re performing the heapify n number of times.
Pros and Cons of Binary Heaps
Pros:
- Better than O(n) time complexity to retrieve min or max
- Structure supports prioritization
- Flexible size
- Fast insert
Cons:
- Slow lookup (slower than searching a BST)
Implementing a Heap
Following a few simple formulas, it’s possible to implement a heap using an array. By artificially creating a dummy value of 0 at index 0 of the array, it becomes simpler to perform the division operations needed to heapify.
With the assumption that we’re using a dummy value of 0 at index 0, the root value will appear at index 1. In this situation, the following formulas apply.
Move from a node’s index in the queue (n) to its:
- Parent: n // 2
- Left: n * 2
- Right: n * 2 + 1
We’ll now look at some of the main methods you’ll need to implement in a min heap class.
Main Methods
- find_min – Return the min
- insert – Adds the new item to the bottom right position, then calls heapify_up
- heapify_up – Swaps the bottom right item with its parent until heap property is restored
- delete_min – Swaps the min with the bottom right item in the heap. Deletes the bottom right item, then calls heapify_down
- heapify_down – Swaps the root with its smallest child until heap property is restored
Min-heap Operations
There are two basic operations to a min heap; insert and delete min (root). The logic behind each operation is outlined below. We’ll see how this translates into code later in the guide.
Insert:
- Insert the element at the bottom rightmost spot
- Swap the new element with its parent until it is larger than its parent
- This swapping operation is known as ‘heapify up’ or ‘percolate up’
Translating this into code, using our array, we need to append the new value, then percolate it up until it is smaller than its parent. If n is our new value, the parent we’re comparing against is the value at index position n // 2.
Delete Min:
- Swap the root with the bottom node
- Delete the bottom node
- Swap the root with its smallest child
- Repeat until both children are larger than the value being swapped, or we create a new child node
- This swapping operation is known as ‘heapify down’ or ‘percolate down’
Translating this into code, we need to swap the first value in the array with the last value, then pop the last value off. We then need to compare the root against the larger of the two children (values at n * 2 and n * 2 + 1) then swap with the larger of the two.
Max-heap Operations
Inserting into a max heap follows the same pattern as inserting to a min heap, except we now stop swapping if the inserted item is smaller than its parent.
Insert:
- Insert the element at the bottom rightmost spot
- Swap the new element with its parent until it is smaller than its parent, or becomes the new root
Delete Max:
- Swap the root with the bottom right node
- Delete the bottom right node
- Swap the root with its largest child
- Repeat until both children are smaller than the value being swapped, or we create a new child node
- This swapping operation is known as ‘heapify down’ or ‘percolate down’
Min Heap in Python
class MinHeap:
def __init__(self):
"""
Attributes:
heap: Initialize the heap array, with [0] at index 0.
size: Define the 'size' attribute for use in heapify functions.
"""
self.heap = [0]
self.size = 0
def insert(self, val):
"""Insert a new value to the binary heap.
Args:
val: The value being added to the heap.
"""
self.heap.append(val)
self.size += 1
self.__perc_up(self.size)
def __perc_up(self, i):
"""Percolate a newly inserted value up to its correct position."""
while i // 2 > 0:
if self.heap[i] < self.heap[i // 2]:
tmp = self.heap[i // 2]
self.heap[i // 2] = self.heap[i]
self.heap[i] = tmp
i = i // 2
def del_min(self):
"""Delete the minimum value from the binary heap.
Returns:
The value that was deleted if success, error message otherwise.
"""
if self.heap and self.size > 0:
retval = self.heap[1]
self.heap[1] = self.heap[self.size]
self.size -= 1
self.heap.pop()
self.__perc_down(1)
return retval
else:
return "Cannot delete from empty heap."
def __perc_down(self, i):
"""Percolate a value down to its correct position."""
while i * 2 <= self.size:
mc = self.__min_child(i * 2)
if self.heap[i] > self.heap[mc]:
tmp = self.heap[i]
self.heap[i] = self.heap[mc]
self.heap[mc] = tmp
i = mc
def __min_child(self, i):
"""Get the minimum child value for a given index 'i'."""
if i + 1 > self.size:
return i
else:
if self.heap[i] < self.heap[i + 1]:
return i
else:
return i + 1
def get_min(self):
"""Get the minimum value from the binary heap. Always at heap[1].
Returns:
The minimum value in the binary heap. Error message if no values.
"""
if self.heap and self.size > 0:
return self.heap[1]
return "No values exist in heap."
def view_heap(self):
"""Get the minimum value from the binary heap. Always at heap[1].
Returns:
The binary heap as a Python list.
"""
if self.heap and self.size > 0:
return self.heap[1:]
return []
Max Heap in Python
Most guides will only walk through how to create a min heap, as the steps to create a max heap are so similar.
Taking our min heap implementation as a base, we only need to reverse the comparison on lines 25, 55 and 67 to create a max heap.
class MaxHeap:
def __init__(self):
"""
Attributes:
heap: Initialize the heap array, with [0] at index 0.
size: Define the 'size' attribute for use in heapify functions.
"""
self.heap = [0]
self.size = 0
def insert(self, val):
"""Insert a new value to the binary heap.
Args:
val: The value being added to the heap.
"""
self.heap.append(val)
self.size += 1
self.__perc_up(self.size)
def __perc_up(self, i):
"""Percolate a newly inserted value up to its correct position."""
while i // 2 > 0:
if self.heap[i] > self.heap[i // 2]:
tmp = self.heap[i // 2]
self.heap[i // 2] = self.heap[i]
self.heap[i] = tmp
i = i // 2
def del_max(self):
"""Delete the maximum (root) value from the binary heap.
Returns:
The value that was deleted if success, error message otherwise.
"""
if self.heap and self.size > 0:
retval = self.heap[1]
self.heap[1] = self.heap[self.size]
self.size -= 1
self.heap.pop()
self.__perc_down(1)
return retval
else:
return "Cannot delete from empty heap."
def __perc_down(self, i):
"""Percolate a value down to its correct position."""
while i * 2 <= self.size:
mc = self.__max_child(i * 2)
if self.heap[i] < self.heap[mc]:
tmp = self.heap[i]
self.heap[i] = self.heap[mc]
self.heap[mc] = tmp
i = mc
def __max_child(self, i):
"""Get the maximum child value for a given index 'i'."""
if i + 1 > self.size:
return i
else:
if self.heap[i] > self.heap[i + 1]:
return i
else:
return i + 1
def get_max(self):
"""Get the maximum value from the binary heap. Always at heap[1].
Returns:
The maximum value in the binary heap. Error message if no values.
"""
if self.heap and self.size > 0:
return self.heap[1]
return "No values exist in heap."
def view_heap(self):
"""View the entire binary heap.
Returns:
The binary heap as a Python list.
"""
if self.heap and self.size > 0:
return self.heap[1:]
return []
