Browse Articles

Heap Sort in Data Structures

Amit Kumar Ghosh  27 min read
22 Sep 2023
Intermediate
397 Views

Heap Sort in Data Structure: An Overview

Data structures are a fundamental part of programming, and sorting algorithms help us to sort data in different ways according to specific needs. Heap Sort is one such method for sorting data which has been successful in its application over the past few decades. It helps us to rapidly manipulate large collections of numbers or strings into an organized structure so that they can be examined quickly and accurately. In this article, we'll discuss what Heap sort in data structure is exactly, why it is used by developers around the world, how it works, when to use it, and its pros and cons. Now let's get started!

What is heap sort in data structure?

Data structures are at the heart of computer programming, and one such structure that has gained popularity due to its efficiency is heap sort. It is a sorting algorithm that makes use of a heap data structure, which gives it a distinct edge over other sorting techniques. In a heap sort, the root element (min or max) is repeatedly removed from an array and then the heap is sorted. It is effective, compatible with a variety of data formats, and perfect for quick sorting in intricate data structures.

Heap sort algorithm in data structure

Example

Python

 # Heap Sort in python

   def heapify(arr, n, i):

       # Find the 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//2, -1, -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 = [2, 22, 9, 3, 8, 13]

   heapSort(arr)

   n = len(arr)

   print("Sorted array is")

   for i in range(n):

       print("%d " % arr[i], end='')

Java

public class HeapSort {

    public void heapify(int arr[], int n, int i) {

        int largest = i;

        int left = 2 * i + 1;

        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest]) {

            largest = left;

        }

        if (right < n && arr[right] > arr[largest]) {

            largest = right;

        }

        if (largest != i) {

            int swap = arr[i];

            arr[i] = arr[largest];

            arr[largest] = swap;

            heapify(arr, n, largest);

        }

    }

    public void heapSort(int arr[]) {

        int n = arr.length;

        // Build max heap

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

            heapify(arr, n, i);

        }

        // Extract elements from the heap one by one

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

            // Swap root element with the last element

            int temp = arr[0];

            arr[0] = arr[i];

            arr[i] = temp;

            // Call max heapify on the reduced heap

            heapify(arr, i, 0);

        }

    }

    public static void main(String args[]) {

        int arr[] = {2, 22, 9, 3, 8, 13};

        int n = arr.length;

        HeapSort heapSort = new HeapSort();

        heapSort.heapSort(arr);

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

        for (int i = 0; i < n; i++) {

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

        }

    }

}

C++

#include <iostream>

using namespace std;

class HeapSort {

public:

    void heapify(int arr[], int n, int i) {

        int largest = i;

        int left = 2 * i + 1;

        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest]) {

            largest = left;

        }

        if (right < n && arr[right] > arr[largest]) {

            largest = right;

        }

        if (largest != i) {

            int swap = arr[i];

            arr[i] = arr[largest];

            arr[largest] = swap;

            heapify(arr, n, largest);

        }

    }

    void heapSort(int arr[], int n) {

        // Build max heap

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

            heapify(arr, n, i);

        }

        // Extract elements from the heap one by one

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

            // Swap root element with the last element

            int temp = arr[0];

            arr[0] = arr[i];

            arr[i] = temp;

            // Call max heapify on the reduced heap

            heapify(arr, i, 0);

        }

    }

};

int main() {

    int arr[] = {2, 22, 9, 3, 8, 13};

    int n = sizeof(arr) / sizeof(arr[0]);

    HeapSort heapSort;

    heapSort.heapSort(arr, n);

    cout << "Sorted array is" << endl;

    for (int i = 0; i < n; i++) {

        cout << arr[i] << " ";

    }

    cout << endl;

    return 0;

}

Explanation

In order to sort an array (arr) in ascending order, the Heap Sort algorithm first builds a maximum heap and then repeatedly swaps the array's root element with its last element.

Output:

Sorted array is
2, 3, 8, 9, 13, 22

Working of Heap Sort Algorithm

