堆排序-从小到大-创新互联

利用数组模拟一棵完全二叉树，根据数组下标可以快速确定一个结点的左右孩子和父母。
例如根结点下标为5，下标10为其左孩子，11为右孩子，2为双亲。
非常适合处理的问题：在只能存储一定数据时，而总元素个数较大，只需取前k个小的数
时间复杂度O(nlogn)

#include#include#include#include
#include#includeusing namespace std;

#define N 100005
#define pi 3.14159
typedef long long ll;

int a[N];//存储数据

void adjustHeap(int i, int len)//调整堆//down
{a[0] = a[i];//a[0]保存根的值
	for (int j = 2 * i; j<= len; j*=2)//找更大的孩子
	{if (j< len && a[j]< a[j + 1]) j++;//a[j]为左孩子，a[j+1]为右孩子
		if (a[0] >= a[j]) break;//根已经比孩子大，符合大顶堆
		else
		{	a[i] = a[j];//将大的孩子的值给根
			i = j;//选定的孩子作为新根
		}
	}
	a[i] = a[0];//归还
}

void creatHeap(int len)//建堆
{for (int i = len / 2; i >0; i--)
	{adjustHeap(i, len);
	}
}

void heapSort(int len)
{creatHeap(len);
	for (int i = len; i >1; i--)
	{swap(a[1], a[i]);//将堆顶的大元素放到最后面
		adjustHeap(1, i - 1);
	}
}

int main()
{int n;
	scanf("%d", &n);
	for (int i = 1; i<= n; i++)
	{scanf("%d", &a[i]);
	}
	heapSort(n);
	for (int i = 1; i<= n; i++)
	{printf("%d ", a[i]);
	}



	return 0;
}

实现从小到大排序则建立大顶堆，实现从大到小建立小顶堆

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