Heap Sort
Heap Sort is a comparison-based sorting algorithm that works by utilizing a binary heap data structure. It was introduced by J. W. J. Williams in 1964. Heap Sort has a time complexity of O(n log n) for both the average and worst-case scenarios, making it an efficient sorting algorithm for large datasets. Heap Sort is performed in-place, but it is not a stable sort, which means that the relative order of equal elements might not be preserved.
AlgorithmEdit
The Heap Sort algorithm works by building a binary heap (either a max-heap or a min-heap) from the input data, then repeatedly extracting the maximum or minimum element and inserting it at the end of the sorted part of the array. The algorithm continues until the heap is empty, and the entire array is sorted.
The key steps in the Heap Sort algorithm are:
- Build a binary heap from the input data (either a max-heap or a min-heap).
- Repeatedly extract the maximum or minimum element from the heap and insert it at the end of the sorted part of the array.
- Continue until the heap is empty and the entire array is sorted.
PseudocodeEdit
Here is a high-level pseudocode for the Heap Sort algorithm:
function heapSort(arr) buildMaxHeap(arr) for i = arr.length - 1 to 1 swap arr[0] and arr[i] maxHeapify(arr, 0, i) end for end function function buildMaxHeap(arr) for i = arr.length / 2 - 1 to 0 maxHeapify(arr, i, arr.length) end for end function function maxHeapify(arr, i, heapSize) largest = i left = 2 * i + 1 right = 2 * i + 2 if left < heapSize and arr[left] > arr[largest] largest = left end if if right < heapSize and arr[right] > arr[largest] largest = right end if if largest != i swap arr[i] and arr[largest] maxHeapify(arr, largest, heapSize) end if end function
C++ ExampleEdit
Here is a C++ implementation of the Heap Sort algorithm:
#include <iostream> #include <vector> void swap(int & a, int & b) { int temp = a; a = b; b = temp; } void maxHeapify(std::vector < int > & arr, int i, int heapSize) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < heapSize && arr[left] > arr[largest]) { largest = left; } if (right < heapSize && arr[right] > arr[largest]) { largest = right; } if (largest != i) { swap(arr[i], arr[largest]); maxHeapify(arr, largest, heapSize); } } void buildMaxHeap(std::vector < int > & arr) { for (int i = arr.size() / 2 - 1; i >= 0; i--) { maxHeapify(arr, i, arr.size()); } } void heapSort(std::vector < int > & arr) { buildMaxHeap(arr); for (int i = arr.size() - 1; i > 0; i--) { swap(arr[0], arr[i]); maxHeapify(arr, 0, i); } } int main() { std::vector < int > arr = { 12, 11, 13, 5, 6, 7 }; int n = arr.size(); heapSort(arr); std::cout << "Sorted array: \n"; for (int i = 0; i < n; i++) std::cout << arr[i] << " "; std::cout << std::endl; return 0; }