Heap sort is a comparison-based sorting algorithm that uses the binary heap data structure to sort elements. It divides the input into two parts, a sorted region, and an unsorted region. The sorted region is initially empty, while the unsorted region contains all the elements.
Here's how the Heap Sort algorithm works:
  1. Build Max Heap: The first step is to build a max heap from the input array. To do this, we start from the last non-leaf node and heapify the array in a bottom-up manner. Heapify means that we compare the parent node with its children and swap them if necessary to maintain the heap property. This process ensures that the largest element is at the root of the heap.
  2. Heapify: After building the max heap, we have the largest element at the root. We swap this element with the last element in the unsorted region. Then, we reduce the size of the heap (considering the last element as sorted) and perform heapify on the root to maintain the heap property. This step effectively moves the maximum element from the unsorted region to the sorted region.
  3. Repeat: We repeat the heapify step until the heap becomes empty. Each iteration will result in moving the maximum element from the unsorted region to the sorted region.
  4. Obtain Sorted Array: Finally, we have a sorted array when the heap is empty and all elements have been moved to the sorted region. The sorted array is obtained by removing elements from the sorted region and placing them in the appropriate positions.

Visualization of heap sort

Heap sort is a comparison-based sorting algorithm that works by dividing the input into a binary heap data structure and repeatedly extracting the maximum element from the heap to place it in the sorted portion of the array. Here's a step-by-step visualization of the heap sort algorithm:
Let's say we have the following array as input: [8, 5, 3, 9, 2]
Step 1: Build a max heap
  • Start by considering the list as a binary tree.
  • Convert the list into a max heap by applying the "heapify" operation.
  • Heapify ensures that the largest element is at the root of the tree and that each subtree is also a max heap.
The initial binary tree representation:
 After heapify:
  Step 2: Swap the root node (the largest element) with the last element of the list.
  • In this case, swap 9 with 2.
 Step 3: Remove the last element (the largest element) from the heap and place it in its final sorted position.
  • The last element in the heap is 9, so move it to the end of the list.
Step 4: Restore the max heap property by heapifying the remaining elements.
  • Apply heapify to the root node (2) and its children (8 and 3).
 
Step 5: Repeat steps 2 to 4 until the heap is empty.
  • Swap the root node (8) with the last element of the heap (3).
  • Remove 8 from the heap and place it at the end of the list.
  • Apply heapify to the root node (3) and its child (2).
 Step 6: Repeat steps 2 to 4 until the heap is empty.
  • Swap the root node (5) with the last element of the heap (2).
  • Remove 5 from the heap and place it at the end of the list.

  • Apply heapify to the root node (2) and its child (3).
Step 7: Repeat steps 2 to 4 until the heap is empty.
  • Swap the root node (3) with the last element of the heap (2).
  • Remove 3 from the heap and place it at the end of the list.
     
The heap is now empty, and the list is sorted in ascending order: [2, 3, 5, 8, 9].
So, the sorted list using heap sort for the input [8, 5, 3, 9, 2] is [2, 3, 5, 8, 9].

Implementation of Heap Sort Algorithm

Example

Python

 def heapify(arr, n, i):

 largest = i

 left_child = 2 * i + 1

 right_child = 2 * i + 2

 # If the left child is larger than the root

 if left_child < n and arr[left_child] > arr[largest]:

 largest = left_child

 # If the right child is larger than the largest so far

 if right_child < n and arr[right_child] > arr[largest]:

 largest = right_child

 # If the largest is not the root

 if largest != i:

 arr[i], arr[largest] = arr[largest], arr[i]

 # Recursively heapify the affected sub-tree

 heapify(arr, n, largest)

def heap_sort(arr):

 n = len(arr)

 # Build a max heap

 for i in range(n // 2 - 1, -1, -1):

 heapify(arr, n, i)

 # Extract elements from the heap one by one

 for i in range(n - 1, 0, -1):

 # Swap the root (maximum element) with the last element

 arr[i], arr[0] = arr[0], arr[i]

 # Call heapify on the reduced heap

 heapify(arr, i, 0)

def print_array(arr):

 for value in arr:

 print(value, end=" ")

 print()

if __name__ == "__main__":

 arr = [12, 11, 13, 5, 6, 7]

 print("Original array:")

 print_array(arr)

 heap_sort(arr)

 print("\nSorted array:")

 print_array(arr)

Java

public class HeapSort {

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

        int largest = i;

        int leftChild = 2 * i + 1;

        int rightChild = 2 * i + 2;

        if (leftChild < n && arr[leftChild] > arr[largest]) {

            largest = leftChild;

        }

        if (rightChild < n && arr[rightChild] > arr[largest]) {

            largest = rightChild;

        }

        if (largest != i) {

            int swap = arr[i];

            arr[i] = arr[largest];

            arr[largest] = swap;

            heapify(arr, n, largest);

        }

    }

    public static void heapSort(int arr[]) {

        int n = arr.length;

        // Build a max heap

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

            heapify(arr, n, i);

        }

        // Extract elements from the heap one by one

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

            // Swap the root (maximum element) with the last element

            int temp = arr[0];

            arr[0] = arr[i];

            arr[i] = temp;

            // Call heapify on the reduced heap

            heapify(arr, i, 0);

        }

    }

    public static void printArray(int arr[]) {

        for (int value : arr) {

            System.out.print(value + " ");

        }

        System.out.println();

    }

    public static void main(String args[]) {

        int arr[] = {12, 11, 13, 5, 6, 7};

        System.out.println("Original array:");

        printArray(arr);

        heapSort(arr);

        System.out.println("\nSorted array:");

        printArray(arr);

    }

}

