Home

 › 

Articles

 › 

What Is Heap Sort, And How Do You Use It?

heap sort

What Is Heap Sort, And How Do You Use It?

When sorting an array of data, it’s crucial to familiarize yourself with sorting algorithms. In data structures, sorting is arranging data in a specific format based on a linear relationship among data items. 

Sorting is essential as data search can be optimized at a very high level when data is sorted in a given format. Furthermore, sorting can represent data in a more readable format. We have a wide range of sorting algorithms, but in this article, we will examine what Heap sort is, and how to use it. Let’s get right into it!

What is Heap Sort: An Exact Definition

Heap sort is a well-known and efficient sorting algorithm. It’s a concept used to sort array data by eliminating elements one by one from the heap- a complete binary tree- part of the list, and then inserting them into the sorted part of the list.

Heap sort basically has two phases involved:

  • Creating a heap, either max-heap or min-heap using elements of a specified array.
  • Recursively deleting the root element of the heap built in the first phase.

How Does the Heap Sort Algorithm Work?

Here is how the heap sort algorithm is implemented:

  1. Create a max heap to store data from the unsorted list.
  2. Take out the largest value from the heap and insert it into a sorted list.
  3. Swap the root of the heap with the last element in the list, and then rebalance the heap.
  4. Once the max-heap is completely empty, return the sorted list.

Here is the algorithm

HeapSort(arr)

CreateMaxHeap(arr)

for i = length(arr) to 2

    swap arr[1] with arr[i]

        heap_size[arr] = heap_size[arr] ? 1

        MaxHeapify(arr,1)

End        

Let’s examine the steps a little more.

Step 1: Create a max-heap

CreateMaxHeap(arr)

    heap_size(arr) = length(arr)

    for i = length(arr)/2 to 1

   MaxHeapify(arr,i)

   End 

In this algorithm, we will need to build out a max-heap. As we all know, in a max-heap, the largest value is the root value. Each parent node needs to have a larger value than its associated children.

Imagine we had the list below of unsorted values:

[14, 11, 2, 20, 3, 10, 3]

By placing our values into a max-heap data structure, this is how our list would look like:

[20, 11, 14, 2, 10, 5, 3]

We can present the above max-heap like this:

Presentation of a max-heap.

Step 2: Take out the root of the heap

To sort out the data, we will repeatedly extract and eliminate the largest value from the heap until it’s empty. If we follow the principles of heaps, we can anticipate that the largest value will be located at the heap root.

After eliminating the largest value, we can’t just abandon the heap without a root, because it would result in two nodes being disconnected. Instead, we can exchange the root node with the last element in the heap. Since the last element has no children, it can be easily removed from the heap.

However, this step causes a major problem. By swapping the two elements, the root node now isn’t the largest in the heap. The heap will need to be restructured to ensure it’s balanced.

Step 3: Heapify down (restore the heap)

The root value not being the larger value, the heap principle has been violated as the parent must have a value greater than the children’s value.

However, there is a solution to this problem! We’ll need to heapify up, which involves adding a value to the end of the heap and working your way up the data structure until you find its appropriate position. To heapy down, you compare the new root value to its children, select the child with the greater value, and swap it with the root value. Work your way down the heap until it’s balanced.

heap sort
Illustration of the heapify down process.

In the above example, you swap the original root value 20 with 3 – the right-most child. Having 3 as the new root, compare its value to its child value 14, and since it’s greater than 3, swap them to make 14 the new root. Next, compare 3 to its new child 5, and since 5 is greater than 3, swap them so that 5 is the new parent value. Since there are no other children to compare to 3, the heap is now balanced.

Step 4: Repeat

you‘ll need to repeat the procedure of swapping the root and the last element, taking out the largest value, and rebalancing the heap as long as the data structure contains a size greater than 1. When this criterion is met, you will have a sorted set of values.

Heap Sort Complexity

Time Complexity

Here is the time complexity of Heap Sort in the best case, average case, and worst case.

CaseTime Complexity
Best CaseO(n log n)
Average CaseO(n log n)
Worst CaseO(n log n)
  • Best Case Complexity: Occurs when the array is already sorted, i.e no sorting required. O(n log n) is the best-case time complexity of heap sort.
  • Average Case Complexity: It occurs when the elements in the array are not arranged in a properly ascending or descending order, resulting in a jumbled order. O(n log n) is the average case time complexity of heap sort.
  • Worst Case Complexity: This happens when you need to sort the array elements in reverse order, meaning that if the elements are initially in descending order, you will need to sort them in ascending order. O(n log n) is the worst-case time complexity of heap sort. 

Space Complexity

The space complexity of heap sort is O(1)

Space ComplexityO(1)
StableN0

How Is the Heap Sort Algorithm Implemented?

Here’s how heap sort is implemented in Java programming language.

//To heapify a subtree. Here "i" is the root node index in arr[], and "x" is the heap size

public class HeapSort {

