Note: through out this blog I’m going to be using 0 based indexing, it is common to use 1 based indexing when dealing with heaps.
Initially, one might think to implement a max heap using nodes with pointers, as you might implement a binary search tree. However, the power of a heap, comes from using an array structure instead. Using some simple formulas, we can determine the parent, left child, and right child of elements in the array.
First let’s come up with a formula to find the left and right children.
left child = (index * 2) + 1
right child = (index * 2) + 2
How does this work? Well, starting from our root node at index 0.
0 * 2 = 0
left child = 0 + 1
right child = 0 + 2
We can see this coincides with our visualization. The root node’s children are at indices 1 and 2 in the array.
How about for the node at index 1?
1 * 2 = 2
left child = 2 + 1
right child = 2 + 2
Again, this aligns with our visualization, where the left and right children are at positions 3 and 4.
Now to come up with the formula for deriving the index of the parent node:
parent = floor( (index - 1) / 2 )
Let’s find the parent node for the element at index 4
floor( (4 - 1) / 2 ) → floor(3 / 2) → floor(1.5) → 1
Let’s create our class.
From here on out, all of the code will go inside of this class. We’ll start with the methods to derive the indices of children and parent nodes
Now we’re going to make a method to determine if a given node is a leaf. A leaf is a node that doesn’t have any children. In a complete binary tree, the number of leaves is (number of nodes + 1) / 2. We can use that to our advantage, to find the index of the first leaf. We can use the length property of our
values array to get the correct starting index of the leaves. The leaves will go from this index until the index of the last element in our array.
We’re going to be doing a lot of swapping of elements, to maintain the heap property of our max heap, so let’s create a method to swap two elements in the
Now we need to be able to add elements to our heap.
We will start by adding the element to the end of our values array. After that we need to move the element up the heap until it is in its correct position. We broke the last bit of code into its own method,
The process is pretty simple, since we have a method to give us the index of a node’s parent element. Starting with the current element, we compare its value to the value of its parent. If it is greater than the parent, since this is a max heap, we know we need to swap those elements. After we swap, the current index is now at the index of the parent, and there is a new parent node to compare to. We will do this until the node is not greater than its parent and therefor satisfies the heap property, or until it is the root node.
One of the most common implementations of a max heap is a priority queue. Which is a data structure that allows an element to be given a priority, the element with the highest priority is returned before all other elements. In a max heap, the maximum element is the root node or first element. We can remove it using
The way we do this is by getting the value of the first element to return, moving the last element to the first position, and the moving it down the heap until it is in its correct position again (as to satisfy the heap property). We use a method to called
heapifyDown to move the element down the heap into its correct position.
The first thing we do is check to make sure the element isn’t a leaf (because if it doesn’t have any children then there is no way for it to move down any further). After that we check to see if it is less than either of its children, if so, it needs to be swapped with the child that has the greatest value. If it has been swapped, we need to recursively call
heapifyDown, giving it an argument of the element’s new index (which is the index of the child it just swapped with).
Since we can use
heapifyDown, now we can take in an array and turn it into a max heap!
This works, because we work from the leaves up, pushing each element down to its correct location in the heap, until we reach the root node.
Now for a simple method
peek() which will just return the value of the max element in the heap.
Finally, we will write a method to print out our max heap.
This works by starting with the root node, and printing out each element and its left and right child, until it gets to the leaves of our binary heap.
Time and Space Complexity
Let’s look at the time complexity of the methods we just wrote:
isLeaf()take O(1) time
heapifyDownboth take O(log n) time
addtakes O(log n)
extractMaxtakes O(log n) time
heapifyDown technically take O(h), where h is the height of the heap, however, complete binary trees have a height of ceil(log2(N+1)) - 1. This makes sense because worst case an element either gets pushed from the bottom to the top, or from the top to the bottom, going level by level.
The answer to this stack overflow question, is very detailed as to why
buildHeap takes O(n) time. To simplify it and put it in my own words, it takes linear time, because:
- At the bottom level, the leaves can not be pushed down any further
- At the second most bottom level, the nodes can at most be pushed down one level
- At the third most bottom level, the nodes can at most be pushed down two levels
- As we move up the heap, they can each be pushed down further, but there are less nodes
There are more nodes at each level, but the maximum time that
heapifyDown can take, decreases (because as mentioned,
heapifyDown actually takes O(h) where h is the height of the heap). So rather than O(n log n), it amounts to O(n).
Space complexity of a max heap is O(n). We only have our
values array, and move elements around within this array.
Learning about heaps was interesting, I would have never thought to use an array to represent a binary tree. Not only will it be useful to learn heap sort, but also they have other use cases like being used for a priority queue. The code in this blog can be found in this GitHub repository. If you would like to see a visualization of a max heap, and some of its methods, you can go here.