Learning Algorithms - Heap | part 01

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.

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:

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?

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?

Yes, It is a max heap where the key of the root has a max value.

Is the image below a heap?

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.

 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

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 + 1For example, 'i =1, 2 * i + 1 = 3

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.

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.