A heap data structure in computer science is a special tree that satisfies the heap property, this just means that the parent is less than or equal to the child node for a minimum heap A.K.A min heap, and the parent is greater than or equal to the child node for a maximum heap A.K.A max heap. In this article I will talk specifically about binary heaps, so each node in our tree will have at most two children. Yes there are more than just binary heaps. The binary heap was created by J.W. J. Williams in 1964 for heapsort.
A binary heap is a binary tree with two other constraints [1]
1) Shape Property: A binary heap is a complete binary tree, this means all of the levels of the tree are completely filled except possibly the last level. The nodes are filled from left to right.
2) Heap Property: The value stored in each node is either (greater than or equal to) OR (less than or equal to ) it?s children depending if it is a max heap or a min heap.
Build a Min Heap
Let?s take an array and make a heap with an empty heap using the Williams method. We will insert the values 3,1,6,5,2 and 4 in our heap.
Array of numbers 3,1,6,5,2, and 4
Williams Method of building a heap:Building a heap from an array of n input elements can be done by starting with an empty heap, then successively inserting each element. This algorithm runs O( n log n) time. However this method is suboptimal and a faster algorithm was created by Floyd, which starts by putting the elements on a binary tree, respecting the shape property, then starting from the lowest level and moving upwards. ? Wikipedia
Insertion Algorithm [1]
To add an element to a heap we must perform an up-heap operation (also known as bubble-up, percolate-up, sift-up trickle-up, heapify-up, or cascade-up), by following this algorithm:
0. If heap is empty place element at root.
- Add the element to the bottom level of the heap.
- Compare the added element with its parent; if they are in the correct order, stop.
- If not, swap the element with its parent and return to the previous step.
The number of operations required depends only on the number of levels the new element must rise to satisfy the heap property, thus the insertion operation has a worst-case time complexity of O(log n) but an average-case complexity of O(1).
Williams Algorithm: top downwhile not end of array, if heap is empty, place item at root; else, place item at bottom of heap; while (child > parent) swap(parent, child); go to next array element; end
First Insert 3 in root of the empty heap:
Next Insert 1 at the bottom of the heap
Swap the child node (1) with the parent node (3) , because 1 is less than 3.
Next insert 6 to the bottom of the heap, and since 6 is greater than 1, no swapping needed
Next insert 5 to the bottom of the heap, and since 5 is greater than 3, no swapping needed
Next insert 2 to the bottom of the heap, and since 2 is less than 3, we need to swap the 3 with the 2.
Swap the 3 and the 2.
Next insert 4 to the bottom of the heap, and since 4 is less than 6, we need to swap the 4 and the 6.
Swap the 6 and the 4, and we are done !
The array will now look like the below:
The min heap array
Build A Max Heap Video!
If you would like to learn more about computer science and Algorithm Analysis , you can take my online course here. I also have a course on Udemy.com called Recurrence Relation Made Easy where I help students to understand how to solve recurrence relations and asymptotic terms such as Big-O, Big Omega, and Theta. You can check out my YouTube channel of videos where I solve recurrence relations and perform algorithm analysis on code that anyone can check out for free !
Introduction to Algorithm Analysis [For Complete Beginners]
Understand and solve algorithms using Big O, Big Omega, and Theta time complexity.
www.udemy.com
Recurrence Relation Made Easy | Udemy
A guide to solving any recursion program, or recurrence relation.
www.udemy.com
Thanks for reading this article I hope its helpful to you all ! Keep up the learning, and if you would like more computer science, programming and algorithm analysis videos please visit and subscribe to my YouTube channels (randerson112358 & compsci112358 )
Check Out the following for content / videos on Computer Science, Algorithm Analysis, Programming and Logic:
YouTube Channel:randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ
compsci112358:https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA
Website:http://everythingcomputerscience.com/
Video Tutorials on Recurrence Relation:https://www.udemy.com/recurrence-relation-made-easy/
Video Tutorial on Algorithm Analysis:https://www.udemy.com/algorithm-analysis/
Twitter:https://twitter.com/CsEverything
YouTube Channel:
Computer Science Website:
Udemy Videos on Recurrence Relation:
Resources:
(1) https://en.wikipedia.org/wiki/Binary_heap(2)http://cs.carleton.edu/faculty/adalal/teaching/fall03/cs127/notes/oct22.pdf (3) https://en.wikipedia.org/wiki/Heap_(data_structure)
