堆是一种非常重要的数据结构 , 堆排序是时间复杂度为O(nlogn)的排序算法 , 值得学习

堆结构

1.堆在逻辑上可以看做一颗完全二叉树 , 完全二叉树指满二叉树或从左向右依次渐满的二叉树 , 可以用一维数组来表示 , 数组下标为0的数为堆顶 ,1和2分别为它的左孩子和右孩子, 对于数组下标为n的节点,其父节点下标为(n – 1)/2 , 左孩子下标为 2 × n + 1 ,右孩子下标为 2 × n + 2.

2.将根节点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆 , 堆排序可以使用这两者的任意一个.

建堆

1. 首先，定义一个变量 heapsize，初始值为0，表示堆的大小。堆是一个完全二叉树的数据结构，我们从数组的下标0开始构建它。
2. 从数组下标为0的元素开始，逐个检查每个元素。对于每个元素，我们将其与其父节点进行比较。
3. 如果当前元素比其父节点大，就交换当前元素与其父节点的值，然后继续向上比较，直到当前元素不再比其父节点大为止。
4. 然后，增加 heapsize 的值，表示堆的大小增加了1。
5. 对于下一个元素重复上述操作，直到遍历到数组的最后一个元素为止。
6. 完成建堆过程，确保数组中的元素构成一个大根堆。

// 使某个数以上面所讲逻辑向上浮的函数 , 
void up(int arr[],int index){ // arr为数组,index为需要上浮的数的下标
	while(arr[index] > arr[(index - 1) / 2]){ // 当index比它的父节点大时
		swap(arr[index],arr[(index - 1) / 2]); // 交换index和其父节点的值
		index = (index - 1) / 2; // 现在index在原父节点的位置 , 更新index
	}
}
int buildheap(int arr[],int n){ // n为数组长度
        int heapsize = 0;

        for(int i = 0 ; i < n ; ++i){
	        up(arr,i);
         }
        heapsize = n;
        return heapsize;
}

堆排序

1. 假设你拥有一个大根堆，堆顶元素是堆中的最大值。
2. 首先，将堆顶元素与堆中的最后一个元素进行交换。然后，将堆的大小（heapsize）减一，这样原本在堆顶的最大元素就被从堆中移除了。
3. 接下来，需要对新的堆顶元素进行操作，以确保它仍然满足大根堆的性质。
4. 从堆顶元素开始，比较它与其两个孩子中的较大者。如果堆顶元素比较大，那么堆已经满足大根堆的性质，操作结束。
5. 如果堆顶元素比较小，那么将堆顶元素与较大的孩子元素进行交换，并重复第4步，直到堆顶元素比它的两个孩子都大，或者达到堆的底部

// 使某个数按上面逻辑下沉的函数
void down(int arr[],int heapsize,int index){ // heapsize为堆的大小 , index为需要下沉数的下标
	int leftson = index * 2 + 1; // 该数左孩子的下标
	while(leftson < heapsize){ // 保证该数有左孩子
		int larger = leftson + 1 < heapsize && arr[leftson + 1] > arr[leftson] ? leftson + 1 : leftson;  // 若无右孩子,则左孩子必然最大,若有右孩子,则选出左右孩子中较大的那个
		larger = arr[larger] > arr[index] ? larger : index; // 较大孩子与该数进行比较
		if(larger == index){ // 若该数就是最大的那一个,堆结构已经复原,跳出循环
			break;
		}  
		swap(arr[index],arr[larger]); // 若该数小于它的某个孩子 , 交换
		index = larger; // 该数到了它这个孩子原本的位置
		leftson = index * 2 + 1;  // 更新新的左孩子的位置
	}
}

现在我又重新拥有了一个大根堆 , 重复上面操作 , 直到所有数都到了它该在的位置 , 数组变为有序

up 和 down两个函数构成了维护一个大根堆的基本操作 , 称为”堆化”

完整代码

#include<bits/stdc++.h>
using namespace std;

void up(int arr[],int index){
	while(arr[index] > arr[(index - 1) / 2]){
		swap(arr[index],arr[(index - 1) / 2]);
		index = (index - 1) / 2;
	}
}
void down(int arr[],int heapsize,int index){
	int leftson = index * 2 + 1;
	while(leftson < heapsize){
		int larger = leftson + 1 < heapsize && arr[leftson + 1] > arr[leftson] ? leftson + 1 : leftson; 
		larger = arr[larger] > arr[index] ? larger : index;
		if(larger == index){
			break;
		}

		swap(arr[index],arr[larger]);
		index = larger;
		leftson = index * 2 + 1; 
	}
}
void heapsort(int arr[],int n){
	int heapsize = 0;

	for(int i = 0 ; i < n ; ++i){
		up(arr,i);
	}
	heapsize = n;

	while(heapsize > 0){
		swap(arr[0],arr[heapsize-1]);
		heapsize--;
		down(arr,heapsize,0);
	}
	
}



int main(){
	int n ;
	random_device rd;
        mt19937 gen(rd());
        uniform_int_distribution<int> dis(0, 100);
	cin >> n;
	int arr[n];
	for(int i = 0 ; i < n; ++i){
		arr[i] = dis(gen);
	}
	for(int i = 0 ; i < n ; ++i){
		cout <<arr[i] << " ";
	}
	cout << endl;
	heapsort(arr,n);
	for(int i = 0 ; i < n ; ++i){
		cout <<arr[i] << " ";
	}
	
	return 0;
}

Mareep