How to Heapify a Heap Tree in C++: A Tutorial With Examples

In pc science, a heap is a sort of tree-shaped knowledge construction that has the particular property of being an almost-completely binary construction satisfying the heap property. A heap could be both a min heap or a max heap. A max heap is a knowledge construction by which every youngster node is lower than or equal to its dad or mum node. A min heap is an analogous sort of knowledge construction the place every youngster node is bigger than or equal to its dad or mum node. Thus, heapifying a heap tree means reordering the kid nodes in order that they conform to both min heap or max heap guidelines.

When min heap or max heap constraints are positioned on tree knowledge buildings, we find yourself with timber of comparatively brief size. As a result of heaps are shorter, traversing from the minimal to the utmost worth takes much less time, which makes the method of looking for values throughout the tree a lot sooner.

 

What Are Min Heaps and Max Heaps?

Let’s contemplate the next max heap.

The property of the max heap is that the foundation node has the utmost worth. Additional, the worth of every node is lower than or equal to its dad or mum node. On the prime of the tree we have now the foundation node with a price of 90, which is the most important worth within the tree. Additional, on the second stage we see the values 79 and 72, that are lower than 90, after which 30 and 65 that are lower than 79, and so forth.

Conversely, check out the instance of the min heap under.

If we take a look at the worth on the root in comparison with the values at every node under the foundation, we see that 12 is the smallest worth within the tree. On the stage under, we have now 20 and 29 that are each higher than 12, and so forth.

 

Learn how to Heapify a Heap Tree in C++

The duty of heapifying a heap tree is the method of reordering the weather of a tree such that it has the properties of a min or max heap.

 

Max Heapify

Particularly, max heapify is the method of taking an array that’s represented as a binary tree and recording the values at every node such that the kid nodes are both lower than or equal to the dad or mum, satisfying a max heap:

 

Min Heapify

Min heapify is the method of recording the values at every node such that the kid is bigger than or equal to the dad or mum node, satisfying a min heap:

Heap knowledge buildings may also be used for locating and retaining observe of the minimal/most worth in an array. This may be helpful for scheduling duties in a precedence queue for purchasers, the place clients with points that take the shortest period of time are prioritized. This will result in a decrease common ready time for all clients. Heaps are additionally utilized in graph algorithms corresponding to Djiktra’s algorithm, which is used to seek out the shortest path between two nodes in an array. This can be utilized for infrastructure planning duties corresponding to establishing a street community, electrical energy line, or oil pipeline. 

 

Defining a Heapify Perform

To elucidate how greatest to heapify your knowledge, let’s contemplate the next array:

array_in = [3, 5, 8, 10, 17, 11, 13, 19, 22, 24, 29]

This array has the corresponding full binary tree, that means that every dad or mum node has exactly two youngster nodes:

We will outline a heapify perform that takes the array as enter and converts it right into a max or min heap. Let’s contemplate changing this binary tree right into a max heap. The very first thing we have to do is locate the final node that isn’t a leaf. A leaf is a node that doesn’t have any youngsters. We see that 11, 13, 19, 22, 24, and 29 are all leaves since they don’t level to any youngsters:

Additional, studying the nodes in every tree stage (that’s, a stage above the leaf nodes) from left to proper we see that the final non-leaf node is 17. That is additionally the dad or mum of the final node:

If we wish to construct a max-heap from our binary tree, we will do that by heapifying the nodes as much as the final non-leaf node [3,5,8,10,17] moving into reverse order. We apply the heapify operation in reverse stage order, that means ranging from proper to left at every stage we examine every youngster node to its dad or mum. For max-heapify, if the kid node is bigger than its dad or mum, swap the values. For instance, we begin the heapify operation by swapping 17 with the worth of its furthest proper youngster, 29, because the youngster is bigger than the dad or mum:

We then transfer to the following node, going from proper to left, and examine 24 with 29. This satisfies the max-heap property so we then transfer on to 22, which we examine to 10. Since 10 is at a dad or mum node and is lower than 22, it doesn’t fulfill the heap property, so we swap:

We then transfer to the following node. Since 19 is lower than 22, it satisfies the max heap precept so we transfer on to the following stage. We begin at 13 and examine it to its dad or mum. It doesn’t fulfill the heap property so we swap 8 and 13:

The following node values to swap are 5 with 29, then 5 with 24:

Then we swap 3 and 29, 3 and 24, after which 3 and 17, in order that 3 works its manner down the tree to develop into a leaf node and 29 is the foundation:

Hug Extra Tree (-Formed Knowledge Constructions) on Constructed In’s Knowledgeable Contributors CommunityHow to Get Started With Regression Trees

 

Indexing a Heap

Earlier than we will transfer on to write down code to heapify our array in C++, we have to rapidly determine the index.

We will discover the index, which is just the place within the tree, of the final non-leaf node by taking the ground of half the variety of nodes minus one, the place the ground is the best integer lower than or equal to the enter. For instance, the ground of two.2 is 2.0. Let’s calculate the index of the final non-leaf node:

index of final non-leaf node = flooring of (variety of nodes)/2 – 1.

In our earlier instance there are 11 nodes so the index of the final non-leaf node is:

index of final non-leaf node = flooring of 11/2-1, which might be 5.5 -1 = 4.5. The ground of 4.5 = 4.0.

