Heapsort


title: Heapsort

Heapsort

Heapsort is an efficient sorting algorithm based on the use of max/min heaps. A heap is a tree-based data structure that satisfies the heap property — that is for a max heap, the key of any node is less than or equal to the key of its parent (if it has a parent). This property can be leveraged to access the maximum element in the heap in O(logn) time using the maxHeapify method. We perform this operation n times, each time moving the maximum element in the heap to the top of the heap and extracting it from the heap and into a sorted array. Thus, after n iterations we will have a sorted version of the input array. The algorithm is not an in-place algorithm and would require a heap data structure to be constructed first. The algorithm is also unstable, which means when comparing objects with same key, the original ordering would not be preserved. This algorithm runs in O(nlogn) time and O(1) additional space [O(n) including the space required to store the input data] since all operations are performed entirely in-place.

The best, worst and average case time complexity of Heapsort is O(nlogn). Although heapsort has a better worse-case complexity than quicksort, a well-implemented quicksort runs faster in practice. This is a comparison-based algorithm so it can be used for non-numerical data sets insofar as some relation (heap property) can be defined over the elements.

An implementation in Java is as shown below :

import java.util.Arrays; public class Heapsort { public static void main(String[] args) { //test array Integer[] arr = {1, 4, 3, 2, 64, 3, 2, 4, 5, 5, 2, 12, 14, 5, 3, 0, -1}; String[] strarr = {"hope you find this helpful!", "wef", "rg", "q2rq2r", "avs", "erhijer0g", "ewofij", "gwe", "q", "random"}; arr = heapsort(arr); strarr = heapsort(strarr); System.out.println(Arrays.toString(arr)); System.out.println(Arrays.toString(strarr)); } //O(nlogn) TIME, O(1) SPACE, NOT STABLE public static <E extends Comparable<E>> E[] heapsort(E[] arr){ int heaplength = arr.length; for(int i = arr.length/2; i>0;i--){ arr = maxheapify(arr, i, heaplength); } for(int i=arr.length-1;i>=0;i--){ E max = arr[0]; arr[0] = arr[i]; arr[i] = max; heaplength--; arr = maxheapify(arr, 1, heaplength); } return arr; } //Creates maxheap from array public static <E extends Comparable<E>> E[] maxheapify(E[] arr, Integer node, Integer heaplength){ Integer left = node*2; Integer right = node*2+1; Integer largest = node; if(left.compareTo(heaplength) <=0 && arr[left-1].compareTo(arr[node-1]) >= 0){ largest = left; } if(right.compareTo(heaplength) <= 0 && arr[right-1].compareTo(arr[largest-1]) >= 0){ largest = right; } if(largest != node){ E temp = arr[node-1]; arr[node-1] = arr[largest-1]; arr[largest-1] = temp; maxheapify(arr, largest, heaplength); } return arr; } }

Implementation in C++

#include <iostream> using namespace std; 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) { 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 printArray(int arr[], int n) { for (int i=0; i<n; ++i) cout << arr[i] << " "; cout << "\n"; } int main() { int arr[] = {12, 11, 13, 5, 6, 7}; int n = sizeof(arr)/sizeof(arr[0]); heapSort(arr, n); cout << "Sorted array is \n"; printArray(arr, n); }

Visualization

More Information:

This article needs improvement. You can help improve this article. You can also write similar articles and help the community.