Introduction
Heaps are a data structure created to implement a “Priority Queue” – that which represents a set of elements containing keys associated with a priority – supporting operations such as finding the element with the largest key, extracting the element with the largest key and so on.
A Heap can be imagined as an array, visualized as a nearly-completed binary tree. For a given Array A[0..N], any key at index i, can be imagined as a parent with its child nodes at 2i+1 and 2i+2 indexes respectively.
For a element at an index i:
parent(i) = A[(i-1)/2]
left(i) = A[2i+1]
right(i) = A[2i+2]The important aspect of a heap is such that, every key at index i is always greater than (or less than) all of its children. If the heap follows the maximum parent node property, then it is called as a Max Heap, and if the heap follows the minimum parent node property, then it is called as a Min Heap.
In this article, we shall deal with Max Heaps and understand how we can build a heap from a given array and then use the heap property in sorting the elements – called as Heap Sort.
How to build a Max Heap
A Max Heap defines two important operations to convert an array into a Heap:
- max_heapify()
- build_max_heap()
In order to build a Max Heap, we need to implement these two operations and then use them in building the heap from a normal array.
max_heapify
In the max_heapify operation, we will ensure that all the elements in the heap follow the Max_Heap property (all the parents are larger than their child nodes) and recursively correct any node which doesn’t follow the property.
The max_heapify operation assumes that for there is an Array A where A[i] violates the Max_Heap property, both the child nodes of the heap Left(i) and Right(i) are Max_Heaps.
- For a given index i which violates the Max_Heap property, check if either the left(i) or right(i) is the largest among the set {A[i],A[l],A[r]}
- Swap the parent A[i] with the largest element largest(A[i],A[l],A[r])
- Now the index i follows Max_Heap, while one of its child where A[i] is swapped may violate the Max_Heap property
- Repeat the steps 1 to 3 on the swapped index largest(A[i],A[l],A[r]) until the Max_Heap property is satisfied.
The algorithm looks like below:
algorithm max_heapify(array A[0...n], i, heap_size)
begin
l = left(i) // 2i+1
r = right(i) // 2i+2
if l <= heap_size and A[l] > A[r] then
begin
largest = A[l]
else
largest = A[i]
end
if r <= heap_size and A[r] > A[largest] then
begin
largest = A[r]
end
if largest != i then
begin
Swap(i, largest)
max_heapify(A, largest)
end
end Implementing Max Heap in C#
public void max_heapify(int[] array, int i, int heap_size)
{
var left = 2 * i + 1;
var right = 2 * i + 2;
int largestIndex = i;
if (left <= heap_size && array[left] > array[i])
{
// left child is greater than the current element
// potential swap candidate
largestIndex = left;
}
if (right <= heap_size && array[right] > array[largestIndex])
{
// right child is larger than the largest(i, left)
largestIndex = right;
}
// swap the parent and the largestIndex element
if (largestIndex != i)
{
swap(array, i, largestIndex);
// now the tree at largestIndex may not be a max_heap
// iterate on the sub_heap
max_heapify(array, largestIndex, heap_size);
}
}
build_max_heap
build_max_heap operation converts a normal array of elements into a Max_Heap. The operation works on the max_heapify operation and iteratively calls max_heapify on all the nodes which are not the leaves.
For a given array A[0…n], the operation works as follows:
algorithm build_max_heap(array A[0...n])
begin
let length = A.length;
let i = length/2;
let heap_size = A.Length - 1;
while i >= 0 do
begin
max_heapify(A, i, heap_size);
i = i - 1;
end
endThe algorithm is very simple, we run the max_heapify() operation on all the nodes starting from the mid of the array till the first element and on the way they’re all converted into Max Heaps.
Why from the mid?
Because by definition of a Heap, all the elements starting from the mid of the array (n/2) are all leaf nodes of the heap and they follow Max_Heap by default (since there are no children for leaves).
Implementing Build Max Heap in C#
public void build_max_heap(int[] array)
{
// run from the mid element to the first element
// and max_heapify() at each element
var i = array.Length / 2;
var heap_size = array.Length - 1;
while (i >= 0)
{
max_heapify(array, i, heap_size);
i--;
}
}For example, for an input set of elements [4,8,6,1,7,28,5,34], running build_max_heap() converts this array into [34,8,28,4,7,6,5,1] where the first element of the array [34] is the maximum element of the set. And every element of the output set [34,8,28,4,7,6,5,1] satisfy the Max_Heap property at any given index i.
Implementing Heap Sort
When we convert an array into a Max Heap, subconsciously we unlock a useful property of the Max Heap – The root node of the Max Heap is the largest element in the array. This can be used to efficiently find the largest element in the array in logarithmic time (we’ll come to the complexity analysis at the end).
Let’s say that we’ve removed the root node of the Max Heap, now the new root of the Max Heap may not follow the Max_Heap property by itself, while its children do follow Max_Heap property.
We can use this to create a sorted array out of an unsorted array by repetitively creating a Max Heap from the array and then replacing the root node which happens to be the maximum element of the set in each iteration. This implementation is called as Heap Sort.
The algorithm for heap sort looks like below:
algorithm Heap_Sort(array A[0...n])
begin
build_max_heap(A);
let heap_size = A.Length - 1;
while heap_size >= 0 do
begin
let max = A[0];
swap(A, 0, heap_size);
heap_size = heap_size - 1;
max_heapify(A, 0, heap_size)
end
endIn this algorithm, we repetitively swap the first element of the array (which is basically the root node of the Max Heap representation of the array) to the last element and shrink the Heap by 1 (excluding the elements from the end of the array after every swap) and now since the root node may not satisfy the Max_Heap property, we call the max_heapify() on the root.
How to implement Heap Sort using C#
public void heap_sort(int[] array)
{
// build heap from the array
build_max_heap(array);
int heap_size = array.Length - 1;
while (heap_size >= 0)
{
// max element of the heap sits at first index
var max = array[0];
//swap it to the last of the array
swap(array, 0, heap_size);
// shrink heap by 1 element
// heap is now from array[0...heap_size-1]
heap_size = heap_size - 1;
// max_heap property might be void now
// run max_heapify at the root
max_heapify(array, 0, heap_size);
}
}
Analyzing Time and Space Complexity of Heap Sort
By definition, a Max Heap is an array visualized as a nearly complete Binary Tree. And since the operations assume that we’re operating on a tree, the time taken for operations are logarithmic in nature. To calculate the time taken for building a Max Heap or sorting, let’s start by calculating the time taken to perform the max_heapify operation on the heap.
In the max_heapify operation, we’re operating on either the left or right branch of the heap and then recursively moving down the levels. Hence the total time taken for this recursive operation on a Heap representing a binary tree of height H is O(H) which is basically around logN, where N is the number of nodes of the tree.
For the build_max_heap() operation, we’re working on half of the array set and then iteratively calling on max_heapify() on the nodes above the leaves and so on till the root is reached.
We can think of it like this:
Assuming a Binary Heap having 15 nodes, we have:
- At the leaves, we generally have 8 nodes which is Level 0
- At the Level 1, we have 4 nodes (approx. N/4)
- At Level 2, we have 2 nodes (approx. N/8)
- At Level 3, we have 1 node which is root. (approx. N/16)
The max_heapify() operation takes O(1) time on one level above leaves (Level 1), it takes O(l) time for nodes that are l levels above the leaves. The total work done is the sum of the work done at all the levels.
which is:
N/4(1C) + N/8(2C) + .... + 1(logN)Cwhere C represents a constant work done during the swap operation between the parent and child nodes, the n/4, n/8 .. represent the number of nodes present for the levels 1, 2, .. logN. logN represents the level of the root node.
simplifying this equation by extracting N from the equation results in the deduction that the build_max_heap operation takes O(N) time over an array of N elements.
Finally for the Heap Sort, we have the max_heapify() operation taking place on each element of the set. Since the loop runs on all the elements N of the array, it runs for O(N) time while each max_heapify() takes O(logN) time. Hence the total complexity for the Heap Sort is O(NlogN).
We don’t need to think much about the space in this case because we’re swapping “in-place” within the array and so no additional space is required.
Conclusion
Heap data structure visualizes itself as a nearly complete binary tree, while being just a linear data structure such as an array. The Max_Heap property of the heap together with its tree nature helps in implementing operations such as find_max, insert and sort in logarithmic times. However, finding an element in a heap still takes O(N) time in its worst case, because still we need to touch every node of the heap for the lookup – which paves way for another data structure called Binary Search Trees.
Found this article helpful? Please consider supporting!