    public static void sort(int[] arr) {

        int x = arr.length;

        //rearrange array (Build heap)

        for (int i = x /2 - 1; i >= 0; i--)

        heapify(arr, x, i);

        // extract an element one by one from the heap

        for (int i = x - 1; i > 0; i--) {

            // move the initial root to the end

            int temp = arr[0];

            arr[0] = arr[i];

            arr[i] = temp;

            // call the max heapify function on the reduced heap

            heapify(arr, i, 0);

        }

    }

static void heapify(int[] arr, int x, int i) {

    int largest = i; //initialize largest as root

    int l = 2 * i + 1; //left

    int r = 2 * i + 2; // right

    // if the left child is bigger than the root

    if (l < x && arr[l] > arr[largest])

    largest = l;

    //if the right child is bigger than largest so far

    if (r < x && arr[r] > arr[largest])

    largest = r;

    //if largest is not the root

    if (largest != i){

        int swap = arr[i];

        arr[i] = arr[largest];

        arr[largest] = swap;

        //repeatedly heapify the affected sub-tree

        heapify(arr, x, largest);

    }

}

//a function to print an array of size x

static void printArray(int[]) {

    int x = arr.length;

    for (int i = 0; i < x; ++i)

        System.out.print(arr[i] + " ");

    System.out.println();    

}

// Driver code

public static void main (String[] args) {

    int[] arr = { 13, 12, 14, 6, 7, 8 };

    sort(arr);

    System.out.println("Sorted array is");

    printArray(arr);

 }

}

Output

This is the sorted integer array in ascending order.

The sorted array is

6, 7, 8, 12, 13, 14

Pros and Cons of Heap Sort Algorithm

Pros

  • Efficiency: This sorting algorithm is very efficient as the time required to sort a heap increases logarithmically, whereas in other algorithms time grows exponentially slower as the sorting items increase.
  • Simplicity: Compared to other equally efficient algorithms, it’s simpler as it doesn’t use advanced computer science principles such as recursion.
  • Memory Usage: Heap sort uses minimal memory to hold the initial list of items to be sorted, and no additional memory space is required to work.

Cons

  • Expensive: Heap sorting is costly.
  • Unstable: Heap sort is unreliable as it might rearrange the relevant order of elements.
  • Inefficient: When dealing with highly complex data, Heap Sort is not very efficient.

Applications of Heap Sorting

You might have encountered Dijkstra’s algorithm, which uses heap sort to determine the shortest path. In Data Structure, heap sort allows the quick retrieval of either the smallest (shortest) or largest (longest) value. It has various applications, including determining the order in statistics, managing priority queues in Prim’s algorithm (also known as minimum spanning tree), and performing Huffman encoding or data compression.

Likewise, various operating systems use the Heap sort algorithm for jobs and process management, since it is based on a priority queue.

In a real-life scenario, heap sort can be applied in a SIM card store, where we have a long queue of customers waiting to be served. The customers who need to pay their bills can be prioritized, as their work takes minimal time. This approach will save time for many customers and avoid unnecessary delays, leading to a more efficient and satisfactory experience for all.

Wrapping Up

Every sorting or searching algorithm has its advantages and disadvantages, and Heap Sorting is no exception. However, the Heap Sort disadvantages are relatively minimal. For instance, It doesn’t require any additional memory space beyond what is already allocated.

Time is another factor. It is found that time complexity is determined using nlog(n), but the actual heap sort is less than O(nlog(n)). This is because extraction from the heap sort reduces the size, thus taking lesser time as the process goes on. Hence, Heap Sort is widely regarded as one of the “best” sorting algorithms in the realm of Data Structure for various reasons.

Frequently Asked Questions

What is meant by heapify?

Heapify is the process of building a heap data structure from an array representation of a binary tree. This process can be used to create either a Max-Heap or a Min-Heap. It starts from the last index of the non-leaf node in the binary tree, whose index is given by n/2 – 1. Heapify is implemented using recursion.

How does Heap Sort work?

Heap sort is a comparison-based sorting algorithm. It works by moving the largest elements from the unsorted region to the sorted region, thereby shrinking the unsorted region. Heap sort visualizes the elements of the array as a heap, and it is known for having an optimal running time. This algorithm is useful when you want to maintain order while extracting the minimum or maximum element from the array.

How do you “heapify” a tree?

To reshape or heapify a binary tree, you start by selecting a node as the root node of the subtree. Then, you compare the value of the root node with the values of its left and right children nodes. If any of the children nodes have a larger (in the case of a max heap) or smaller (in the case of a min-heap) value than the root node, you swap the values of the root node, and the child node with the larger (or smaller) value. After swapping the values, you recursively heapify the subtree rooted at the child node until the entire subtree satisfies the heap property. You repeat this process for every node in the tree until the entire tree satisfies the heap property.

The time complexity of heapify is O(log n), where n is the number of nodes in the subtree being heapified.

What is a binary heap?

A binary heap is a data structure that can be thought of as a complete binary tree where every parent node is less than or equal to its children (in a min-heap) or greater than or equal to its children (in a max heap).

What are the advantages of heap sort?

The advantages of heap sort include its time complexity of O(n log n) which is faster than some other popular sorting algorithms like bubble sort and insertion sort. Additionally, heap sort has a low memory footprint since it only requires a constant amount of extra space.

What are the disadvantages of heap sort?

The disadvantages of heap sort include its non-stable sorting property, which means that the relative order of equal elements may not be preserved after sorting. Additionally, heap sort is not very efficient for small arrays, and its recursive nature can lead to slower performance on some architectures.

To top