A heap is a specialized tree-based data structure that satisfies the heap property. It's commonly used to implement priority queues and for efficient sorting (heapsort). Heap Property Max-Heap Property For every node $i$ other than the root: $$ A[\text{parent}(i)] \geq A[i] $$ The parent's value is greater than or …

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure. It has guaranteed $O(n \log n)$ time complexity and sorts in-place. Algorithm Overview Build Max Heap: Convert array into max heap Extract Max: Repeatedly remove max element and rebuild heap Key Properties Time: $O(n \log n)$ for …