堆排序

堆排序是将数组构建成大顶堆，即根节点是数组中最大元素，将根节点与堆底最后一个元素交换，使得最大值排到末尾，即已排序好。将剩下的n-1个元素重新调整为大顶堆，在堆顶/根节点处得到第二大的值，与堆底最后一个元素交换，便又排序好一个元素。

算法描述

1. 将数组构建成大顶堆
2. 交换堆顶元素和堆底元素
3. 调整堆，使其重新成为大顶堆
4. 重复步骤2和步骤3 n-1次，排序完成。n为数组长度。

堆分为两类：

1. 最大堆（大顶堆）：堆的每个父节点都大于其孩子节点；
2. 最小堆（小顶堆）：堆的每个父节点都小于其孩子节点；

堆的存储：

一般都用数组来表示堆，i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。

堆排序的步骤分为三步:

1. 建堆（升序建大堆，降序建小堆）；
2. 交换数据；
3. 向下调整。

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

void swap(vector<int>& arr, int i, int j) {
	int tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
}

//i位置与其父节点的位置进行比较，如果大于父节点，就交换
void heapInsert(vector<int>& arr, int i) {
	while (arr[i] > arr[(i - 1) / 2]) {
		swap(arr, i, (i - 1) / 2);
		i = (i - 1) / 2;
	}
}
//当大顶堆中某一个元素发生变化的时候，取该元素的左右子节点较大的一个，
//这个最大子节点再和这个修改的元素作比较，子节点大则交换。
void heapify(vector<int>& arr, int size) {
	int i = 0;
	int left = 1;
	int largest;
	while (left < size) {
	    //取该元素的左右子节点较大的一个
		largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
		//比较子节点和被修改元素的大小
		largest = arr[i] > arr[largest] ? i : largest;
		if (largest == i) {
			break;
		}
		swap(arr, largest, i);
		i = largest;
		left = i * 2 + 1;
	}
}

void heapSort(vector<int>& arr) {
	for (int i = 0; i < arr.size(); ++i) {
		heapInsert(arr, i);
	}
	for (int i = arr.size() - 1; i >= 0; --i) {
		swap(arr, 0, i);
		heapify(arr, i);
	}
}

int main() {
	int n;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; ++i) {
		cin >> arr[i];
	}
	heapSort(arr);
	for (int i = 0; i < n; ++i) {
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}