"""Binary Heap. A min heap is a complete binary tree where each node is smaller thanits children. The root, therefore, is the minimum element in the tree. The minheap uses an array to represent the data and operation. For example a min heap:
A binary heap is a special data structure that resembles a binary tree. It differs in the sense that the root of any subtree should be the smallest or the largest element.
There are two main types of heaps.
Minheap – In a minheap, the root of every subtree is the smallest element.
Maxheap – In a maxheap, the root of every subtree is the largest element.
In this article, let’s take a look at heaps and dive into programming heaps in Python.
For more background on the different types of data structures in Python, check out the following articles:
Note: Prerequisites – Make sure you have basic Python knowledge before diving into this article. It also might be a good idea to check out some linear data structures. (links are given above)
Table of Contents
Heaps: Introduction
Heaps are complete binary trees. Complete binary trees satisfy the following conditions:
All levels are filled, except the last.
All the nodes are as far left as possible.
Heaps satisfy the heap property. This means that the root of every subtree should be the greatest or smallest element in the subtree, recursively.
Applications of Heaps
Priority Queues can be implemented using heaps. The root of a heap always contains the maximum or the minimum value, based on the heap type. Therefore, a min-priority queue is implemented using a minheap. A max-priority queue is implemented using a maxheap. The element with the highest priority can be retrieved in O(1) time.
Statistics – If we want to get ordered statistics, heaps serve as a great choice. If we want the kth smallest or largest element, we can pop the heap k times to retrieve them.
Heaps are used in implementing various graph algorithms like and
Implementing a Heap
Heap Operations
A heap has the following methods:
getMax()
This operation returns the root of the maxheap.
Time Complexity - O(1).
Maxheap using List
We are going to do the list implementation of a heap. In this, the heap’s level-order traversal would be stored as an array/list.
Note - Level-Order Traversal is a recursive traversal where the root is processed first, followed by the children of the root. This is followed by the grandchildren of the root until all the nodes are processed. In the diagram above, the root node is processed first, followed by the left child, right child and so on. The final level order traversal would be: 10 4 8 50 24 5 12 18. For an overview of what a level order traversal is, check out Quora page.
In the array representation of a heap, for an element in array index i,
The Parent Node would be at position floor((i-1)/2).
The Left Child would be at position 2*i + 1.
The Right Child would be at position 2*i + 2.
Let us first define the Heap class.
This initiates a heap as a list. Now, let us define our methods.
Minheap using Heapq
We have successfully implemented a heap using a list. Now, let’s use the heapq library in Python to implement a minheap.
A heap is one common implementation of . A priority queue contains items with some priority. You can always take an item out in the priority order from a priority queue. It is important to take an item out based on the priority. When you look around poster presentations at an academic conference, it is very possible you have set in order to pick some presentations. Or you will make a priority list before you go sight-seeing (In this case, an item will be a tourist spot.). A stack and a queue also contain items. You can take an item out from a stack if the item is the last one added to the stack. This is first in, last out (FILO). As for a queue, you can take an item out from the queue if this item is the first one added to the queue. This is first in, first out (FIFO). You can regard these as a specific type of a priority queue. This is because the priority of an inserted item in stack increases and the priority of an inserted item in a queue decreases.
class MaxHeap:
def __init__(self):
self.heap = []
class MaxHeap:
def __init__(self):
# Initialize a heap using list
self.heap = []
def getParentPosition(self, i):
# The parent is located at floor((i-1)/2)
return int((i-1)/2)
def getLeftChildPosition(self, i):
# The left child is located at 2 * i + 1
return 2*i+1
def getRightChildPosition(self, i):
# The right child is located at 2 * i + 2
return 2*i+2
def hasParent(self, i):
# This function checks if the given node has a parent or not
return self.getParentPosition(i) < len(self.heap)
def hasLeftChild(self, i):
# This function checks if the given node has a left child or not
return self.getLeftChildPosition(i) < len(self.heap)
def hasRightChild(self, i):
# This function checks if the given node has a right child or not
return self.getRightChildPosition(i) < len(self.heap)
def insert(self, key):
self.heap.append(key) # Adds the key to the end of the list
self.heapify(len(self.heap) - 1) # Re-arranges the heap to maintain the heap property
def getMax(self):
return self.heap[0] # Returns the largest value in the heap in O(1) time.
def heapify(self, i):
while(self.hasParent(i) and self.heap[i] > self.heap[self.getParentPosition(i)]): # Loops until it reaches a leaf node
self.heap[i], self.heap[self.getParentPosition(i)] = self.heap[self.getParentPosition(i)], self.heap[i] # Swap the values
i = self.getParentPosition(i) # Resets the new position
def printHeap(self):
print(self.heap) # Prints the heap
import heapq
class MinHeap:
def __init__(self, minheap): # minheap is the list that we can to convert to a heap
heapq.heapify(minheap) # Use the heapify function to convert list to a heap
self.minheap = minheap
def insert(self, key):
heapq.heappush(self.minheap, key) # Insert key into the heap (heapq automatically maintains the heap property)
def getMin(self):
return self.minheap[0] # Returns the smallest element of the heap in O(1) time
def removeMin(self):
heapq.heappop(self.minheap) # The heappop function removes the smallest element in the heap
def printHeap(self):
print(self.minheap) # Prints the heap
2. Representation
A heap is one of the tree structures and represented as a binary tree. I put the image of heap below. You can implement a tree structure by a pointer or an array. In this post, I choose to use the array implementation like below. In terms of space complexity, the array implementation has more benefits than the pointer implementation. The indices of the array correspond to the node number in the below image.
The heap above is called a min heap, and each value of nodes is less than or equal to the value of child nodes. We call this condition the heap property.
In a min heap, when you look at the parent node and its child nodes, the parent node always has the smallest value. When a heap has an opposite definition, we call it a max heap. For the following discussions, we call a min heap a heap.
You can access a parent node or a child nodes in the array with indices below.
A root node｜i = 1, the first item of the array
A parent node｜parent(i) = i / 2
A left child node｜left(i) = 2i
A right child node｜right(i)=2i+1
When you look at the node of index 4, the relation of nodes in the tree corresponds to the indices of the array below.
The parent node corresponds to the item of index 2 by parent(i) = 4 / 2 = 2. The child nodes correspond to the items of index 8 and 9 by left(i) = 2 * 2 = 4, right(i) = 2 * 2 + 1 = 5, respectively.
3. The way how to build a heap
You need two operations to build a heap from an arbitrary array.
min_heapify｜make some node and its descendant nodes meet the heap property.
build_min_heap｜produce a heap from an arbitrary array.
We can build a heap by applying min_heapify to each node repeatedly.
3.1 min_heapify
In min_heapify, we exchange some nodes with its child nodes to satisfy the heap property under these two features below;
Some node and its child nodes don’t satisfy the heap property,
That child nodes and its descendant nodes satisfy the property.
A tree structure has the two features below.
Look at the nodes surrounded by the orange square. We find that 9 is larger than both of 2 and 3, so these three nodes don’t satisfy the heap property (The value of node should be less than or equal to the values of its child nodes). Please check the orange nodes below.
However, look at the blue nodes. These nodes satisfy the heap property.
Here we define min_heapify(array, index). This method takes two arguments, array, and index. We assume this method exchange the node of array[index] with its child nodes to satisfy the heap property.
Let’s check the way how min_heapify works by producing a heap from the tree structure above. First, we call min_heapify(array, 2) to exchange the node of index 2 with the node of index 4.
After apply min_heapify(array, 2) to the subtree, the subtree changes below and meets the heap property. This subtree colored blue.
If the subtree exchanged the node of index 2 with the node of index5, the subtree won’t meet the heap property like below. So the subtree exchange the node has the smallest value in the subtree with the parent node to satisfy the heap property.
Get back to the tree correctly exchanged. When we look at the orange nodes, this subtree doesn’t satisfy the heap property.
So call min_heapify(array, 4) to make the subtree meet the heap property.
Now, this subtree satisfies the heap property by exchanging the node of index 4 with the node of index 8.
These operations above produce the heap from the unordered tree (the array).
3.2 build_min_heap
The pseudo-code below stands for how build_min_heap works.
This function iterates the nodes except the leaf nodes with the for-loop and applies min_heapify to each node. We don’t need to apply min_heapify to the items of indices after n/2+1, which are all the leaf nodes. We apply min_heapify in the orange nodes below.
Each node can satisfy the heap property with meeting the conditions to be able to apply min_heapfiy. This is because this function iterates the nodes from the bottom (the second last level) to the top (the root node level). For instance, this function first applies min_heapify to the nodes both of index 4 and index 5 and then applying min_heapify to the node of index 2. So the node of the index and its descendent nodes satisfy the heap property when applying min_heapify.
4. Time complexity
Let’s think about the time complexity of build_min_heap. First of all, we think the time complexity of min_heapify, which is a main part of build_min_heap.
min_heapify repeats the operation of exchanging the items in an array, which runs in constant time. So the time complexity of min_heapify will be in proportional to the number of repeating. In the worst case, min_heapify should repeat the operation the height of the tree times. This is because in the worst case, min_heapify will exchange the root nodes with the most depth leaf node. Assuming h as the height of the root node, the time complexity of min_heapify will take O(h) time.
The time complexities of min_heapify in each depth are shown below. The number of the nodes is also showed in right.
From the figure, the time complexity of build_min_heap will be the sum of the time complexity of inner nodes. The final time complexity becomes:
So we should know the height of the tree to get the time complexity.
The sum of the number of nodes in each depth will become n. So we will get this equation below.
The equation above stands for the geometric sequence, so we can deform it and get the height of the tree as follow:
Finally, we get O(n) as the time complexity of build_min_heap. Also, we get O(logn) as the time complexity of min_heapify.
5. Implementation
Here we implement min_heapify and build_min_heap with Python. the implementation of min_heapify will be as follow.
First, this method computes the node of the smallest value among the node of index i and its child nodes and then exchange the node of the smallest value with the node of index i. When the exchange happens, this method applies min_heapify to the node exchanged.
Index of a list (an array) in Python starts from 0, the way to access the nodes will change as follow.
The root node｜i = 0
The parent node｜parent(i) = (i-1) / 2
The left child node｜left(i) = 2i + 1
The right child node｜right(i)=2i+2
The variable, smallest has the index of the node of the smallest value. If the smallest doesn’t equal to the i, which means this subtree doesn’t satisfy the heap property, this method exchanges the nodes and executes min_heapify to the node of the smallest.
The implementation of build_min_heap is almost the same as the pseudo-code.
The for-loop differs from the pseudo-code, but the behavior is the same. This for-loop also iterates the nodes from the second last level of nodes to the root nodes.
6. Heapsort
Heapsort is one sort algorithm with a heap. It’s really easy to implement it with min_heapify and build_min_heap. The flow of sort will be as follow. Please note that the order of sort is ascending.
Build a heap from an arbitrary array with build_min_heap.
Swap the first item with the last item in the array.
Remove the last item from the array.
Run min_heapify to the first item.
Back to step 2.
In a heap, the smallest item is the first item of an array. The array after step 3 satisfies the conditions to apply min_heapify because we remove the last item after we swap the first item with the last item. By this nature, we can sort an array by repeating steps 2 to 4.
The implementation of heapsort will become as follow.
The time complexity of heapsort is O(n_log_n) because in the worst case, we should repeat min_heapify the number of items in array times, which is n.
In the heapq module of Python, it has already implemented some operation for a heap. I followed the method in MIT’s lecture, the implementation differs from Python’s. If you’d like to know Python’s detail implementation, please visit the source code here. For example, these methods are implemented in Python.
heapq.heapify | corresponds to build_min_heap
heapq.heapop | corresponds to swapping items, remove the last item, and min_heapify at once.
classBinaryHeap{constructor(){this.heap = []}insert(value){this.heap.push(value)this.heapify()}size(){returnthis.heap.length}empty(){returnthis.size() ===0} // using iterative approach to reorder the heap after insertionheapify(){let index =this.size() -1while (index >0) {constelement=this.heap[index]constparentIndex=Math.floor((index -1) /2)constparent=this.heap[parentIndex]if (parent[0] >= element[0]) breakthis.heap[index] = parentthis.heap[parentIndex] = element index = parentIndex}} // Extracting the maximum element from the HeapextractMax(){constmax=this.heap[0]consttmp=this.heap.pop()if (!this.empty()) {this.heap[0] = tmpthis.sinkDown(0)}return max} // To restore the balance of the heap after extraction.sinkDown(index){constleft=2* index +1constright=2* index +2let largest = indexconstlength=this.size()if (left < length &&this.heap[left][0] >this.heap[largest][0]) { largest = left}if (right < length &&this.heap[right][0] >this.heap[largest][0]) { largest = right} // swapif (largest !== index) {consttmp=this.heap[largest]this.heap[largest] =this.heap[index]this.heap[index] = tmpthis.sinkDown(largest)}}}constmaxHeap=newBinaryHeap()maxHeap.insert([4])maxHeap.insert([3])maxHeap.insert([6])maxHeap.insert([1])maxHeap.insert([8])maxHeap.insert([2])while (!maxHeap.empty()) {constmx=maxHeap.extractMax()console.log(mx)}
/* Minimum Priority Queue
* It is a part of heap data structure
* A heap is a specific tree based data structure
* in which all the nodes of tree are in a specific order.
* that is the children are arranged in some
* respect of their parents, can either be greater
* or less than the parent. This makes it a min priority queue
* or max priority queue.
*/
// Functions: insert, delete, peek, isEmpty, print, heapSort, sink
class MinPriorityQueue {
// calls the constructor and initializes the capacity
constructor (c) {
this.heap = []
this.capacity = c
this.size = 0
}
// inserts the key at the end and rearranges it
// so that the binary heap is in appropriate order
insert (key) {
if (this.isFull()) return
this.heap[this.size + 1] = key
let k = this.size + 1
while (k > 1) {
if (this.heap[k] < this.heap[Math.floor(k / 2)]) {
const temp = this.heap[k]
this.heap[k] = this.heap[Math.floor(k / 2)]
this.heap[Math.floor(k / 2)] = temp
}
k = Math.floor(k / 2)
}
this.size++
}
// returns the highest priority value
peek () {
return this.heap[1]
}
// returns boolean value whether the heap is empty or not
isEmpty () {
return this.size === 0
}
// returns boolean value whether the heap is full or not
isFull () {
if (this.size === this.capacity) return true
return false
}
// prints the heap
print () {
console.log(this.heap.slice(1))
}
// heap sorting can be done by performing
// delete function to the number of times of the size of the heap
// it returns reverse sort because it is a min priority queue
heapSort () {
for (let i = 1; i < this.capacity; i++) {
this.delete()
}
}
// this function reorders the heap after every delete function
sink () {
let k = 1
while (2 * k <= this.size || 2 * k + 1 <= this.size) {
let minIndex
if (this.heap[2 * k] >= this.heap[k]) {
if (2 * k + 1 <= this.size && this.heap[2 * k + 1] >= this.heap[k]) {
break
} else if (2 * k + 1 > this.size) {
break
}
}
if (2 * k + 1 > this.size) {
minIndex = this.heap[2 * k] < this.heap[k] ? 2 * k : k
} else {
if (
this.heap[k] > this.heap[2 * k] ||
this.heap[k] > this.heap[2 * k + 1]
) {
minIndex =
this.heap[2 * k] < this.heap[2 * k + 1] ? 2 * k : 2 * k + 1
} else {
minIndex = k
}
}
const temp = this.heap[k]
this.heap[k] = this.heap[minIndex]
this.heap[minIndex] = temp
k = minIndex
}
}
// deletes the highest priority value from the heap
delete () {
const min = this.heap[1]
this.heap[1] = this.heap[this.size]
this.heap[this.size] = min
this.size--
this.sink()
return min
}
}
// testing
const q = new MinPriorityQueue(8)
q.insert(5)
q.insert(2)
q.insert(4)
q.insert(1)
q.insert(7)
q.insert(6)
q.insert(3)
q.insert(8)
q.print() // [ 1, 2, 3, 5, 7, 6, 4, 8 ]
q.heapSort()
q.print() // [ 8, 7, 6, 5, 4, 3, 2, 1 ]
build_min_heap(array)
for i=n/2 downto 1
do min_heapify(array, i)
def min_heapify(array, i):
left = 2 * i + 1
right = 2 * i + 2
length = len(array) - 1
smallest = i if left <= length and array[i] > array[left]:
smallest = left
if right <= length and array[smallest] > array[right]:
smallest = right
if smallest != i:
array[i], array[smallest] = array[smallest], array[i]
min_heapify(array, smallest)
def build_min_heap(array):
for i in reversed(range(len(array)//2)):
min_heapify(array, i)
import heapqdef heapsort(array):
h = array.copy()
heapq.heapify(h)
return [heapq.heappop(h) for _ in range(len(array))]
"""
Heaps (priority queues)
"""
# the maximum number of items that can be stored in the heap
CAPACITY = 10
"""
*** Max Heap ***
----------------
"""
# define the heap class
class Heap(object):
def __init__(self):
# create array with as many slots as the CAPACITY
self.heap = [0] * CAPACITY
# track the size of the heap (the number of items in the heap)
self.heap_size = 0
# insertion takes O(1) running time BUT we have to make sure that hte
# heap properties are not violated (it takes O(logN) because of the
# fixUp() method)
def insert(self, item):
# if the heap is at CAPACITY already we can not insert any more items
if CAPACITY == self.heap_size:
return
# insert the item at the index of the size of the heap (the last
# empty spot) and then increment the counter
self.heap[self.heap_size] = item
self.heap_size += 1
# after insert check to see if the heap properties were violated and
# if so fix them
self.fix_up(self.heap_size - 1)
# we consider the last item and check whether swaps are needed or not
# running time O(logN)
def fix_up(self, index):
# get the parent index of the given node in the heap
parent_index = (index - 1) // 2
# while the index > 0 means until we consider all the items "above"
# the one we inserted we have to swap the node with the parent if the
# heap property is violated
# this is a MAX HEAP: largest items are in the higher layers (max
# item == root node)
if index > 0 and self.heap[index] > self.heap[parent_index]:
self.swap(index, parent_index)
# run the check again after the swap on the parent
self.fix_up(parent_index)
# Get max, return the root node. Because this is a max heap the root is
# the max item. Because this is an array it takes O(1) time
# this is the peek() method
def get_max(self):
return self.heap[0]
# Get poll, returns the max item and also REMOVES the item from the heap
# note: we just dont care about that item anymore but because we have an
# array with fixed size we aren't able to get rid of it completely
# O(logN) running time
def poll(self):
max = self.get_max()
# first swap the first item with the last item
self.swap(0, self.heap_size - 1)
# then decrement the heap size ( excludes the last item from the heap
# going forward thus 'removing it')
self.heap_size = self.heap_size - 1
# nex check if the heap properties have been violated and if so fix
# them ( fix down is similar to fix up but works from the root down )
self.fix_down(0)
# finally return the max item removed
return max
# fix down, we have a given item in the heap and we consider all the
# items below and check whether the heap properties are violated or not
def fix_down(self, index):
# every node has 2 children so in the array the node i has left child
# with index *i+1 and right child with index 2*i+2
index_left = 2 * index + 1
index_right = 2 * index + 2
# this is a max heap so the parent is always greater than the children
index_largest = index
# if the left child is greater than the parent: largest is the left node
if index_left < self.heap_size and self.heap[index_left] > self.heap[
index]:
index_largest = index_left
# figure out if the left child or right child is the greater one
# first check if the given index is valid ( not larger than the heap
# size)
# if the right child is greater than the left child: largest is the
# right node
if index_right < self.heap_size and self.heap[index_right] > \
self.heap[index_largest]:
index_largest = index_right
# we don't want to swap items with themselves
if index != index_largest:
self.swap(index, index_largest)
# recursively check down the tree for any other heap violations
# and fix them as needed
self.fix_down(index_largest)
# we have N items and we want to sort them with a heap
# every poll operation takes O(logN) time because of the fix down
# method thats why the overall running time is O(NlogN) for heapsort
def heap_sort(self):
# we decrease the size of hte heap in the poll method so we have to
# store it
size = self.heap_size
for i in range(0, size):
max = self.poll()
print(max)
# swap two items with (index1, index2) in the heap array
def swap(self, index1, index2):
self.heap[index2], self.heap[index1] = self.heap[index1], self.heap[index2]
heap = Heap()
heap.insert(10)
heap.insert(8)
heap.insert(12)
heap.insert(20)
heap.insert(-2)
heap.insert(0)
heap.insert(1)
heap.insert(321)
heap.heap_sort()
# Implements a min-heap. For max-heap, simply reverse all comparison orders.
#
# Note on alternate subroutine namings (used in some textbooks):
# - _bubble_up = siftdown
# - _bubble_down = siftup
def _bubble_up(heap, i):
while i > 0:
parent_i = (i - 1) // 2
if heap[i] < heap[parent_i]:
heap[i], heap[parent_i] = heap[parent_i], heap[i]
i = parent_i
continue
break
def _bubble_down(heap, i):
startpos = i
newitem = heap[i]
left_i = 2 * i + 1
while left_i < len(heap):
# Pick the smaller of the L and R children
right_i = left_i + 1
if right_i < len(heap) and not heap[left_i] < heap[right_i]:
child_i = right_i
else:
child_i = left_i
# Break if heap invariant satisfied
if heap[i] < heap[child_i]:
break
# Move the smaller child up.
heap[i], heap[child_i] = heap[child_i], heap[i]
i = child_i
left_i = 2 * i + 1
def heapify(lst):
for i in reversed(range(len(lst) // 2)):
_bubble_down(lst, i)
def heappush(heap, item):
heap.append(item)
_bubble_up(heap, len(heap) - 1)
def heappop(heap):
if len(heap) == 1:
return heap.pop()
min_value = heap[0]
heap[0] = heap[-1]
del heap[-1]
_bubble_down(heap, 0)
return min_value
# Example usage
heap = [3, 2, 1, 0]
heapify(heap)
print('Heap(0, 1, 2, 3):', heap)
heappush(heap, 4)
heappush(heap, 7)
heappush(heap, 6)
heappush(heap, 5)
print('Heap(0, 1, 2, 3, 4, 5, 6, 7):', heap)
sorted_list = [heappop(heap) for _ in range(8)]
print('Heap-sorted list:', sorted_list)
# Large test case, for randomized tests
import random
# Heapify 0 ~ 99
heap = list(range(100))
random.shuffle(heap)
heapify(heap)
# Push 100 ~ 199 in random order
new_elems = list(range(100, 200))
random.shuffle(new_elems)
for elem in new_elems:
heappush(heap, elem)
sorted_list = [heappop(heap) for _ in range(200)]
print(sorted_list == sorted(sorted_list))
