堆排序

堆排序

1. 堆排序的最坏、最好和平均时间复杂度为O(nlogn)
2. 以数组来描述堆：以子节点求父节点=(i-1)/2，以父节点求子节点=2i+1 2i+2
3. 堆是完全二叉树
4. 堆的每个节点的值都大于等于/小于等于其左右子节点的值，a[i]>=a[2i+1]&&a[i]>=a[2i+2]
5. 堆排序：

• 堆化操作：完成每个子树的堆化
• 从倒数第二层开始网上开始做堆化操作
• 将堆顶的最大值移到末尾，将树长度-1，循环完成堆排序

#include <iostream>
#include <vector>
using namespace std;

void heap_sort(vector<int>& tree, int& n);
void heap_build(vector<int>& tree, int& n);
void heapify(vector<int>& tree, int& n, int i);

int main() {
	vector<int> tree{1,4,10,5,8,3,7,2,9};
	int len=tree.size();

	heap_sort(tree,len);

	for(int i=0; i<len; ++i)
		cout<<tree[i]<<" ";

	return 0;
}

void heapify(vector<int>& tree, int& n, int i)
{
	if(i>=n)
		return;

	int c1=2*i+1;
	int c2=2*i+2;
	int maxNum=i;

	if(c1<n && tree[c1]>tree[maxNum])
		maxNum=c1;

	if(c2<n && tree[c2]>tree[maxNum])
		maxNum=c2;

	if(maxNum!=i)
	{
		swap(tree[maxNum],tree[i]);
		heapify(tree, n, maxNum);
	}
}

void heap_build(vector<int>& tree, int& n)
{
	int parent=(n-1)/2;
	for(int i=parent; i>=0; --i)
	{
		heapify(tree, n, i);
	}
}

void heap_sort(vector<int>& tree, int& n)
{
	heap_build(tree, n);

	for(int i=n-1; i>=0; --i)
	{
		swap(tree[i],tree[0]);
		heapify(tree, i, 0);
	}
}