堆排序有两个过程
下标为i的节点的父节点下标: (i-1)/2 整除
下标为i的节点的左孩子下标:i*2+1
下标为i的节点的右孩子下标:i*2+2
待排序序列为:
2 3 8 1 4 9 10 7 16 14
1.建大顶堆
首先建立无序堆
然后建立大顶堆:从右往左,从下往上,递归的选择子节点最大的往上浮
首先14大于4,所以上浮
其次是16,上浮
依次上浮,完毕后如图
2.堆排序
建立大顶堆后进行堆排序,我们将首尾的节点互换,拿到最大值
然后对新的堆进行维护,维护的方式与建立大顶堆的方式一样,维护一次后如图
依次交换堆顶和末尾元素,然后维护大顶堆
.......往下递归即可,最后得到有序序列,至此完成堆排序。
代码如下:
#include<iostream>
using namespace std;
void print_arr(int arr【】, int n) {
for (int i = 0; i < n; i++) {
cout<< " " << arr【i】;
}
putchar('\n');
}
void swap(int *a,int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
/*
arr 存贮数组
n 数组长度
i 代维护节点下标
*/
void heapify(int arr【】, int n, int i) {
int largest = i;
int lson = i * 2 + 1;
int rson = i * 2 + 2;
if (lson < n && arr【largest】 < arr【lson】)
largest = lson;
if (rson < n && arr【largest】 < arr【rson】)
largest = rson;
if (largest != i) {
swap(&arr【largest】, &arr【i】);
heapify(arr, n, largest);
}
}
//堆排序入口
void heap_sort(int arr【】,int n){
//建堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
//排序
for (int i = n - 1; i >= 0; i--) {
swap(&arr【i】, &arr【0】);
heapify(arr, i, 0);
}
}
int main() {
int arr【】 = { 2,3,8,1,4,9,10,7,16,14 };
int n = 10;
print_arr(arr, n);
heap_sort(arr, n);
print_arr(arr, n);
return 0;
}
标签:大顶,arr,下标,int,内附,堆排序,详解,节点
From: https://www.cnblogs.com/dwinternet/p/18363393