## DEV Community 👩‍💻👨‍💻 is a community of 919,000 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. Aya Bouchiha

Posted on • Updated on

# Your complete guide to Heap data structure!

Hi, I'm Aya Bouchiha, in this beautiful day, I'm going to explain the Heap data structure.
#day_22

## Definition of Heap

Heap: is a complete binary tree (types of a binary tree) (which each node has at most two children and All the leaves should lean towards the left) where the root node is compared with its children and arrange accordingly.

### Example of complete binary tree ### Example of incomplete binary tree ## Types of Heap

### 1. Max-heap

The key of every node is smaller than or equal its parent

`arr[parent] >= arr[i]`

### Example of max-heap ### 2. Min-heap

The key of every node is greater than or equal its parent

`arr[parent] <= arr[i]`

### Example of min-heap ## Application of Heap

• Heap sort algorithm
• Order statistics Getting The minimum value or the maximum value in a constant time
• Graph algorithms like Prim's Algorithm and Dijkstra's algorithm
• Priority Queue

## Space and Time complexity of Heap

The space complexity of the heap is O(n)

insertion (push) deletion (pop) peek
O(log n) O(log n) O(1)

## Heap array implementation

let's take this example of max-heap:
the index of each node is between parentheses ( ):

``````          15(0)
/          \
(1) 9            13 (2)
/  \         /
(3)5  (4)7   (5)11
``````
``````arr = [15, 9, 13, 5, 7, 11]
``````

the implementation can be done by:

• making the root the first element in the array `arr = root`
• Parent node: `arr[(i - 1) // 2]`
• Left-child: `arr[2 * i + 1]`
• Right-child: `arr[2 * i + 2]`
``````class MinHeap:
def __init__(self):
self.heap = []
self.heap_size = 0

def getParentNodeIndex(self, i: int) -> int:
return (i-1)//2

def getLeftChildNodeIndex(self, i: int) -> int:
return 2*i+1

def getRightChildNodeIndex(self, i: int) -> int:
return 2*i+2

def hasParent(self, i: int) -> bool:
# cheking if a node has a parent
return self.getParentNodeIndex(i) < len(self.heap)

def hasLeftChild(self, i: int) -> bool:
# cheking if a node has a left child
return self.getLeftChildNodeIndex(i) < len(self.heap)

def hasRightChild(self, i: int) -> bool:
# cheking if a node has a right child
return self.getRightChildNodeIndex(i) < len(self.heap)

def getMinValue(self) -> int:
"""
time complexity => O(1)
"""
return self.heap

def printAll(self):
print(self.heap)
``````

## Insertion (push) in Heap

### 1. Approach of insertion

• Increase the size of the heap to add a new element
• The heap is a complete binary tree that's why the new element should lean towards the left, which means, in array representation, we insert the element at the end of the array.
• Heap must satisfy the heap-order property, that's why we should Heapify or bubble up the new element, Heapify or bubbling up is swapping the new element with its parent until
• its parent is greater than or equal to it in a max-heap.
• its parent is smaller than or equal to it in min-heap.

### 1. Explanation of insertion

For better understanding, let's take an example:
we want to insert 1 in this min-heap

``````        3 (0)
/   \
(1) 5     10 (2)
/
9 (3)

``````
``````  [3, 5, 10, 9]
``````
1. Insert the new Element at the end of the array
``````         3 (0)
/   \
(1)  5     10 (2)
/  \
(3)9 (4)1

``````
``````  heap_size += 1
arr = [3, 5, 10, 9, 1]
``````
1. Bubble up the new element
• Since 1 < 5, swap them, so:
``````         3 (0)
/   \
(1)  1     10 (2)
/  \
(3)9 (4)5

``````
``````  arr = [3, 5, 10, 9, 1]
newElementIndex = len(arr) - 1 # 4
# the index of the parent of the new element
ParentIndex = (newElementIndex - 1) // 2 # (4-1)//2 = 1
# 1 < 5
if arr[newElementIdx] < arr[ParentIdx]:
# swap(1, 5)
arr[newElementIdx], arr[ParentIdx] = arr[ParentIdx], arr[newElementIdx]
``````

