Heap sorting algorithm

Heap Sort, сортировка, алгоритмы

Heap sort is a popular and efficient sorting algorithm in computer programming. Learning how to write a heap sort algorithm requires knowledge of two types of data structures - arrays and trees.

For example, the initial set of numbers that we want to sort is stored in the array [10, 3, 76, 34, 23, 32], and after sorting, we get a sorted array [3,10,23,32,34,76].

Heap sort works by rendering the elements of an array as a special kind of complete binary tree called a heap.

What is a binary tree? What kinds of binary trees are there?

Binary tree is a tree data structure where each parent node can have at most two children.

A Full binary tree is a special type of binary tree where each parent node has two or no children.

The Perfect Binary Tree is similar to the Complete Binary Tree, but with two main differences:

1. Each level must be completely filled.
2. All sheet elements should lean to the left.

Note: The last element may not have a valid sibling, i.e. an ideal binary tree need not be a complete binary tree.

How to create a complete binary tree from an unsorted list (array)?

• Select the first element of the list to be the root node. (First level - 1 element).
• Place the second element as the left child of the root node and the third element as the right child. (Second level - 2 elements).
• Place the following two elements as children of the left node of the second level. Again, place the next two elements as children of the second level right node (3rd level - 4 elements).
• Keep repeating until you reach the last element.

Relationship between array indices and tree elements

A full binary tree has an interesting property that we can use to find the children and parents of any node.
If the index of any element in the array is i, the element at index 2i + 1 will become the left child, and the element at index 2i + 2 will become the right child. Also, the parent of any element at index i is given a lower bound of (i-1) / 2.

Let's check it out:

Left child of 1 (index 0)
= element in (2*0+1) index 
= element in 1 index 
= 12


Right child of 1
= element in (2*0+2) index
= element in 2 index 
= 9

Similarly,
Left child of 12 (index 1)
= element in (2*1+1) index
= element in 3 index
= 5

Right child of 12
= element in (2*1+2) index
= element in 4 index
= 6

Also confirm that the rules are correct for finding the parent of any node:

Parent of 9 (position 2) 
= (2-1)/2 
= ½ 
= 0.5
~ 0 index 
= 1

Parent of 12 (position 1) 
= (1-1)/2 
= 0 index 
= 1

Understanding this mapping of array indices to tree positions is critical to understanding how the heap data structure works and how it is used to implement heap sort.

What is a heap data structure?

A heap is a special tree-like data structure. A binary tree is said to follow a heap data structure if

• this is a complete binary tree;
• all nodes in the tree follow the property that they are larger than their children, i.e. the largest element is at the root and both of its children are less than the root, and so on. Such a heap is called a descending heap (Max-Heap). If instead all nodes are smaller than their children, this is called a growing heap (Min-Heap).

On the left in the figure is a decreasing heap, on the right is an increasing heap.

How to build a tree

Starting with a perfect binary tree, we can change it to be descending by running the heapify function on all non-leaf elements of the heap.

Because heapfiy uses recursion, this can be hard to understand. So let's first think about how you would build a three-element tree.

heapify(array)
    Root = array[0]
    Largest = largest( array[0] , array [2*0 + 1]. array[2*0+2])
    if(Root != Largest)
          Swap(Root, Largest)

The example above shows two scenarios - one where the root is the largest element and we don't have to do anything. And another one where the root has a larger child, and we needed to swap them around to keep the shrinking heap property.
If you have worked with recursive algorithms before, then you understand that this should be the base case.

Now let's think of another scenario where there is more than one level.

In the figure, both subtrees of the second-level root element are already
descending heaps.
The top element does not fit into the descending heap, but all subtrees are descending.
In order to keep the descending property for the entire tree, we will need to "push" the parent down until it reaches its correct position.

Thus, to keep the descending property in a tree where both subtrees are descending, we need to repeatedly run heapify on the root element until it is larger than its children, or it becomes a leaf node.

We can combine both of these conditions into a single heapify function like this:

void heapify(int arr[], int n, int i)
{
   int largest = i;
   int l = 2*i + 1;
   int r = 2*i + 2;

   if (l < n && arr[l] > arr[largest])
     largest = l;

   if (right < n && arr[r] > arr[largest])
     largest = r;

   if (largest != i)
   {
     swap(arr[i], arr[largest]);

     // Recursively heapify the affected sub-tree
     heapify(arr, n, largest);
   }
}

This function works for both the base case and any tree size. Thus, we can move the root element to the correct position to maintain a shrinking heap status for any tree size, as long as the subtrees are shrinking.

Descending heap build

To build a descending heap from any tree, we can start building each subtree from bottom to top and get a descending heap after applying the function to all elements, including the root element.

In the case of a full tree, the first index of a non-leaf node is defined as n/2 - 1. All other nodes after that are leaf nodes and thus do not need a heap.

We can build a descending heap like this:

// Build heap (rearrange array)
   for (int i = n / 2 - 1; i >= 0; i--)
     heapify(arr, n, i);

As shown in the diagram above, we start with a bunch of the smallest trees and work our way up until we reach the root element.

Procedures for Heapsort

