C++

Heapsort Time Complexity

Heap Sort, written as Heapsort, is a kind of sorting algorithm. It takes a list that is partially ordered and produces a sorted list from it. Sorting can be ascending or descending. In this article, sorting is ascending. Note that heapsort does not sort an incompletely unsorted list. It sorts a partially ordered (sorted) list. That partially ordered list is a heap. In this article, the heap considered is the minimum (ascending) heap.

A heap is referred to as “partially ordered” and not “partially sorted”. The word “sort” means complete ordering (complete sorting). A heap is not partially ordered arbitrarily. A heap is partially ordered following a criterion (pattern), as shown below.

So, heapsort consists of two stages: building the heap and extracting the ordered element from the top of the heap. In the second stage, after each extraction, the heap is rebuilt. Each rebuilding is faster than the original building process since rebuilding is done from a previous build, where one element has been removed. And with that, heapsort sorts a completely unsorted list.

The aim of this article is to briefly explain heapsort and then produce its time complexity (see the meaning of time complexity below). Toward the end, coding is done in C++.

Minimum Heap

A heap can be a minimum heap or a maximum heap. A max-heap is one where the first element is the highest element, and the whole tree or corresponding list is partially ordered in descending order. A min-heap is one where the first element is the least element, and the whole list is partially ordered in ascending order. In this article, only the minimum heap is considered. Note: in the topic of the heap, an element is also called a node.

A heap is a complete binary tree. The binary tree can be expressed as an array (list); read from top to bottom and left to right. The heap property for a min-heap is that a parent node is less than or equal to each of its two children. An example of an unordered list is:

 9 19 24 5 3 11 14 22 7 6 17 15 null null null 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

The first row of this table is the elements of the array. In the second row are the zero-based indexes. This list of elements can be expressed as a tree. The null elements have been added to make a full binary tree. Strictly speaking, the null elements are not part of the list (tree). This list has no order, so it is not a heap yet. It will become a heap when it has had partial ordering, according to the heap property.

Relationship Between Nodes and Indexes

Remember, a heap is a complete binary tree before having the heap configuration (heap property). The previous list is not a heap yet, because the elements do not obey the heap property. It becomes a heap after rearranging elements into partial order according to the min-heap property. Partial order can be seen as partial sort (though the word “sort” means complete ordering).

Whether a binary tree is a heap or not, each parent has two children, except the leaf (last) nodes. There is a mathematical relationship among the indexes between each parent and its children. It is as follows: If the parent is at index i, then the left child is at index:

2*i + 1

and the right child is at index:

2*i + 2

This is for zero-based indexing. And so, a parent at index 0 has its left child at index 2×0+1=1 and its right child at 2×0+2=2. A parent at index 1 has its left child at index 2×1+1=3 and right child at index 2×1+2=4; and so on.

By the min-heap property, a parent at i is less than or equal to the left child at 2i+1 and less than or equal to the right child at 2i+2.

Heap

Heapifying means building a heap. It means to rearrange the elements of a list (or corresponding tree) so that they satisfy the heap property. At the end of the heapifying process, the list or tree is a heap.

If the previous unsorted list is heapified, it will become:

 3 5 11 7 6 15 14 22 9 19 17 24 null null null 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Note: there are 12 elements and not 15 in the list. In the second row are the indexes. In the heap building process, elements had to be checked, and some swapped.

Notice that the smallest and first element is 3. The rest of the elements follow in an ascending but undulating manner. If the left and right children at positions 2i+1 and 2i+2 are each greater than or equal to the parent at i, then this is a min-heap. This is not full ordering or sorting. This is partial ordering, according to the heap property. It is from here that the next stage for heap sort starts.

Heapify Time Complexity

Time complexity is the relative running time of some code. It can be seen as the number of main operations for that code to complete. There are different algorithms for heap building. The most efficient and fastest continuously divide the list by two, checking the elements from the bottom, and then doing some swapping of elements. Let N be the number of practical elements in the list. With this algorithm, the maximum number of main operations (swapping) is N. The time complexity for heapifying is given formerly as:

