C++实现堆排序

C++实现堆排序

堆是一种重要的数据结构，可以用来维护一些有序性质。其中最常用的就是堆排序算法。堆排序算法是一种不稳定的排序算法，时间复杂度为 O(nlogn)，并且它是原址排序算法，不需要额外的存储空间。

堆的基本概念

• 堆是一种完全二叉树。
• 堆中每个节点的关键字都大于等于或小于等于其子节点的关键字，称之为大顶堆或小顶堆。
• 为了方便比较，我们通常认为所有节点都小于等于其左右子节点的关键字（小顶堆）。

堆排序的基本思想

• 将待排序序列建立成一个大顶堆或小顶堆，这里以大顶堆为例。
• 将堆顶元素和堆底元素交换位置，将最大元素沉到数组末尾。
• 然后重新调整剩余的 n-1 个元素，使其重新构成一个大顶堆，并重复步骤 2、3，直到排序完成。

C++代码实现

#include <iostream>