HeapSort - MinHeap
Tags: algorithms, python, programming, computerscience
Published: 2023-01-22 07:46:22

##Definition
The heap data structure is an array object that we can view as a nearly complete binary tree. Each node of the tree corresponds to an element of the array. The tree is completely filled on all levels except possibly the lowest, which is filled from the left up to a point.



![Min Heap](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uzuts5z2e3alzyzw7q3g.png)
The above image represents a min-heap

The tree structure in the diagram is an imaginary structure and this structure is going to be implemented completely in an array, the important point is how we are going to link the elements in an array so that we could **logically form a tree** and the structure as a whole is more efficient than a normal array.

A basic heap with a parent, one left child and one right child

![Parent, Child](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vf8ev8jfuzl6ywq3eyuw.png)
<br/><br/>

## Visualising The Working Of Heap Sort Using Min Heap
Let's take an array of size **5** and build a **min-heap** out of it and finally, remove the least element one by one(sort by ascending order). In the process, you'll understand how a min-heap is formed and how sorting by ascending order is done using the heap sort algorithm.

**1. Insert 5 elements one by one** 

![image 1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/o5zxwykd60l128jacwf1.png)

![image 2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rq42srbu646duo0c4beb.png)
In the above image you could observe that as soon as soon as 5(i.e 0005) was inserted it shifted upwards and 7(i.e 0007) now became the left child to 5, this process of shifting is done to maintain the **min-heap property**


![image 3](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2j1yadrdqg6ugclek3ku.png)
Now as soon as 6(i.e 0006) was inserted as it is greater than 5(i.e 0005) so 5 was not replaced instead 6 was added as the right child to 5.
According to **min-heap property** the **smallest element in the array will always remain on the top**.


![image 4](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ggtvszs5tqlyw46ko4ez.png)
Now when we try to insert 4(i.e 0004) it replaced the root node 5 as **4 is smaller than 5** and 5 replaced 7 as 5 is smaller than 7. One important thing to note here is that not only the root node tries to maintain the min-heap property, but any swap that happens at any level of the heap follows the min-heap property like the swap that we observed above.


![Image 5](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/615z2rbfrw779y3w6vm1.png)
Finally, the last element 8(i.e 0008) is inserted and it takes gets added as the right child to 5.

**2. Delete/Remove element from heap**
Now let's try to **delete** or **remove** the root node from the heap(this operation is nothing but getting the smallest element in the heap)


![Image 5](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/g9egjeso7xk8lwprplvk.png)
We could observe that 5(i.e 0005) takes up the new root node position 7 moves up and 8 becomes the left child of 7.


&nbsp;
### What we imagined and what actually happened...
We performed all the min-heap building operations and operations that helped to maintain the min-heap property, but we **imagined that everything happened on the heap**(tree-like structure in the above diagrams) but all these operations **happen on an array**. There are 3 formulae that link an array and the imaginary heap structure in our heads. 

**Parent index = (index - 1)//2**
**Left Child index = 2*index+1**
**Right Child index = 2*index+2** 

![Parent Child Formula](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5i5k8yn642z31srknidh.jpeg)

(**NOTE** - Indexing in python starts from 0 so index of the element 10 in array is 0)
In the above figure lets consider elements **23, 32, 38** and their corresponding indexes are **1, 3, 4**, now 
**Parent(element 38)** i.e **Parent(index 4)** is 
**(index-1)//2** i.e **(4-1)//2 = 1**
The element in index **1** is **23**

**LeftChild(element 23)** i.e **LeftChild(index 1)** is 
**2*index+1** i.e **(2*1)+1 = 3**
The element in index **3** is **32**

**RightChild(element 23)** i.e **RightChild(index 1)** is 
**2*index+2** i.e **(2*1)+2 = 4**
The element in index **4** is **38**





 



&nbsp;

## Building A Min-Heap Using Python

The first step is to build a min heap using the elements of an array.
Let's take an unsorted array with 5 elements
```python
unsorted_array = [2,10,9,12,11]
```

We are going to code the whole min-heap data structure as a single class (The code snippets below may not follow proper indentation, the whole code is attached as a single block at the end).

```python
class MinHeap:
    def __init__(self, capacity) -> None:
        self.storage = [0]*capacity
        self.capacity = capacity
        self.size = 0
```
**storage**  - Array equivalent to the size of the heap
**capacity** - Size of unsorted array/heap
**size**     - This variable is used for building the array

### Helper Functions
We will have a few helper functions which would help in building the heap and sorting the elements in it.



```python
def getParentIndex(self, index):
    return (index - 1)//2

def getLeftChildIndex(self, index):
    return 2*index+1

def getRightChildIndex(self, index):
    return 2*index+2
```
The above three functions are used to get the parent index, left child index and right child index.






```python
def hasParent(self, index):
    return self.getParentIndex(index) >= 0

def hasRightChild(self, index):
    return self.getRightChildIndex(index) < self.size

def hasLeftChild(self, index):
    return self.getLeftChildIndex(index) < self.size

```
This above functions are used to check whether a node has a parent node or not, has right child or not, has left child or not.

```python
def parent(self, index):
    return self.storage[self.getParentIndex(index)]

def leftChild(self, index):
    return self.storage[self.getLeftChildIndex(index)]

def rightChild(self, index):
    return self.storage[self.getRightChildIndex(index)]
```
The above functions are used to get the parent element, left child element and right child element.