1. Because the tree satisfies the descending property, the largest element is stored at the root node.
2. Remove the root element and place it at the end of the array (nth position). Place the last element of the tree (the heap) in free space.
3. Decrease the heap size by 1 and grow the root element again so that you have the largest element at the root.
4. The process is repeated until all elements of the list are sorted.

The code looks like this:

for (int i=n-1; i>=0; i--)
   {
     // Переместить текущий корень в конец
     swap(arr[0], arr[i]);

     // вызовите максимальный heapify на уменьшенной куче
     heapify(arr, i, 0);
   }

Performance

Heap sort has O(nlogn) time complexity for all cases (best case, average case, and worst case). What is the reason? The height of a complete binary tree containing n elements is log(n).

As we saw earlier, to fully accumulate an element whose subtrees are already descending heaps, we need to keep comparing the element with its left and right children and push it down until it reaches a point where both of its children are less than it.

In the worst case, we would need to move an element from the root node to the leaf node by performing multiple log(n) comparisons and swaps.

In the build_max_heap step, we do this for n/2 elements, so the worst case complexity of the build_heap step is n/2 * log(n) ~ nlogn.

In the sorting step, we exchange the root element with the last element and swap the root element. For each element, this again takes a long time as we may have to move that element from the root to the leaf. Since we are repeating the operation n times, the heap_sort step is also nlogn.

Also, since the build_max_heap and heap_sort steps are executed one after the other, the algorithmic complexity is not multiplied and remains in the order of nlogn.

It also sorts in O(1) complexity space. Compared to quicksort, worst case (O(nlogn)). Quicksort has O(n^2) complexity for the worst case. But in other cases, quicksort is quite fast. Introsort is an alternative to heapsort that combines quicksort and heapsort to retain benefits such as heapsort's worst-case speed and quicksort's average speed.

Using heap sort

Security-related and embedded systems such as the Linux kernel use heapsort because of the O(n log n) upper bound on Heapsort's running time and the constant O(1) upper bound on its backing store.

Although heapsort has O(n log n) time complexity even for the worst case, it doesn't have more applications (compared to other sorting algorithms like quicksort, mergesort). However, its underlying data structure, the heap, can be used effectively if we want to extract the smallest (or largest) from a list of elements without the overhead of keeping the remaining elements in sorted order. For example, priority queues.

Implementation of heap sort in different programming languages

C++ implementation

// C++ program for implementation of Heap Sort
#include <iostream>
using namespace std;

void heapify(int arr[], int n, int i)
{
   // Find largest among root, left child and right child
   int largest = i;
   int l = 2*i + 1;
   int r = 2*i + 2;

   if (l < n && arr[l] > arr[largest])
     largest = l;

   if (right < n && arr[r] > arr[largest])
     largest = r;

   // Swap and continue heapifying if root is not largest
   if (largest != i)
   {
     swap(arr[i], arr[largest]);
     heapify(arr, n, largest);
   }
}

// main function to do heap sort
void heapSort(int arr[], int n)
{
   // Build max heap
   for (int i = n / 2 - 1; i >= 0; i--)
     heapify(arr, n, i);

   // Heap sort
   for (int i=n-1; i>=0; i--)
   {
     swap(arr[0], arr[i]);

     // Heapify root element to get highest element at root again
     heapify(arr, i, 0);
   }
}

void printArray(int arr[], int n)
{
   for (int i=0; i<n; ++i)
     cout << arr[i] << " ";
   cout << "\n";
}

int main()
{
   int arr[] = {1,12,9,5,6,10};
   int n = sizeof(arr)/sizeof(arr[0]);
   heapSort(arr, n);

   cout << "Sorted array is \n";
   printArray(arr, n);
}

Java Implementation

// Java program for implementation of Heap Sort
public class HeapSort
{   

    public void sort(int arr[])
    {
        int n = arr.length;

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
          heapify(arr, n, i);
        }


        // Heap sort
        for (int i=n-1; i>=0; i--)
        {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // Heapify root element
            heapify(arr, i, 0);
        }
    }

    void heapify(int arr[], int n, int i)
    {
        // Find largest among root, left child and right child
        int largest = i; 
        int l = 2*i + 1; 
        int r = 2*i + 2;  

        if (l < n && arr[l] > arr[largest])
            largest = l;

        if (r < n && arr[r] > arr[largest])
            largest = r;

        // Swap and continue heapifying if root is not largest
        if (largest != i)
        {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n, largest);
        }
    }

    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i < n; ++i)
            System.out.print(arr[i]+" ");
        System.out.println();
    }

    public static void main(String args[])
    {
        int arr[] = {1,12,9,5,6,10};

        HeapSort hs = new HeapSort();
        hs.sort(arr);

        System.out.println("Sorted array is");
        printArray(arr);
    }
}

Python implementation (Python 3)

def heapify(arr, n, i):
    # Find largest among root and children
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2 

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    # If root is not largest, swap with largest and continue heapifying
    if largest != i:
        arr[i],arr[largest] = arr[largest],arr[i]
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)

    # Build max heap
    for i in range(n, 0, -1):
        heapify(arr, n, i)


    for i in range(n-1, 0, -1):
        # swap
        arr[i], arr[0] = arr[0], arr[i]  

        #heapify root element
        heapify(arr, i, 0)


arr = [ 12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print ("Sorted array is")
for i in range(n):
    print ("%d" %arr[i])