O(n)

Where n is N and is the maximum possible number of main operations. This notation is called the Big-O notation. It begins with O in uppercase, followed by parentheses. Inside the parentheses is the expression for the possible highest number of operations.

Remember: addition can become multiplication if the same thing being added keeps repeating.

Heapsort Illustration

The previous unsorted list will be used to illustrate heapsort. The given list is:

9   19   24   5   3   11   14   22   7   6   17   15

The min-heap produced from the list is:

3   5   11   7   6   15   14   22   9   19   17   24

The first stage in heapsort is to produce the heap which has been produced. This is a partially ordered list. It is not a sorted (completely sorted) list.

The second stage consists of removing the least element, which is the first element, from the heap, re-heapifying the remaining heap, and removing the least elements in the results. The least element is always the first element in the re-heapifyied heap. The elements are not removed and thrown away. They can be sent to a different array in the order in which they are removed.

In the end, the new array would have all the elements sorted (completely), in ascending order; and no longer just partially ordered.

In the second stage, the first thing to do is to remove 3 and place it in the new array. The results are:

3

and

5   11   7   6   15   14   22   9   19   17   24

The remaining elements have to be heapified before the first element is extracted. The heap of the remaining elements can become:

5   6   7   9   15   14   22   11   19   17   24

Extracting 5 and adding to the new list (array) gives the results:

3   5

and

6   7   9   15   14   22   11   19   17   24

Heapifying the remaining set would give:

6   7   9   15   14   22   11   19   17   24

Extracting 6 and adding to the new list (array) gives the results:

3   5   6

and

7   9   15   14   22   11   19   17   24

Heapifying the remaining set would give:

7   9   11   14   22   15   19   17   24

Extracting 7 and adding it to the new list gives the results:

3   5   6   7

and

9   11   14   22   15   19   17   24

Heapifying the remaining set gives:

9   11   14   22   15   19   17   24

Extracting 9 and adding to the new list, gives the results:

3   5   6   7   9

and

11   14   22   15   19   17   24

Heapifying the remaining set gives:

11   14   17   15   19   22   24

Extracting 11 and adding it to the new list gives the results:

3   5   6   7   9   11

and

14   17   15   19   22   24

Heapifying the remaining set would give:

14   17   15   19   22   24

Extracting 14 and adding it to the new list gives the results:

3   5   6   7   9   11   14

and

17   15   19   22   24

Heapifying the remaining set would give:

15   17   19   22   24

Extracting 15 and adding it to the new list gives the results:

3   5   6   7   9   11   14   15

and

17   19   22   24

Heapifying the remaining set would give:

17   19   22   24

Extracting 17 and adding it to the new list gives the results:

3   5   6   7   9   11   14   15   17

and

19   22   24

Heapifying the remaining set would give:

19   22   24

Extracting 19 and adding it to the new list gives the results:

3   5   6   7   9   11   14   15   17   19

and

22   24

Heapifying the remaining set gives:

22   24

Extracting 22 and adding it to the new list gives the results:

3   5   6   7   9   11   14   15   17   19   22

and

24

Heapifying the remaining set gives:

24

Extracting 24 and adding it to the new list gives the results:

3   5   6   7   9   11   14   15   17   19   22   24

and

- - -

The heap array is now empty. All the elements it had at the beginning are now in the new array (list) and sorted.

Heapsort Algorithm

Though the reader might have read in textbooks that heapsort consists of two stages, heapsort can still be seen as consisting of one stage, which iteratively shrinks off the given array. With that, the algorithm to sort with heapsort is as follows:

• Heapify the unsorted list.
• Extract the first element of the heap and put it as the first element of the new list.
• Heapify the remaining list.
• Extract the first element of the new heap and put as the next element of the new list.
• Repeat the previous steps in order until the heap list is empty. In the end, the new list is sorted.

