In computer science, a heap is a type of tree data structure that satisfies the heap property. Heaps commonly present as binary heaps, which take on a complete binary tree data structure. The values in the tree can be arranged in one of two ways:
- A max heap is when each parent node is greater than or equal to its child nodes.
- A min heap is when each parent node is smaller than or equal to its child nodes.
Thus, “heapifying” a tree means reordering the child nodes so that they conform to either max heap or min heap rules.
How to Heapify a Tree
Heapifying a tree is the process of reordering the elements of a tree data structure such that it has the properties of a min or max heap.
When min heap or max heap constraints are placed on tree data structures, we end up with trees of relatively short length. Because heaps are shorter, traversing from the minimum to the maximum value takes less time, which makes the process of searching for values within the tree much faster.
What Are Max Heaps and Min Heaps?
Max Heap Example
Let’s consider the following max heap.
The property of the max heap is that the root node has the maximum value. Further, the value of each node is less than or equal to its parent node. At the top of the tree we have the root node with a value of 90, which is the largest value in the tree. Further, at the second level we see the values 79 and 72, which are less than 90, and then 30 and 65 which are less than 79, and so on.
Min Heap Example
Conversely, take a look at the example of the min heap below.
If we look at the value at the root compared to the values at each node below the root, we see that 12 is the smallest value in the tree. At the level below, we have 20 and 29 which are both greater than 12, and so on.
How to Heapify a Tree Using Max Heapify vs. Min Heapify
The task of heapifying a heap tree is the process of reordering the elements of a tree such that it has the properties of a min or max heap.
Max Heapify
Specifically, max heapify is the process of taking an array that is represented as a binary tree and recording the values at each node such that the child nodes are either less than or equal to the parent, satisfying a max heap:
Min Heapify
Min heapify is the process of recording the values at each node such that the child is greater than or equal to the parent node, satisfying a min heap:
Heap data structures can also be used for finding and keeping track of the minimum/maximum value in an array. This can be useful for scheduling tasks in a priority queue for customers, where customers with issues that take the shortest amount of time are prioritized. This can lead to a lower average waiting time for all customers. Heaps are also used in graph algorithms such as Djiktra’s algorithm, which is used to find the shortest path between two nodes in an array. This can be used for infrastructure planning tasks such as establishing a road network, electricity line or oil pipeline.
Defining a Heapify Function
To explain how best to heapify your data, let’s consider the following array:
array_in = [3, 5, 8, 10, 17, 11, 13, 19, 22, 24, 29]
This array has the corresponding complete binary tree, meaning that each parent node has precisely two child nodes:
We can define a heapify function that takes the array as input and converts it into a max or min heap. Let’s consider converting this binary tree into a max heap. The first thing we need to do is find the last node that isn’t a leaf. A leaf is a node that doesn’t have any children. We see that 11, 13, 19, 22, 24, and 29 are all leaves since they do not point to any children:
Further, reading the nodes in each tree level (that is, a level above the leaf nodes) from left to right we see that the last non-leaf node is 17. This is also the parent of the last node:
Max Heapifying the Tree
If we want to build a max-heap from our binary tree, we can do this by heapifying the nodes up to the last non-leaf node [3, 5, 8, 10, 17] going in reverse order. We apply the heapify operation in reverse level order, meaning starting from right to left at each level we compare each child node to its parent. For max-heapify, if the child node is greater than its parent, swap the values. For example, we start the heapify operation by swapping 17 with the value of its furthest right child, 29, since the child is greater than the parent:
We then move to the next node, going from right to left, and compare 24 with 29. This satisfies the max-heap property so we then move on to 22, which we compare to 10. Since 10 is at a parent node and is less than 22, it does not satisfy the heap property, so we swap:
We then move to the next node. Since 19 is less than 22, it satisfies the max heap principle so we move on to the next level. We start at 13 and compare it to its parent. It does not satisfy the heap property so we swap 8 and 13:
The next node values to swap are 5 with 29, then 5 with 24:
Then we swap 3 and 29, 3 and 24, and then 3 and 17, so that 3 works its way down the tree to become a leaf node and 29 is the root:
Indexing a Heap
Before we can move on to write code to heapify our array in C++, we need to quickly identify the index.
We can find the index, which is simply the position in the tree, of the last non-leaf node by taking the floor of half the number of nodes minus one, where the floor is the greatest integer less than or equal to the input. For example, the floor of 2.2 is 2.0. Let’s calculate the index of the last non-leaf node:
index of last non-leaf node = floor of (number of nodes)/2 - 1.
In our earlier example there are 11 nodes so the index of the last non-leaf node is:
index of last non-leaf node = floor of 11/2-1, which would be 5.5 -1 = 4.5. The floor of 4.5 = 4.0.
So the index of the last non-leaf node is 4, which has the value of 17. As a reminder, we start indexing nodes with 0. For example, the first element has an index of 0, the second has an index of 1, the fifth element has an index of 4, and so forth.
How to Heapify a Tree in C++
1. Define a Heapify Function
Let’s write some C++ code that implements this heapify logic. Let’s create a .cpp file called heapify_code.cpp. In terminal type:
vi heapify_code.cppLet’s start by including iostream (which allows us to write to the standard input/output streams) and using namespace std (which allows us to use standard library methods).
#include <iostream>
using namespace std;
Let’s also define a function called heapify that returns void:
void heapify()
{
}The function will take an integer array input. Let’s call the integer array array_in. It will also take an integer, array_size, for the size of the array. It will also take an integer, subtree_root_index, for the index of subtree root:
void heapify(int array_in[], int array_size, int subtree_root_index)
{
}Next, we need to define a few variables within the scope of our function. Let’s initialize a variable called largest_value. Let’s also initialize variables for the left and right children. For the left child, the index is 2*subtree_root_index +1 and the right child is 2*subtree_root_index +2.
void heapify(int array_in[], int array_size, int subtree_root_index)
{
int largest_value = subtree_root_index;
int left = 2*subtree_root_index + 1;
int right = 2*subtree_root_index + 2;
}Next let’s add logic that checks if the left child is larger than the root. If the left child is greater than the root, we redefine the largest_value as the left child. Within this logic we also need to make sure that the index of the left child is less than the size of the array:
void heapify(int array_in[], int array_size, int subtree_root_index)
{
...//code truncated for clarity
if (left < array_size && array_in[left] > array_in[largest_value]){
largest_value = left;
}
}Next we need to add logic that checks if the right child is larger than the root. Like the previous check, if the right child is greater than the root, we redefine the largest_value as the right child. We also need to make sure that the index of the right child is less than array_size:
void heapify(int array_in[], int array_size, int subtree_root_index)
{
...//code truncated for clarity
if (left < array_size && array_in[left] > array_in[largest_value]){
largest_value = left;
}
if (right < array_size && array_in[right] > array_in[largest_value]){
largest_value = right;
}
}Finally, we need to check if the largest value is equal to the value at the root. If it is not we swap the values at the root with the largest value:
void heapify(int array_in[], int array_size, int subtree_root_index)
{
...//code truncated for clarity
if (largest_value != subtree_root_index )
{
swap(array_in[subtree_root_index], array_in[largest_value];
}
}And finally we recursively call the heap function on the subtree under the condition largest_value is not equal to subtree_root_index:
void heapify(int array_in[], int array_size, int subtree_root_index)
{
...//code truncated for clarity
if (largest_value != subtree_root_index )
{
swap(array_in[subtree_root_index], array_in[largest_value]
heapify(array_in, array_size, largest_value);
}
}The full heapify function is as follows:
void heapify(int array_in[], int array_size, int subtree_root_index)
{
int largest_value = subtree_root_index;
int left = 2*subtree_root_index + 1;
int right = 2*subtree_root_index + 2;
if (left < array_size && array_in[left] > array_in[largest_value]){
largest_value = left;
}
if (right < array_size && array_in[right] > array_in[largest_value]){
largest_value = right;
}
if (largest_value != subtree_root_index)
{
swap(array_in[subtree_root_index], array_in[largest_value]);
heapify(array_in, array_size, largest_value);
}
}
2. Define a Heap Constructor Using the Heapify Function
Now that we’re done writing our heapify function, we can write another function that allows us to construct a heap given an input array. This function will take an array and its size as inputs, and within a for loop call the heapify function on the array starting from the last-node leaf node. We will call the function construct Heap:
void construct_heap(int array_in[], int array_size){
}Let’s define a variable called last_non_leaf_node which is the (array_size/2)-1:
void construct_heap(int array_in[], int array_size){
int last_non_leaf_node = (array_size/2) -1;
}Next we can loop in reverse order starting from the last leaf node, iteratively reducing the index by 1, and call on the heapify function with each value for the index:
void construct_heap(int array_in[], int array_size){
int last_non_leaf_node = (array_size/2) -1;
for (int subtree_root_index = last_non_leaf_node; subtree_root_index >=0; subtree_root_index-=1){
heapify(array_in, array_size, subtree_root_index);
}
}
3. Define a Print Function to Display the Heap Values
Next let’s define a print function that will allow us to print out the values in our heap:
void print_heap(int array_in[], int array_size){
cout << "Printing values at each node in heap" << endl;
for (int index = 0; index < array_size; index+=1){
cout<< array_in[index] << endl;
}
}
4. Define a Main Function to Execute Heapify, Construct_Heap and Print_Heap Functions
Now we can define our main function which will serve as the driver code for executing our heapify, construct_heap and print_heap functions. Let’s define the array we were working with earlier, array_in = [3, 5, 8, 10, 17, 11, 13, 19, 22, 24, 29], which has the corresponding tree representation:
int main(){
int array_in[] = {3, 5, 8, 10, 17, 11, 13, 19, 22, 24, 29};
int array_size = sizeof(array_in) / sizeof(array_in[0]);
construct_heap(array_in, array_size);
print_heap(array_in, array_size);
}Let’s compile our script:
g++ heapify_code.cppAnd run our compiled script:
./a.outAnd we should get the following output:
Printing values at each node in heap
29
24
13
22
17
11
9
19
10
5
3This has the array representation heap = [29, 24, 13, 22, 17, 11, 8, 19, 10, 5, 3] and the following transformation we performed is as follows:
The full program created above is as follows:
#include <iostream>
using namespace std;
void heapify(int array_in[], int array_size, int subtree_root_index)
{
int largest_value = subtree_root_index;
int left = 2*subtree_root_index + 1;
int right = 2*subtree_root_index + 2;
if (left < array_size && array_in[left] > array_in[largest_value]){
largest_value = left;
}
if (right < array_size && array_in[right] > array_in[largest_value]){
largest_value = right;
}
if (largest_value != subtree_root_index)
{
swap(array_in[subtree_root_index], array_in[largest_value]);
heapify(array_in, array_size, largest_value);
}
}
//
void construct_heap(int array_in[], int array_size){
int last_non_leaf_node = (array_size/2) -1;
for (int subtree_root_index = last_non_leaf_node; subtree_root_index >=0; subtree_root_index-=1){
heapify(array_in, array_size, subtree_root_index);
}
}
//
void print_heap(int array_in[], int array_size){
cout << "Printing values at each node in heap" << endl;
for (int index = 0; index < array_size; index+=1){
cout<< array_in[index] << endl;
}
}
//
int main(){
int array_in[] = {3, 5, 8, 10, 17, 11, 13, 19, 22, 24, 29};
int array_size = sizeof(array_in) / sizeof(array_in[0]);
construct_heap(array_in, array_size);
print_heap(array_in, array_size);
}
The code used in this post is also available on GitHub.
Why and When to Heapify a Tree
In summary, heapifying a tree is important since it allows us to benefit from the favorable properties of the heap data structure. Heap data structures can significantly speed up these algorithmic tasks. Heaps also have applications such as min/max searching, order statistics and finding the shortest paths. An order statistic corresponds to the Kth smallest (or largest) value in a collection of items. This has applications in tasks such as quickly finding the median in an array. It is generally useful any time you need to repeatedly select largest or smallest values from a collection of items which is the case with priority queues and order statistics.
Frequently Asked Questions
What is a heap tree?
A heap is a complete binary tree data structure that satisfies the heap property. In a max heap, each parent node is greater than or equal to its child nodes. In a min heap, each parent node is less than or equal to its child nodes. Heaps are commonly used in shortest path algorithms, sorting algorithms (i.e. heap sort) and priority queue implementation.
What does it mean to Heapify?
Heapifying means transforming a binary tree or array into a heap data structure. This is done by rearranging the order of values in the data structure in a way that satisfies the heap property.
What is the min heapify operation?
A min heapify operation is an operation that creates a min heap from an unsorted array or unordered tree. Using a min heapify operation means to rearrange values where parent node values are less than or equal to child node values.
What is the difference between max heapify and min heapify?
A max heapify (max-heap) operation rearranges tree nodes where each parent node is greater than or equal to its child nodes, and the root node always has the largest value. A min heapify (min-heap) operation rearranges tree nodes where each parent node is less than or equal to its child nodes, and the root node always has the smallest value.
