Learning Algorithms - Heap | Part 02
Tags: computerscience, algorithms, heap, datastructures
Published: 2020-10-19 19:58:08

Continuing from the last post, _Heap Part 01_, I would explain **heap sort** which happens when inserting and deleting items from a heap. Let me recap from what I covered last time. We were doing a **min-heap** example and its basic methods such as **parent()**, **left_child()**, **right_child()**.

{% link https://dev.to/ji90/learning-algorithms-heap-part-01-3bg2 %}

# Violation
**Violation** in a heap is when a child node is greater than a parent node in **max-heap** or child node is less than a parent node in **min-heap**.

# Insertion
We are going to have a look a trivial example of how items inserted, to understand the **heap sort**. To start with, we are going to insert 7, 1, 3 in the order.

```python
insert(7)
insert(3)
insert(1)
```
![1_618hbhp2YozrVFx8fkaTRg](https://dev-to-uploads.s3.amazonaws.com/i/ssufmrjv3fpi2x8od5x4.png)
Did you notice? every time we inserted an item, there will be a comparison of two items, a parent and child, and swap the two when there is a violation. Continuing inserting items from the given example. 

```python
insert(20)
insert(11)
insert(9)
```
![1_4bLTQShx0QXjrBw98_BT6w](https://dev-to-uploads.s3.amazonaws.com/i/3giim280ifo1l8102q04.png)
We inserted 7, 3, 1, 20, 11 and 9 so far. There has not been any swap in the second round. Moving on to the next round.

```python
insert(3)
insert(15)
insert(4)
insert(13)
```
![1__2pQBv-hY4ZZT2QoVJUg4A](https://dev-to-uploads.s3.amazonaws.com/i/z5irjzmy1az1g6wql41f.png)
We swapped 20 and 15 as 15 is smaller than its parent 20, and moving on to parent node 7, the parent 7 is smaller than its child 15, so it is all sorted.

![1_t_i1vuStGBajPEEFPM1pjA](https://dev-to-uploads.s3.amazonaws.com/i/ti15truwa62s6igwzuwb.png)
There are two comparisons 4 and 15, 4 and 7, the number 4 initially inserted in [9] and moved up to [2] as it is swapped with its parent each time. Last round is to insert 13, hang in there till the end.

### Final result
![1_Y9pSpbkGyw8aN4BcwzEqWw](https://dev-to-uploads.s3.amazonaws.com/i/zdlcx8tzvom15wop9ch3.png)


# Extract min
Extract min is the deletion method in a heap. In a big picture, there are two steps:
1. deletion: swap [1] and [n] where n = length of a heap exclude [0] and delete the [n] which is the min item.
2. heap sort: swap until the item in [1] is smaller than its children.

#### step 1: deletion
![1_1TZ3pO2aDWjvPTbLgNcy1A](https://dev-to-uploads.s3.amazonaws.com/i/gqku53eel6v8s0iolps9.png)

#### step 2: heap sort
![1_ONI2tFtXRB4i3NodEEF6-Q](https://dev-to-uploads.s3.amazonaws.com/i/3a61132jvy2byq7dgfyg.png)

# Swap
**Swap** method is simply swapping two items and will be used in **heapify()** method. 

```python
def swap(self, a, b):
    self.heap[a], self.heap[b] = self.heap[b], self.heap[a]
``` 

# Heapify
Whenever there is a violation in heap properties, we are going to correct the violation by swapping a child and a parent. What I mean by violation is, when a child is less than its parent in **min-heap**. There would be two ways of implementation using recursion or iteration. Insertion and deletion always run heapify at the end of the execution to keep to sort the heap.

## Iteration
```python
def heapify(self, i):
    parent = i // 2
    """ 
    as long as the element is in the range of index of a heap 
    (0 is not included)
    """
    while i // 2 > 0:
        # if the element is bigger than its parent swap them
        if self.heap[i] < self.heap[parent]:
            self.swap(parent, i)
            
        # move the index to the parent
        i = i // 2
```  
Let me break down the code line by line.

1. `while i // 2` means as long as the in the range (from 1 to n)
2. `self.heap[i] < self.heap[parent]` if the current node is less than its parent, swap those two since parent should be smaller.
3. `i = i // 2` means bubble up to its parent to keep checking the violation.

Note: `i` in this heapify is **self.size** which refers to the **last index**

## Recursion
```python
def heapify(self, i):
    l = self.left(i)
    r = self.right(i)
    smallest = i

    """
    if the r and l are within the range of index,
        and if one of those are smaller than i,
        swap them with i
    """
    if l <= self.size and self.heap[l] < self.heap[i]:
        smallest = l
        print(f"now smallest is {self.heap[l]}")
        self.swap(i, smallest)
    if r <= self.size and self.heap[r] < self.heap[i]:
        smallest = r
        self.swap(i, smallest)

    """
    recursively do the process(heapify) above
    until i becomes smallest in the three relationships in the tree
    """
    if smallest != i:
        self.heapify(i)
```
##### Break down:
i = parent node
there are three pointers that refer to the left child, right child and smallest. In here, the important thing to remember in here `i ≤ l or r`.
if `l` or `r` are within the range of index and one of those are smaller than `i`, then swap them with `i` since `i` should be the smallest.

2. recursively do the process until `i` becomes smallest amongst the three (left child, right child, parent i).


# Implementation
The two insertions are basically the same, the argument the heapify method receives varies due to different heapify method. Firstly, appending a new node then increase size. Lastly, sorting the heap.

## Insertion: iteration
```python
def insert(self, key):
    self.heap.append(key)
    self.size += 1
    # Fix violation if there is one
    # iteration heapify
    self.heapify(self.size)
```
In iterative insertion, the heapify takes the last index.

## Insertion: recursion
```python
def insert(self, key):
    self.heap.append(key)
    self.size += 1
    # Fix violation if there is one
    # recursion heapify
    self.heapify(self.size // 2)
```
In recursive insertion, the heapify takes the parent index of the last item.

The **time complexity of insertion** is appending O(1) + size alteration O(1) + heapify O(log n) = _O(log n)_

# Deletion (extract min)
Code break down:
1. store the item to delete
2. swap the root item with the last one
3. delete the last item that where there is min item
4. heap sort until it meets the criteria
5. return the removed item

```python
def extract_min(self):
    popped = self.heap[1]
    # swap last item and the root(min) item
    self.swap(self.size, 1)
    # pop the last item off
    self.heap.pop()
    # reduce size of the heap as an item is deleted
    self.size -= 1
    # sort the heap
    self.heapify(1)
    # return the popped item
    return popped
```
Easy peasy, yeah?

The **time complexity of deletion** is swap O(1) + deletion O(1) + size alteration O(1) + heapify O(log n) = **O(log n)**


# Time analysis
Heapify plays a key role in this algorithm. Because other steps in insertion and deletion are constant time, what we really care about is the heapify method. Let me explain why heapify takes **logarithmic time**.

![1_2NnifXR3HQjk1efoppNkkQ](https://dev-to-uploads.s3.amazonaws.com/i/tp45emxtw4iq4740jwhb.png)
If `N = 9`, the heapify will take a maximum of 4 steps in the worst case, therefore the height of the tree would be the time to process the heapify function. Let's substitute the N to logarithm formula.

![1_zlt2J9xnjYBCKoY5ANPzDQ](https://dev-to-uploads.s3.amazonaws.com/i/0z9a7x4xnjcz626bjyac.png)

2³ is roughly equal to 9, hence the heapify is O(log N)

I still have one advanced method to explain. I will see you in part 3!