Implementing the Heap Sort Algorithm in C++

Heap sort is an efficient sorting algorithm based on the heap data structure, with a time complexity of O(n log n) and a space complexity of O(1), making it suitable for large-scale data. A heap is a special complete binary tree, divided into max heaps (parent ≥ children) and min heaps, with max heaps commonly used in sorting. It is stored in an array where the parent of index i is (i-1)/2, and the left and right children are 2i+1 and 2i+2, respectively. The core steps are: 1. Constructing the initial max heap (adjusting from the last non-leaf node upwards); 2. Sorting (swapping the top element with the end of the unsorted part, adjusting the heap, and repeating until completion). The C++ implementation includes swap, max_heapify (iteratively adjusting the subtree to form a max heap), and heap_sort (constructing the heap and performing sorting) functions. The main function tests array sorting, and the output result is correct.