the array will be:

``````arr = [3, 1, 10, 9, 5]
``````
• Hence 1 < 3, swap them, so:
``````         1 (0)
/   \
(1)  3     10 (2)
/  \
(3)9 (4)5

``````

we'll do the same process for 1 and 3 like (1 and 5) so the array will be

``````arr = [1, 3, 10, 9, 5]
``````

### 3. Implementation of insertion in python

#### the implementation of bubble up or heapify function in python

``````    def bubbleUp(self, i: int):
parentIndex = self.getParentNodeIndex(i)
if parentIndex < 0:
parentIndex = 0
# Loops until it reaches a leaf node
while(i > 0 and self.heap[i] < self.heap[self.getParentNodeIndex(i)]):
# Swap the elements
self.heap[i], self.heap[self.getParentNodeIndex(i)] = self.heap[self.getParentNodeIndex(i)], self.heap[i]
i = self.getParentNodeIndex(i)
``````

#### the implementation of insert function in python

``````    def insert(self, value: int):
self.heap_size += 1
# insert the element at the end
self.heap.append(value)
# bubble up the new element
self.bubbleUp(len(self.heap) - 1)
``````

## Deletion in Heap

### 1. Approach of Deletion

The standard deletion operation on Heap is deleting the root which is the maximum value of the max-heap, and the minimum value of the in-heap.

• Decrease the size of the heap to delete the element
• Swap the root with the last element
• Pop (delete) last element of the array
• Heap must satisfy the heap-order property, that's why we should bubble-down (also known as heapify, percolate-down, sift-down, sink-down, trickle-down, heapify-down, cascade-down, extract-min or extract-max, or down-heap) the new element, bubble-down is swapping the new element with one of its children until
• the child is smaller than or equal to it in a max-heap.
• the child is greater than or equal to it in a min-heap.

### 1. Explanation of deletion

For better understanding, let's take an example:
we want to delete 3 in this min-heap

``````        3 (0)
/   \
(1) 5     10 (2)
/
9 (3)

``````
``````  [3, 5, 10, 9]
``````
1. Swap the root with the last element
``````         9 (0)
/   \
(1)  5     10 (2)
/
(3)3

``````
``````  arr = [9, 5, 10, 3]
``````
1. Delete the last element and decrease the size of the array
``````         9 (0)
/   \
(1)  5     10 (2)
``````
``````  arr = [9, 5, 10, 3]
heap_size -= 1
arr.pop()
``````

so the array will be

``````  arr = [9, 5, 10]
``````
1. Bubble down the root
• Since 9 > 5, swap them, so:
``````         5 (0)
/   \
(1)  9     10 (2)
``````
``````  arr = [5, 9, 10]
``````

### 3. Implementation of deletion in python

#### Bubble down implementation in python

``````    def bubbleDown(self):
# the index of the root => 0
i = 0
while True:
smallest = None

leftChildIndex = self.getLeftChildNodeIndex(i)
rightChildIndex =  self.getRightChildNodeIndex(i)
#  if the node has not any child
if (not self.hasLeftChild(i) and not self.hasRightChild(i)):
break
# if the node has only a left child
elif (not self.hasRightChild(i)):
# the smallest variable will be the index of the left child
smallest = leftChildIndex
# if the node has only a right child
elif (not self.hasLeftChild(i)):
# the smallest variable will be the index of the right child
smallest = rightChildIndex
# if the node has 2 children
else:
# the smallest variable will be the smallest value of the 2 children
smallest = rightChildIndex if self.heap[rightChildIndex] < self.heap[leftChildIndex] else leftChildIndex
# if the node's value is greater than its one of children
if (self.heap[i] > self.heap[smallest]):
# swap the node with its child
self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
# the i variable will be the index of the smallest value of the two children
i = smallest
# if the node's value is smaller than its one of children
else:
break
return

``````

#### delete implementation in python

``````    def delete(self):
# if the size the heap is one or the heap is empty(size = 0)
if self.heap_size <= 1:
self.heap = []
return
# replace last element with the root
self.heap[self.heap_size - 1], self.heap = self.heap, self.heap[self.heap_size - 1]
# decrease the size of heap
self.heap_size -= 1
# delete last element
self.heap.pop()
self.bubbleDown()
``````

