Learning Algorithms - Heap | part 01
Tags: computerscience, algorithms, heap, datastructures
Published: 2020-10-18 21:41:33

In this post, I would like to talk about one of the easiest trees, Heap. Let's crack into it!

# Priority Queue
Before understanding Heap, you need to know what Priority Queue is. **Priority Queue** is an **abstract data type(ADT)** in which data has priority and the one that has higher priority will be deleted first. It has three primary operations. Hold on, what is an abstract data type? It is data structure like _queue_ and _stack_.

* insert(Q, x) - insert an item with a key x into priority queue Q
* max(Q) or min(Q) - return the largest key or the smallest key than any other key in the priority queue Q
* extract-max(Q) or extract-min(Q) - Remove the max or min item from the priority queue Q

# Heap and Priority Queue
So what is the relationship between Heap and **Priority Queue**? **Priority Queue** can be implemented as an _array_, a _linked list_ and a _heap_, a **heap** is the most efficient implementation of it amongst them.

# What is Heap?
## Types of Heap
There are two types of the heap, **max-heap** and **min-heap**. Each type has different **criteria to keep the order**. In a max heap, key-value of the parent node always bigger than children nodes, and vice versa.

**Heap** is a type of binary tree (nearly) made to implement a priority queue, to find **maximum** or **minimum** value at a **constant time** - O(1). A heap consists of the **parent node** and **children nodes**. Its children shouldn't be _greater than or equal to_(*child ≤ parent*) or _smaller than or equal to_(*child ≥ parent*) the parent node. Also, a heap allows the **same data** and we call this data as a **key**.

**Heap** is actually an array that can be visualised as a complete binary tree. There is an array A, `A=[20, 15, 13, 11, 7, 9, 3, 3, 4, 1]`, and it can be visualised as below.
![1_465sMowGy0kffnAfNxyRig](https://dev-to-uploads.s3.amazonaws.com/i/8uhsgygj6visl1kp8ba5.png)

## Rule: The order of heap
The order heap is filled should be **top to bottom** and **left to right**. So the corresponding index would start from the root number **1 to n**. It would be easier with visualisation like so:
![1_auEEI8c2CVCKw3XeRQoJjg](https://dev-to-uploads.s3.amazonaws.com/i/u9u9g0qkd1266cvrlego.png)
We have this array size of 11 represents max heap. The heap will start from index 1 for the sake of convenience of implementation, so index 0 is not in use.

# Is this a heap?
Let's look at the examples below and guess whether this is a heap or not. Is this tree a heap?
![1_lCz4fyutxyhsauePZ3OFAA](https://dev-to-uploads.s3.amazonaws.com/i/83a4hdqi6ujykdqn5n1y.png)
No, it's not a heap. Why? Because the key of the root element is neither of a max value nor key of min value and each node doesn't follow the rule of order as well, so it's against the definition of the **heap**.

What about this tree below? Is this a heap?
![1_kgxrSmp-G_nBK90dJ4KuFQ](https://dev-to-uploads.s3.amazonaws.com/i/x1iokp32fyxqpj3me6t1.png)
Yes, It is a max heap where the key of the root has a max value.

Is the image below a heap?
![1_4llndBvTJBKPG1b2wRXFzg](https://dev-to-uploads.s3.amazonaws.com/i/2zlgsl4uiku4ccxat8sa.png)
Guess what, no! Because each element wasn't filled from the left. There is a violation because of the element with a key 1.

# Implementation of Heap
Now we know what a **heap** is. Time to implement it. Starting with creating a class that generates an array. The index `0` will be not used, it makes the index order simpler.
 
 ```python
 def __init__(self):
     self.heap = [0]
     self.size = len(self.heap) - 1
```

# Methods of Heap
Basic methods for heap would be:
* parent(i)
* left_child(i)
* right_child(i)
* insert(key)
* min() / max()
* extract_min() / extract_max() (delete method)
* heapify(i)

## parent(i)
`parent of i = i / 2` using *integer division*, Let i be an **index** of the node, then its parent's index would be i / 2. For example, if the i = 3, (index), then its parent is 3 / 2 = 1
![1_V2q95fj6QSnXIPIju9vKoA](https://dev-to-uploads.s3.amazonaws.com/i/udexc7r8v63wl3ajsukw.png)
It is apparent that index numbers are integer, not a decimal, so we will do the integer division to get the parent. so `parent(3) = 1`. 

## left_child(i)
it returns the index of the left child of i, `left child = 2 * i`. For example, `i = 3`, `i * 2 = 6`

## right_child(i)
it returns the index of the right child of i, 'right child = 2 * i + 1` For example, 'i =1`, `2 * i + 1 = 3`

```python
def parent(self, i):
    return i // 2

def left(self, i):
    return 2 * i

def right(self, i):
    return (2 * i) + 1 
```

## min()
The minimum node in a min-heap is always a root node, hence it returns root item located in the index `1`.

```python
def min(self):
    return self.heap[1]
```


Okay, guys, I am getting tired… I will continue covering heap in part 2. See you until then.