Learning algorithms with Python: Heaps
It has been a while that I posted data structure since I covered stack. 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.
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 + 1. For example, i =1, 2 * i + 1 = 3
min()
The minimum node in a min-heap is always a root node, hence it returns root item located in the index 1.
Okay, that’s enough for now. We will continue covering heap in Part 2. See you soon!