## Heap implementation in python (Final code)

``````class MinHeap:
def __init__(self):
self.heap = []
self.heap_size = 0

def getParentNodeIndex(self, i: int) -> int:
return (i-1)//2

def getLeftChildNodeIndex(self, i: int) -> int:
return 2*i+1

def getRightChildNodeIndex(self, i: int) -> int:
return 2*i+2

def hasParent(self, i: int) -> bool:
# cheking if a node has a parent
return self.getParentNodeIndex(i) < len(self.heap)

def hasLeftChild(self, i: int) -> bool:
# cheking if a node has a left child
return self.getLeftChildNodeIndex(i) < len(self.heap)

def hasRightChild(self, i: int) -> bool:
# cheking if a node has a right child
return self.getRightChildNodeIndex(i) < len(self.heap)

def getMinValue(self) -> int:
"""
time complexity => O(1)
"""
return self.heap

def insert(self, value: int):
self.heap_size += 1
# insert the element at the end
self.heap.append(value)
# bubble up the new element
self.bubbleUp(len(self.heap) - 1)

def bubbleUp(self, i: int):
parentIndex = self.getParentNodeIndex(i)
if parentIndex < 0:
parentIndex = 0
# Loops until it reaches a leaf node
while(i > 0 and self.heap[i] < self.heap[self.getParentNodeIndex(i)]):
# Swap the elements
self.heap[i], self.heap[self.getParentNodeIndex(i)] = self.heap[self.getParentNodeIndex(i)], self.heap[i]
i = self.getParentNodeIndex(i)

def delete(self):
# if the size the heap is one or the heap is empty(size = 0)
if self.heap_size <= 1:
self.heap = []
return
# replace last element with the root
self.heap[self.heap_size - 1], self.heap = self.heap, self.heap[self.heap_size - 1]
# decrease the size of heap
self.heap_size -= 1
# delete last element
self.heap.pop()
self.bubbleDown()

def bubbleDown(self):
# the index of the root => 0
i = 0
while True:
smallest = None

leftChildIndex = self.getLeftChildNodeIndex(i)
rightChildIndex =  self.getRightChildNodeIndex(i)
#  if the node has not any child
if (not self.hasLeftChild(i) and not self.hasRightChild(i)):
break
# if the node has only a left child
elif (not self.hasRightChild(i)):
# the smallest variable will be the index of the left child
smallest = leftChildIndex
# if the node has only a right child
elif (not self.hasLeftChild(i)):
# the smallest variable will be the index of the right child
smallest = rightChildIndex
# if the node has 2 children
else:
# the smallest variable will be the smallest value of the 2 children
smallest = rightChildIndex if self.heap[rightChildIndex] < self.heap[leftChildIndex] else leftChildIndex
# if the node's value is greater than its one of children
if (self.heap[i] > self.heap[smallest]):
# swap the node with its child
self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
# the i variable will be the index of the smallest value of the two children
i = smallest
# if the node's value is smaller than its one of children
else:
break
return

def printAll(self):
print(self.heap)

my_heap = MinHeap()
my_heap.insert(5)
my_heap.insert(10)
my_heap.insert(1)
my_heap.insert(2)
my_heap.insert(3)
my_heap.insert(4)
#      1
#    /  \
#   2     4
#  / \   /
# 10  3  5
my_heap.printAll()
my_heap.delete()
my_heap.printAll()
#      2
#    /  \
#   3     4
#  / \
# 10  5
print(my_heap.heap_size) # 5
print(my_heap.getMinValue()) # 2
``````

## References and useful resources

if you have any suggestions for the next posts or any questions you can contact me in telegram

Happy coding :)
#day_22

## Top comments (2) Add the option to initialize it with an array of values, because the greatest benefit of a heap is the ability to create one in O(N) time from an array of values.

Also, in real heaps you have value/priority pairs. The heap orders by priority but the actual value is can be some other object. (Unless you're simply implementing a HeapSort on numbers)

## 🌚 Browsing with dark mode makes you a better developer.

It's a scientific fact.