A couple of weeks ago, we learned Trees and Binary Search with Search Trees. Today, we are going to add on an advance topic on top of Trees.
Heaps are another variation of the tree data structure and are adept at keeping track of the maximum or minimum value held within, referred to as max-heaps and min-heaps, respectively. Specifically, heaps are a type of binary tree, since each child node is either greater or less than its parent (depending on if itβs a max-heap or min-heap). They are efficient for accessing the root value, which will either be the max or min (again, depending on the type of heap) and inserting new values.
Heap Representations
We can picture min-heaps as binary trees, where each node has at most two children. As we add elements to the heap, theyβre added from left to right until weβve filled the entire level.
At the top, weβve filled the level containing 12 and 20. The next addition comes as the left child of 12, starting a new level in the tree. We would continue filling this level from left to right until 20 had its right child filled.
Conceptually, the tree representation is beneficial for understanding. Practically, we implement heaps in a sequential data structure like an array or list for efficiency.
Notice how by filling the tree from left to right; weβre leaving no gaps in the array. The location of each child or parent derives from a formula using the index.
- left child: *(index * 2) + 1
- right child: (index * 2) + 2
- parent: (index - 1) / 2 β not used on the root!
[Image credits to geeksforgeeks(https://www.geeksforgeeks.org/memory-representatio)
Adding an Element: Heapify Up
Sometimes you will add an element to the heap that violates the heapβs essential properties.
Weβre adding 3 as a left child of 11, which violates the min-heap property that children must be larger or equal to their parent.
We need to restore the fundamental heap properties. This restoration is known as heapify or heapifying. Weβre adding an element to the bottom of the tree and moving upwards, so weβre heapifying up.
As long as weβve violated the heap properties, weβll swap the offending child with its parent until we restore the properties, or until thereβs no parent left. If there is no parent left, that element becomes the new root of the tree.
3 swaps with 11, but thereβs still work to do because now 3 is a child of 5. One more swap and weβve restored the heap properties. The parent value, 2, is lesser than the child, 3. We can see that 3βs children 5 and 14 are also greater.
[Image credits to wikimedia(https://commons.m.wikimedia.org/wiki/File:Max_heap_insert.webm)
Removing an Element: Heapify Down
Maintaining a minimum value is no good if we can never retrieve it, so letβs explore how to remove the root node.
In the diagram, you can see removing the top node itself would be messy: there would be two children orphaned! Instead, weβll swap the root node, 2, with the bottom rightmost child: 20. The bottom rightmost child is simple to remove because it has no children.
Unfortunately, weβve violated the heap property. 20 is now the root node, and thatβs not the minimum value in the heap. Weβll heapify down to restore the heap property.
This process is similar to heapifying up, except we have two options (5 and 10) where we can make a swap. Weβll choose the lesser of the two values and swap 20 with 5. This is necessary for the heap property, if we had chosen to swap 20 with 10, then the minimum value would not be at the root. With 5 at the root, the root node is the minimum value in the heap again.
Another swap is required because 20 is greater than its children, so we swap 20 with 11.
Now 20 no longer has any children (it is a child of 11), and all other nodes in the heap only have parents with smaller values.
Just like that, weβve retrieved the minimum value, allocated a new minimum, and maintained the heap property!
[Image credits to Bappy Nur on Youtube(https://www.youtube.com/watch?v=R-xvaK1tP58)
Top comments (0)