Function heap_sort

pub fn heap_sort(heap: &mut Heap<i32>)

Sorts a heap in ascending order (min heap) or descending order (max heap)

Heap sort transforms its elements into a heap, then repeatedly removes the largest (or smallest) element and places it in the correct position, restoring the heap property after each removal.

Parameters

• &mut Heap<i32>: a mutable reference to a Heap instance and sorts its elements

If the heap is configured as a max-heap, the elements will be sorted in ascending order. If it’s a min-heap, the elements will be sorted in descending order.

Time Complexity

• Best: O(n log n)
• Worst: O(n log n)
• Average: O(n log n)

Space Complexity

• O(n + k)

Examples

use dsa::algorithms::sorting::heap_sort;
use dsa::data_structures::heap::Heap;
 
let mut heap = Heap::new(false); // Min-heap
heap.values = vec![3, 1, 6, 5, 2, 4];
heap_sort(&mut heap);
assert_eq!(heap.values, vec![6, 5, 4, 3, 2, 1]);