C++超详细实现堆和堆排序过像
堆是一种特殊的数据结构，它是一棵完全二叉树，且在堆中的任何一个父节点的键值都比它的孩子节点的键值大（或小），我们称之为大根堆或小根堆。堆具有以下性质：
1. 堆中某个节点的值总是不大于(或不小于)其父节点的值；
2. 堆总是一棵完全树。
堆有两种类型：大根堆和小根堆。
大根堆：每个结点的值都大于或等于其子节点的值，同时根节点的值最大。
小根堆：每个结点的值都小于或等于其子节点的值，同时根节点的值最小。
下面我们来介绍堆的实现和堆排序过程。
1. 堆的实现
堆的实现通常采用数组来表示。我们假设数组的下标从1开始，那么对于任意一个节点的下标i，其左子节点的下标为2i，右子节点的下标为2i+1，其父节点的下标为i/2。
我们可以使用一个数组来表示堆，数组的 个元素留空，从第二个元素开始存储堆元素，这样我们就可以根据上面介绍的公式确定任意一个节点在数组中的下标。
2. 堆的操作
（1）建立堆
我们可以将无序数组通过插入的方式构建成一个堆，但这种方法效率较低，因为每次插入一个元素都需要维护堆的性质，时间复杂度为O(nlogn)。
另一种方法就是利用建立堆的过程，只需O(n)的时间建立一个堆。具体做法是，对于一个无序数组，从最后一个非叶子节点开始，依次向上调整节点的位置，使得其子树成为一个堆。不断向上调整，最终整个数组就成为一个堆。这个过程叫做“堆化”。
堆化的实现过程如下：
1）从最后一个非叶子节点开始，依次将其子树变成堆。
2）依次将每个非叶子节点向上调整位置，直到每个子树都是一个堆。
具体代码实现如下：
void adjust_heap(int a[],int i,int len){
int left=2*i;
int right=2*i+1;
int max=i;
if(left<=len&&a[left]>a[max]){
max=left;
}
if(right<=len&&a[right]>a[max]){
max=right;
}
if(max!=i){
swap(a[i],a[max]);
adjust_heap(a,max,len);
}
}
void build_heap(int a[],int len){
for(int i=len/2;i>=1;i--){
adjust_heap(a,i,len);
}
}
（2）插入元素
插入元素要维持堆的性质，我们通常将新元素插入堆的最后一个位置，然后向上调整。
具体代码实现如下：
void insert(int a[],int& len,int value){
a[++len]=value;
int i=len;
while(i>1&&a[i]>a[i/2]){
swap(a[i],a[i/2]);
i/=2;
}
}
（3）删除堆顶元素
堆的性质是根节点的元素最大（或者最小）。为了维持堆的性质，我们需要将堆的最后一个元素移到根节点，然后向下调整。
具体代码实现如下：
void remove_top(int a[],int& len){
a[1]=a[len];
len--;
adjust_heap(a,1,len);
}
3. 堆排序
堆排序是利用堆这种数据结构设计的一种排序算法，其基本原理是：将待排序元素构造为堆，然后不断将堆顶元素弹出，直到全部元素都弹出，这样就得到一个有序序列。
堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)，是一种比较高效且稳定的排序算法。
堆排序的实现过程如下：
1. 从待排序序列构建一个最大堆。
2. 从堆顶开始，和堆底交换位置，然后重新维护堆的性质。
3. 重复步骤2，直到所有元素都被弹出堆，形成一个有序序列。
具体代码实现如下：
void heap_sort(int a[],int len){
build_heap(a,len);
for(int i=len;i>=1;i--){
swap(a[1],a[i]);
adjust_heap(a,1,i-1);
}
}
总结
堆是一种非常重要的数据结构，堆排序利用了堆的性质实现了一种高效的排序算法。堆可以用来解决许多算法问题，如TopK问题、最小/大值问题等。堆的实现比较简单，但是需要掌握其基本操作，包括建立堆、插入元素、删除堆顶元素和堆排序等。