C++

#include <iostream>

using namespace std;

class HeapSort {

public:

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

        int largest = i;

        int leftChild = 2 * i + 1;

        int rightChild = 2 * i + 2;

        if (leftChild < n && arr[leftChild] > arr[largest]) {

            largest = leftChild;

        }

        if (rightChild < n && arr[rightChild] > arr[largest]) {

            largest = rightChild;

        }

        if (largest != i) {

            int swap = arr[i];

            arr[i] = arr[largest];

            arr[largest] = swap;

            heapify(arr, n, largest);

        }

    }

    static void heapSort(int arr[], int n) {

        // Build a max heap

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

            heapify(arr, n, i);

        }

        // Extract elements from the heap one by one

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

            // Swap the root (maximum element) with the last element

            int temp = arr[0];

            arr[0] = arr[i];

            arr[i] = temp;

            // Call heapify on the reduced heap

            heapify(arr, i, 0);

        }

    }

    static void printArray(int arr[], int n) {

        for (int i = 0; i < n; i++) {

            cout << arr[i] << " ";

        }

        cout << endl;

    }

};

int main() {

    int arr[] = {12, 11, 13, 5, 6, 7};

    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array:" << endl;

    HeapSort::printArray(arr, n);

    HeapSort::heapSort(arr, n);

    cout << "\nSorted array:" << endl;

    HeapSort::printArray(arr, n);

    return 0;

}

Explanation

The heap_sort method is implemented in this code to sort an array in ascending order, the heapify function is defined to maintain the max-heap property, and an example array is used to show how to use it [12, 11, 13, 5, 6, 7].

Output

Original array:
12 11 13 5 6 7

Sorted array:
5 6 7 11 12 13

Heap sort complexity

Heap Sort Time Complexity

  • Worst Case: O(nlogn).The worst scenario is when a list is arranged in descending order but we wish to sort it in ascending order.
  • Average Case: O(nlogn). The most common scenario is when the list is organized randomly.
  • Best Case: O(n). When the list is already in the appropriate order, that is the ideal situation. The tree doesn't need to be heapified in this situation. It reduces the complexity by a factor of logn, resulting in an O(n) complexity.

Heap Sort Space Complexity

The heap sort algorithm has O(1) space complexity. This is due to the fixed amount of variables we have used, which means that aside from the loop variables and auxiliary variables like temp, n, index, and biggest, we do not require any additional memory space. It indicates that even without the use of a second variable, we can sort an array with 1,000 elements.

Applications of heap sort

  1. Sorting: Heap sort can efficiently sort an array of elements in ascending or descending order. It has a worst-case time complexity of O(n log n), which makes it suitable for sorting large data sets.
  2. Priority Queue: Heap sort can be used to implement a priority queue, where each element has a priority associated with it. The heap structure allows for the efficient insertion and extraction of elements based on their priority.
  3. Selection of Top-K Elements: Heap sort can be used to efficiently find the top-k elements from a large dataset. By building a max-heap, the k largest elements can be extracted in O(k log n) time complexity.
  4. Median Finding: Heap sort can be employed to find the median of a dataset. By using two heaps (a max-heap for the lower half of elements and a min-heap for the upper half), the median can be determined in O(log n) time complexity for each element.
  5. External Sorting: Heap sort can be used in external sorting algorithms, where data is too large to fit entirely in memory. It can be applied in the initial phase of sorting, where chunks of data are sorted and written back to the disk before merging them.

Heap sort advantages and disadvantages

