# Build A Max Heap

Create a Max Heap

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

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.

1. Add the element to the bottom level of the heap.
2. Compare the added element with its parent; if they are in the correct order, stop.
3. 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`

# Build A Min 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 !

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:

compsci112358:

Video Tutorials on Recurrence Relation:

Video Tutorial on Algorithm Analysis:
https://www.udemy.com/algorithm-analysis/

Written by