Definition
Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It works by first transforming the array into a max-heap (where the parent node is always greater than its children), then repeatedly extracting the maximum element from the heap and rebuilding the heap until all elements are sorted.
Constraints
- Not a stable sort (does not maintain relative order of equal elements)
- Poor cache performance compared to Quick Sort and Merge Sort
- Efficient for large datasets but often slower in practice than Quick Sort
- Limited adaptability - doesn't take advantage of existing order in input
Step-by-step explanation
Arguments:
- Array to be sorted -
array
- Heap size -
heapSize
- Current index in heap -
i
- Left child index -
left
- Right child index -
right
- Largest element index -
largest
Explanation:
- Build a max-heap from the input array:
- Start from the last non-leaf node (parent of last element)
- Heapify each node to maintain max-heap property
- Repeatedly extract maximum element from heap:
- Swap root (maximum element) with last element
- Reduce heap size by one (excluding sorted elements)
- Heapify the new root to maintain max-heap property
- Repeat extraction until heap contains only one element
- The array is now sorted in ascending order
Returns:
Returns nothing (sorts array
in-place)
Modifies the original array instead of returning a new one
No explicit return value (void function in most implementations)