Advantages of heap sort

  • Efficiency: Heap sort has a time complexity of O(n log n) in all cases, where 'n' is the number of elements to be sorted. This makes it more efficient than many other sorting algorithms, such as bubble sort or insertion sort, which have higher time complexities in the worst case.
  • Space efficiency: Heap sort in data structure sorts the elements in place, meaning it does not require additional memory proportional to the number of elements being sorted. It achieves this by utilizing the original array to build a binary heap and then performing in-place swaps to sort the elements.
  • Guaranteed worst-case performance: Unlike some other sorting algorithms, such as quicksort, which have a worst-case time complexity of O(n^2) in certain scenarios, heap sort guarantees a worst-case time complexity of O(n log n) regardless of the input data distribution. This predictability makes it a reliable choice in situations where worst-case performance is critical.
  • In-place sorting: As mentioned earlier, heap sort performs sorting in place, which means it does not require additional memory beyond the input array. This makes it suitable for situations where memory usage is a concern or when working with large datasets that may not fit into available memory.
  • Stability: Heap sort is a stable sorting algorithm, meaning it preserves the relative order of elements with equal keys. This property can be important in certain applications where maintaining the original order of elements is necessary.
  • Simplicity: The basic concept of heap sorting is relatively simple to understand compared to some other advanced sorting algorithms. It involves building a binary heap and repeatedly extracting the maximum (or minimum) element from the heap to construct the sorted array. This simplicity makes it easier to implement and debug.
  • Partial sorting: Heap sort can be easily modified to perform partial sorting, where only the top k elements are sorted, rather than the entire array. This feature can be useful in situations where only a subset of the largest or smallest elements is required

Disadvantages of heap sort

  • Not a stable sorting algorithm: Heap sort does not guarantee the relative order of elements with equal keys. If there are duplicate elements in the input array, their order may change after sorting. This makes heap sort unsuitable for sorting certain types of data where stability is important.
  • Requires additional space: Heap sort requires additional space to build the heap data structure. The sorting algorithm itself is an in-place algorithm, meaning it sorts the elements within the input array without requiring additional memory. However, the process of creating the heap initially requires a separate heap data structure, which can consume extra memory. This extra space requirement can be a disadvantage when working with large data sets.
  • Poor cache performance: Heap sort does not exhibit good cache performance, especially compared to other sorting algorithms like to merge sort or quicksort. This is because heap sort accesses memory in a non-sequential manner, jumping between different parts of the heap. This irregular memory access pattern can lead to cache misses and slower performance, particularly when sorting large arrays.
  • The complexity of implementation: Implementing heap sort correctly can be more complex compared to other sorting algorithms like bubble sort or insertion sort. Building the heap and performing the heapify operation to maintain the heap property requires careful implementation. This complexity can make heap sorting harder to understand and debug, especially for novice programmers.
  • Not adaptive: Heap sort does not take advantage of any existing order in the input array. It always performs the same number of comparisons and swaps regardless of the initial order of the elements. This lack of adaptivity makes it less efficient than some other sorting algorithms when applied to partially sorted or nearly sorted arrays.

FAQs

1. What is heap sort in data structure?

The binary heap data structure is used by the comparison-based sorting algorithm known as heap sort to arrange the items in a predetermined order.

2. What are the two types of heap sort?

Depending on whether they organize objects in ascending or descending order, the two forms of heap sort are called Max Heap Sort and Min Heap Sort.

3. What is the example of heap sort?

Sorting an array of numbers like [4, 2, 9, 7, 5] in ascending order is an example of a heap sort.

4. What is heap sort used for?

Large datasets can be effectively sorted using heap sort, which is frequently used in algorithms like priority queues.

5. What are the advantages of heap sort?

The advantages of heap sort include in-place sorting, time complexity of O(n log n), and consistent performance independent of the distribution of the input data.

Summary
The Heap Sort algorithm is a powerful tool for sorting data efficiently and accurately. Its main advantages include its efficiency, performed in-place sorting capability, stability of the data after it has been sorted, fast performance in comparison to other sorting algorithms, and ease of implementation. Although heap sort in data structure with example can have a longer execution time than other sorting algorithms for large datasets, its properties make it an important algorithm to know when dealing with data work.
Share
About Author
Amit Kumar Ghosh (SDE and Mentor)

A passionate professional with over 6 years of experience in development and training. He is passionate about learning new technologies and sharing his experience with professionals. He is an expert in C/C++, Java, Python and DSA.
Accept cookies & close this