Your complete guide to Heap data structure!
Tags: algorithms, computerscience, codenewbie, beginners
Published: 2021-07-05 00:38:08

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](https://dev.to/ayabouchiha/part-2-binary-tree-in-data-structure-5bgf))  (*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

![complete binary tree in data structure Aya Bouchiha](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/aoszkp1y8lpgr16w7sh0.jpg)

### Example of incomplete binary tree

![binary tree in data structure Aya Bouchiha Heap](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/br3gqablukvoktyj18ka.jpg)

## Types of Heap

### 1. Max-heap

The key of every node is smaller than or equal its parent <br /> 
`arr[parent] >= arr[i]`

### Example of max-heap

![max heap in data structure Aya Bouchiha](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ibg7sxp6y969mmk3vzgc.jpg)

### 2. Min-heap 

The key of every node is greater  than or equal its parent <br />
`arr[parent] <= arr[i]`

### Example of min-heap

![min heap un data structure Aya Bouchiha](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/m0j6kwk58xi6opt81v6f.jpg)

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

```python
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 **_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:
&nbsp; we want to insert 1 in this min-heap

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

```
```python
  [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 

```
```python
  heap_size += 1
  arr = [3, 5, 10, 9, 1]
```

2. Bubble up the new element

* Since 1 < 5, swap them, so:
```
         3 (0)
       /   \
 (1)  1     10 (2)
    /  \ 
(3)9 (4)5 

```
```python 
  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:
```python
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 
```python 
arr = [1, 3, 10, 9, 5]
```
### 3. Implementation of insertion in python

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

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

```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:
&nbsp; we want to delete 3 in this min-heap

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

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

```
```python
  arr = [9, 5, 10, 3]
```
2. Delete the last element and decrease the size of the array

```
         9 (0)
       /   \
 (1)  5     10 (2)
```
```python
  arr = [9, 5, 10, 3]
  heap_size -= 1
  arr.pop()
```
so the array will be 
```python
  arr = [9, 5, 10]
```

3. Bubble down the root

* Since 9 > 5, swap them, so:
```
         5 (0)
       /   \
 (1)  9     10 (2)
```
```python 
  arr = [5, 9, 10]
```

### 3. Implementation of deletion in python

#### Bubble down implementation in python

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

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

```python
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://www.geeksforgeeks.org/array-representation-of-binary-heap/)
+ [https://blog.devgenius.io/how-to-implement-a-binary-heap-javascript-d3a0c54112fa](https://blog.devgenius.io/how-to-implement-a-binary-heap-javascript-d3a0c54112fa)
+ [https://www.section.io/engineering-education/heap-data-structure-python/](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://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=dM_JHpfFITs)
+ [https://www.youtube.com/watch?v=NEtwJASLU8Q](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](https://telegram.me/AyaBouchiha)

Happy coding :)
\#day_22