Learning Algorithms — Heap | Part 02

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().

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.

insert(7)
insert(3)
insert(1)

example of inserting

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.

insert(20)
insert(11)
insert(9)

insertion of 20, 11, 9

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.

insert(3)
insert(15)
insert(4)
insert(13)

insertion of 3, 15

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.

insertion of 4

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.

the final result of an insertion

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.

example of step 1: deletion

example of step 2: heap sort and its final result

Swap

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

swap implementation in python

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

example of iteration of heapify

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

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.

1. 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

In iterative insertion, the heapify takes the last index.

Insertion: recursion

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

implementation of deletion of min item

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.

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.

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!