Heap Sort

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to create a sorted array. A binary heap is a complete binary tree that satisfies the heap property: in a max heap, each parent node is greater than or equal to its children, while in a min heap, each parent node is less than or equal to its children. Heap Sort involves building a max heap from the input data, then repeatedly extracting the maximum element from the heap and reconstructing the heap until it is empty, resulting in a sorted array.

Algorithm:

Complexity
Best Time Complexity	O(n log n)
Average Time Complexity	O(n log n)
Worst Time Complexity	O(n log n)
Space Complexity	O(1)

Heap Sort Code

Java C C++ Python

public void sort(int arr[]) {
                        int n = arr.length;
                  
                        for (int i = n / 2 - 1; i >= 0; i--) {
                          heapify(arr, n, i);
                        }
                  
                        for (int i = n - 1; i >= 0; i--) {
                          int temp = arr[0];
                          arr[0] = arr[i];
                          arr[i] = temp;
                  
                          heapify(arr, i, 0);
                        }
                  }
                  
                  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 (r < n && arr[r] > arr[largest])
                          largest = r;
                  
                      if (largest != i) {
                          int swap = arr[i];
                          arr[i] = arr[largest];
                          arr[largest] = swap;
                  
                          heapify(arr, n, largest);
                      }
                  }

void swap(int *a, int *b) {
                        int temp = *a;
                        *a = *b;
                        *b = temp;
                    }
                    
                    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) {
                          swap(&arr[i], &arr[largest]);
                          heapify(arr, n, largest);
                        }
                    }
                    
                    void heapSort(int arr[], int n) {
                        for (int i = n / 2 - 1; i >= 0; i--)
                            heapify(arr, n, i);
                    
                        for (int i = n - 1; i >= 0; i--) {
                            swap(&arr[0], &arr[i]);
                            heapify(arr, i, 0);
                        }
                    }

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) {
                          swap(arr[i], arr[largest]);
                          heapify(arr, n, largest);
                        }
                    }
                    
                    void heapSort(int arr[], int n) {
                        for (int i = n / 2 - 1; i >= 0; i--)
                          heapify(arr, n, i);
                    
                        for (int i = n - 1; i >= 0; i--) {
                          swap(arr[0], arr[i]);
                          heapify(arr, i, 0);
                        }
                    }

def heapify(arr, n, i):
                        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 largest != i:
                            arr[i], arr[largest] = arr[largest], arr[i]
                            heapify(arr, n, largest)
                      
                      
                      def heapSort(arr):
                        n = len(arr)
                      
                        for i in range(n//2, -1, -1):
                            heapify(arr, n, i)
                      
                        for i in range(n-1, 0, -1):
                            arr[i], arr[0] = arr[0], arr[i]
                      
                            heapify(arr, i, 0)

Question Number	Question Title	Level	Link
1	Sort Characters By Frequency	Medium	Link
2	Kth Largest Element in an Array	Medium	Link
3	Top K Frequent Elements	Hard	Link

Heap Sort

Algorithm:

Heap Sort Visualizer

Heap Sort Code

Practice Questions