Binary Heaps a gentle introduction

Most common use of binary heaps as a backing data structure in implementation of Priority queues, the reason they are better
is though array backed priority queues have fast access times O(1) they have very slow insert times O(N) because each element of an array needs to be evaluated for insertion.

To solve this problem Binary heaps are used in priority queues that have require fast insertion rates, as binary heaps offer deletion and insertion in O(LogN) times.

Heaps are binary trees with the following characteristics

1: They are completely filled from left to right
2: They are usually implemented using an array
3: Each nodes key is larger than the keys of its children

Here is an example of a heap

This heap can be represented as the following array

0 -> 100
1 -> 90
2 -> 80
3 -> 30
4 -> 60
5 -> 50
6 -> 70
7 -> 20
8 -> 10
9 -> 20
10 -> 35
11 -> 45
12 -> 5

Try to match the values in the array to the heap diagram above, you just go line by line starting from the root 100 then 90 and 80 and so on..

Since we now know what the heap looks like, lets take a look at the operations that it supports best. Namely insertion of new nodes and deletion of max node.

Deletion of Max (root) node

Node removal follows a simple algorithm which gives us the max node as well as rebalances the heap

We can achieve this using following steps

1: Remove the root node (100) MaxN = Heap[0]
2: Move the last node (5) of the heap to the root LastN = Heap[N-1]
3: Percolate the last node until its below the larger node and above a smaller one

So referring to our diagram above the process will look like this
- Remove 100 — Move 5 to the root node — Begin percolation — Swap 5 and 90 — Swap 5 and 60 — Swap 5 and 35

• during percolation, swapping occurs on the child nodes that have greater key values

From the above process you can see that now 90 is the new root hence once the heap is balanced we can always get the maximum value out of the heap by just calling the first element of that array and rebalancing the heap

Leveraging this characteristic of always being able to quickly pull out the max value out of the heap is the Heap Sort algorithm . This makes its complexity to be in order of O(logN)

Insertion

Insertion follow more or less a similar process but in reverse
- A new node is added to the end of the heap / array — Percolation is done in reverse or upwards till the heap is balanced

The process:

Lets say we are adding a new node with a value of 55
- Attach 55 to node with value of 5 - Begin upwards percolation - Swap 5 and 55 - Swap 55 and 50 And we are done as the heap is now balanced

In the next article we shall look at the code used for both operations. I hope this helped you understand the use and how binary heaps work in general

Bonus material
The following formula allows us to find nodes in the array and its something that you will use when writing percolation code

• Parent : (x — 1) /2
• Left Child : 2x + 1
• Right Child: 2x + 2

Where x is the index of the array