So the index of the final non-leaf node is 4, which has the worth of 17. As a reminder, we begin indexing nodes with 0. For instance, the primary factor has an index of 0, the second has an index of 1, the fifth factor has an index of 4, and so forth.  

 

Writing Code for Heapifying in C++

Let’s write some C++ code that implements this heapify logic. Let’s create a .cpp file known as heapify_code.cpp. In terminal sort:

vi heapify_code.cpp

Let’s begin by together with iostream which permits us to write down to the usual enter/output streams.

#embody <iostream>

Let’s additionally outline a perform known as heapify that returns void:

void heapify()

The perform will take an integer array enter. Let’s name the integer array array_in.  It should additionally take an integer, subtree_root_index,  for the index of subtree root . It should additionally take an integer, array_size, for the scale of the array:

void heapify(int array_in[], int index, int array_size)

Subsequent, we have to outline a number of variables throughout the scope of our perform. Let’s initialize a variable known as largest_value. Let’s additionally initialize variables for the left and proper youngsters. For the left youngster, the index is 2*subtree_root_index +1 and the proper youngster 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 proper = 2*subtree_root_index + 2;

Subsequent let’s add logic that checks if the left youngster is bigger than the foundation. If the left youngster is bigger than the foundation, we redefine the largest_value because the left youngster. Inside this logic we additionally have to be sure that the index of the left youngster is lower than the scale of the array:

void heapify(int array_in[], int array_size, int subtree_root_index)



    ...//code truncated for readability


    if (left < array_size && array_in[left] > array_in[largest_value])

    largest_value = left; 

Subsequent we have to add logic that checks if the proper youngster is bigger than the foundation. Just like the earlier test, if the proper youngster is bigger than the foundation, we redefine the largest_value as the proper youngster. We additionally have to be sure that the index of the proper youngster is lower than array_size:

void heapify(int array_in[], int array_size, int subtree_root_index)



    ...//code truncated for readability


    if (left < array_size && array_in[left] > array_in[largest_value])

    largest_value = left; 




    if (proper < array_size && array_in[right] > array_in[largest_value])

    largest_value = proper; 

Lastly, we have to test if the most important worth is the same as the worth on the root. If it’s not  we swap the values on the root with the most important worth:

void heapify(int array_in[], int array_size, int subtree_root_index)



    ...//code truncated for readability

    if (largest_value != subtree_root_index )



    swap(array_in[subtree_root_index], array_in[largest_value];

And at last we recursively name the heap perform on the subtree below the situation largest_value just isn’t equal to subtree_root_index:

void heapify(int array_in[], int array_size, int subtree_root_index)



    ...//code truncated for readability

    if (largest_value != subtree_root_index )



    swap(array_in[subtree_root_index], array_in[largest_value]

    heapify(array_in, array_size, subtree_root_index);

The total perform 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 proper = 2*subtree_root_index + 2;


    if (left < array_size && array_in[left] > array_in[largest_value])

    largest_value = left; 




    if (proper < array_size && array_in[right] > array_in[largest_value])

    largest_value = proper; 




    if (largest_value != subtree_root_index )



    swap(array_in[subtree_root_index], array_in[largest_value]


    heapify(array_in, array_size, largest_value);

 

Utilizing Our Heapify Perform to Outline a Heap Constructor

Now that we’re accomplished writing our heapify perform, we will write one other perform that enables us to assemble a heap given an enter array. This perform will take an array and its measurement as inputs, and inside a for loop name the heapify perform on the array ranging from the last-node leaf node. We are going to name the perform assemble Heap:

void construct_heap(int array_in[], int array_size)

Let’s outline a variable known as 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;

Subsequent we will loop in reverse order ranging from the final leaf node, iteratively decreasing the index by 1, and name on the heapify perform with every worth 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);

Subsequent let’s outline a print perform that may enable use to print out the values in our heap:

void print_heap(int array_in[], int array_size)

  cout << "Printing values at every node in heap" << endl;

  for (int index = 0; index < array_size; index+=1)

    cout<< array_in[index] << endl;

Now we will outline our fundamental perform which is able to function the motive force code for executing our heapify, construct_heap and print_heap features. Let’s outline the array we have been working with earlier, array_in = [3, 5, 8, 10, 17, 11, 13, 19, 22, 24, 29], which has the corresponding tree illustration:

int fundamental()

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

And run our compiled script:

./a.out

And we should always get the next output:

Printing values at every node in heap
29
24
13
22
17
11
9
19
10
5
3

This has the array illustration heap = [29, 24, 13, 22, 17, 11, 8, 19, 10, 5, 3] and the next transformation we carried out is as follows:

The code used on this put up is out there on GitHub. 

 

Why and When Heapifying Is a Good Concept

In abstract, heapifying a tree is essential because it permits us to learn from the favorable properties of the heap knowledge construction. Heap knowledge buildings can considerably velocity up these algorithmic duties. Heaps even have functions corresponding to min/max looking out, order statististics, and discovering the shortest paths. An order statistic corresponds to the Kth smallest (or largest) worth in a set of things. This has functions in duties corresponding to rapidly discovering the median in an array. It’s usually helpful any time it’s essential repeatedly choose largest or smallest values from a set of things which is the case with precedence queues and order statistics. 

Be taught Extra C++ on Constructed In’s Knowledgeable Contributors CommunityHow to Write Clean Exception Handling Code in C++