# 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 runsO( 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. No need to swap the child node (1) with the parent node (3) , because 3 is greater than 1.

## Next insert 6 to the bottom of the heap, and since 6 is greater than 3, swapping is needed

## Swap the 6 and the 3

## Next insert 5 to the bottom of the heap, and since 5 is greater than 1, swapping is needed

## Swap the 5 and the 1. Since 5 is less than 6, so no further swapping needed.

## Next insert 2 to the bottom of the heap, and since 2 is less than 5, no need to swap the 5 with the 2.

## Next insert 4 to the bottom of the heap, and since 4 is greater than 3, we need to swap the 4 and the 3.

# Swap the 4 and the 3. Since 4 is less than 6 no further swapping needed, and we are done !

# The array will now look like the below:

# 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:

**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)