Heapsort Time Complexity Proper

The one-stage approach is used to determine the time complexity for heapsort. Assume that there are 8 unsorted elements to be sorted.

The possible maximum number of operations to heapify the 8 elements is 8.
The possible maximum number of operations to heapify the remaining 7 elements is 7.
The possible maximum number of operations to heapify the remaining 6 elements is 6.
The possible maximum number of operations to heapify the remaining 5 elements is 5.
The possible maximum number of operations to heapify the remaining 4 elements is 4.
The possible maximum number of operations to heapify the remaining 3 elements is 3.
The possible maximum number of operations to heapify the remaining 2 elements is 2.
The possible maximum number of operations to heapify the remaining 1 element is 1.

The possible maximum number of operations is:

8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36

The average of these numbers of operations is:

36 / 8 = 4.5

Notice that the last four heaps in the previous illustration did not change, when the first element was removed. Some of the previous heaps did not also change when the first element was removed. With that, a better average number of main operations (swappings) is 3 and not 4.5. So, a better total average number of main operations is:

24 = 8 x 3
=>24 = 8 x log<sub>2</sub>8

since log28 = 3.

In general, the average case time complexity for heapsort is:

O(n.log2n)

Where the dot means multiplication and n is N, the total number of elements in the list (either list).

Note that the operation of extracting the first element has been ignored. On the topic of Time Complexity, operations that take relatively short times are ignored.

Coding in C++

In the algorithm library of C++, there is a make_heap() function. The syntax is:

template<class RandomAccessIterator, class Compare>
constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

It takes the iterator pointing to the first element of a vector as its first argument and then the iterator pointing just beyond the end of the vector as its last argument. For the previous unsorted list, the syntax would be used as follows to obtain a minimum heap:

vector<int> vtr = {9, 19, 24, 5, 3, 11, 14, 22, 7, 6, 17, 15};
vector<int>::iterator iterB = vtr.begin();
vector<int>::iterator iterE = vtr.end();
make_heap(iterB, iterE, greater<int>());

This code changes a vector content into a minimum heap configuration. In the following C++ vectors, two vectors will be used instead of two arrays.

To copy and return the first element of a vector, use the vector syntax:

constexpr reference front();

To remove the first element of a vector and throw it away, use the vector syntax:

constexpr iterator erase(const_iterator position)

To add an element at the back of a vector (next element), use the vector syntax:

constexpr void push_back(const T& x);

The beginning of the program is:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

The algorithm and vector libraries are included. Next in the program is the heapsort() function, which is:

void heapsort(vector<int> &oldV, vector<int> &newV) {
if (oldV.size() > 0) {
vector<int>::iterator iterB = oldV.begin();
vector<int>::iterator iterE = oldV.end();
make_heap(iterB, iterE, greater<int>());

int next = oldV.front();
oldV.erase(iterB);
newV.push_back(next);
heapsort(oldV, newV);
}
}

It is a recursive function. It uses the make_heap() function of the C++ algorithm library. The second code segment in the function definition extracts the first element from the old vector after the heap building and adds as the next element for the new vector. Note that in the function definition, the vector parameters are references, while the function is called with the identifiers (names).

A suitable C++ main function for this is:

int main(int argc, char **argv)
{
vector<int> oldV = {9, 19, 24, 5, 3, 11, 14, 22, 7, 6, 17, 15};
vector<int> newV;
heapsort(oldV, newV);

for (int i=0; i<newV.size(); i++) {
cout << newV[i] << ' ';
}
cout << endl;

return 0;
}

The output is:

3 5 6 7 9 11 14 15 17 19 22 24

sorted (completely).

Conclusion

The article discussed in detail the nature and function of Heap Sort commonly known as Heapsort, as a sorting algorithm. Heapify Time Complexity, Heapsort illustration, and Heapsort as an algorithm were covered and supported by examples. The average time complexity for a well-written heapsort program is O(nlog(n))