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[0] = 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[0]
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
or*Heapify*the new element, Heapify or bubbling up is swapping the new element with its parent until*bubble up*- 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]
```

- 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]
```

- 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]
```

- Swap the root with the last element

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

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

- 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]
```

- 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[0] = self.heap[0], 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[0]
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[0] = self.heap[0], 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

- https://www.geeksforgeeks.org/array-representation-of-binary-heap/
- https://blog.devgenius.io/how-to-implement-a-binary-heap-javascript-d3a0c54112fa
- https://www.section.io/engineering-education/heap-data-structure-python/
- https://en.wikipedia.org/wiki/Heap_(data_structure)#:~:text=In%20computer%20science%2C%20a%20heap,to%20the%20key%20of%20C.
- https://www.youtube.com/watch?v=dM_JHpfFITs
- https://www.youtube.com/watch?v=NEtwJASLU8Q

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

Happy coding :)

#day_22

## Discussion (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)

Thank you a lot for your feedback ๐๐