```python
def isFull(self):
    return self.size == self.capacity
```
The above function is used to check if the heap is full or not.

```python
def swap(self, index1, index2):
    temp = self.storage[index1]
    self.storage[index1] = self.storage[index2]
    self.storage[index2] = temp
```
The above function is used to swap two elements in the heap(array).

Now comes **4 important functions** that help to build the heap, to maintain the min-heap property and get elements in ascending order from the heap.


```python
def heapifyUp(self, index):
    if self.hasParent(index) and (self.parent(index) > self.storage[index]):
        self.swap(self.getParentIndex(index), index)
        self.heapifyUp(self.getParentIndex(index))
```
**heapifyUp** function is used while building the min-heap. When we try to insert an element into the array(heap), this function checks if that index has a parent index(parent node) and whether the parent is smaller or not, if not then a swap happens, and a recursive call is made with the parent index. These operations are done to build the min-heap and maintain the min-heap property.


```python
def insert(self, data):
    if self.isFull():
        raise("Heap Is Full")
    self.storage[self.size] = data
    self.size += 1
    self.heapifyUp(self.size - 1)
```
**insert** function is used along with heapifyUp to build the heap. It checks if the heap is already full, and raises an error if full, if not adds elements to **storage** which is the heap array.


```python
def heapifyDown(self, index):
    smallest = index
    if self.hasLeftChild(index) and self.storage[smallest] > self.leftChild(index):
        smallest = self.getLeftChildIndex(index)
    if self.hasRightChild(index) and self.storage[smallest] > self.rightChild(index):
        smallest = self.getRightChildIndex(index)
    if smallest != index:
        self.swap(index, smallest)
        self.heapifyDown(smallest)
```
**heapifyDown** is used while removing elements from the heap, it is used to main the heap property by finding the smallest element in the heap and placing it at the root of the heap. Let's take a scenario where the left child to the root node is smaller than the root node, now **smallest** is assigned with the left child index but the right child is even smaller than the left child, so now **smallest** will be assigned with the right child index and a swap will happen between root and right child, now a recursive call will happen until the **smallest element in heap** is the **new root node**.


```python
def removeMin(self):
    if self.size == 0:
        raise("Heap is empty")
    data =  self.storage[0]
    self.storage[0] = self.storage[self.size - 1]
    self.size -= 1
    self.heapifyDown(0)
    return data
```
**removeMin** is used along with heapifyDown to remove the smallest element(root node from the heap). It removes the smallest element and then assigns the last element as the new root node, reduces the size of the heap array by 1, calls the **heapifyDown** to restore the min-heap property and returns the removed element.

&nbsp;
##Complete Implementation Of Min-Heap
```python
class MinHeap:
    def __init__(self, capacity) -> None:
        self.storage = [0]*capacity
        self.capacity = capacity
        self.size = 0

    def getParentIndex(self, index):
        return (index - 1)//2

    def getLeftChildIndex(self, index):
        return 2*index+1

    def getRightChildIndex(self, index):
        return 2*index+2

    def hasParent(self, index):
        return self.getParentIndex(index) >= 0

    def hasLeftChild(self, index):
        return self.getLeftChildIndex(index) < self.size

    def hasRightChild(self, index):
        return self.getRightChildIndex(index) < self.size

    def parent(self, index):
        return self.storage[self.getParentIndex(index)]

    def leftChild(self, index):
        return self.storage[self.getLeftChildIndex(index)]

    def rightChild(self, index):
        return self.storage[self.getRightChildIndex(index)]

    def isFull(self):
        return self.size == self.capacity

    def swap(self, index1, index2):
        temp = self.storage[index1]
        self.storage[index1] = self.storage[index2]
        self.storage[index2] = temp


    def heapifyUp(self, index):
        if self.hasParent(index) and (self.parent(index) > self.storage[index]):
            self.swap(self.getParentIndex(index), index)
            self.heapifyUp(self.getParentIndex(index))
            
    def insert(self, data):
        if self.isFull():
            raise("Heap Is Full")
        self.storage[self.size] = data
        self.size += 1
        self.heapifyUp(self.size - 1)

    def heapifyDown(self, index):
        smallest = index
        if self.hasLeftChild(index) and self.storage[smallest] > self.leftChild(index):
            smallest = self.getLeftChildIndex(index)
        if self.hasRightChild(index) and self.storage[smallest] > self.rightChild(index):
            smallest = self.getRightChildIndex(index)
        if smallest != index:
            self.swap(index, smallest)
            self.heapifyDown(smallest)

    def removeMin(self):
        if self.size == 0:
            raise("Heap is empty")
        data =  self.storage[0]
        self.storage[0] = self.storage[self.size - 1]
        self.size -= 1
        self.heapifyDown(0)
        return data


###########TESTING WITH A SAMPLE DATA###############

unsorted_array = [2,10,9,12,11]
obj = MinHeap(len(unsorted_array))
for element in unsorted_array:
    obj.insert(element)

# Ascending Order
for i in range(len(unsorted_array)):
    print(obj.removeMin())
```

&nbsp;
## TIME COMPLEXITY

![Time Complexity](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ka9vkq6gzyrcbtfthm1m.png)
The above diagram show the time complexity of merge sort and how it is compared with other algorithms.


[Min-Heap Visualisation Tool](https://www.cs.usfca.edu/~galles/visualization/Heap.html)