堆排序是一种利用堆结构进行排序的算法，堆是一种特殊的树形数据结构，满足以下性质：

1. 堆中任意节点的值都不大于或不小于其子节点的值，分别称为最大堆和最小堆；
2. 堆总是一棵完全二叉树。

堆排序的基本思路是先将待排序数组构建成一个堆，然后依次将堆顶元素（最大元素或最小元素）取出并放到最终的有序序列中，再重新调整堆使其满足堆的性质。具体实现可以分为两个过程：构建堆和排序。

构建堆：

1. 从待排序数组中选取一个节点作为根节点，将其与最后一个节点交换，使最后一个节点成为新的根节点。
2. 对新的根节点进行下沉操作，即将其与其子节点中较大（或较小）的一个交换位置，直到堆的性质被满足。
3. 重复步骤 1 和 2 直到所有节点都被遍历过。

排序：

1. 依次将堆顶元素（最大元素或最小元素）取出并放到最终的有序序列中；
2. 将堆的最后一个元素放到堆顶，重新调整堆使其满足堆的性质；
3. 重复步骤 1 和 2 直到所有元素都被取出。

下面是堆排序的实现（以最大堆为例）：

void heapInsert(vector<int>& array, int targetIndex)
{while (array[targetIndex] > array[(targetIndex - 1) / 2]){swap(array[targetIndex], array[(targetIndex - 1) / 2]);targetIndex = (targetIndex - 1) / 2;}
}void heapify(vector<int>& array, int index, int heapSize)
{while (index < heapSize){int maxChildIndex;int leftChildIndex = index * 2 + 1;if (leftChildIndex >= heapSize){return;}int rightChildIndex = leftChildIndex + 1;if (rightChildIndex >= heapSize){maxChildIndex = leftChildIndex;}else{maxChildIndex = array[leftChildIndex] > array[rightChildIndex] ? leftChildIndex : rightChildIndex;}if (array[index] > array[maxChildIndex]){return;}swap(array[index], array[maxChildIndex]);index = maxChildIndex;}
}void heapSort(vector<int>& array)
{int n = array.size();if (n < 2){return;}// Build the max heapfor (int i = 0; i < n; ++i){heapInsert(array, i);}// Take the max value, and use the last element to do the heapify jobfor (int i = array.size() - 1; i > 0; --i){swap(array[0], array[i]);heapify(array, 0,i);}
}

堆排序的时间复杂度为 $O(nlogn)$，空间复杂度为 $O(1)$。