排序与查找
堆排序
堆排序靠的是一个巧妙的数据结构：二叉堆。它先把数组重排成一个大顶堆——一种每个父节点都不小于其子节点的形状，于是最大的元素浮到了顶端（数组的最前面）。接着它反复把这个顶端元素交换到末尾、把堆的规模缩小一个，再让堆自我修复——每一轮都剥下当前剩余的最大元素，直到数组排好序。
妙处在于这个堆就住在同一个数组里，用下标算术（位置 i 的子节点在 2i+1 和 2i+2）代替指针。建堆耗时 O(n)，而 n 次取最大值的每一步都要花 O(log n) 把新的根下沉回它该在的层级——也就是堆的高度。
相乘就得到最好、平均、最坏情况下都一样的 O(n log n) 时间——堆排序和归并排序一样，没有“坏输入”。更好的是，它原地排序，只需 O(1) 额外空间，这一点强过归并排序。它的弱点是不稳定，而且它跳跃、分散的内存访问不如快速排序对缓存友好，所以实践中通常稍慢一点。它的长处是作为最坏情况安全的兜底方案——这正是内省排序在快排递归过深时改用堆排序的原因。
void heapsort(std::vector<int>& a) {
std::make_heap(a.begin(), a.end()); // build max-heap, O(n)
for (auto end = a.end(); end != a.begin(); --end)
std::pop_heap(a.begin(), end); // move max to the back, O(log n)
} // array is now sorted ascendingn 次取出 × 每次 O(log n) 的下沉 = O(n log n)，原地排序，额外空间 O(1)。
堆排序和归并排序都保证 O(n log n)；堆排序在空间上胜出（O(1) 原地，对比 O(n)），但在稳定性上落败（堆排序不稳定，归并排序稳定）。C++ 把底层机制暴露为 std::make_heap、std::push_heap 和 std::pop_heap。
又称
另见