堆排序详解 top-ag真人游戏

 向下调整建堆

 分析

向下调整时要保证以起始节点为堆顶的树的左子树和右子树为堆

从第一个非叶子节点为堆顶开始向下调整

从后往前，依次向下调整

图解

时间复杂度 

代码实现

//建小堆为例
void down(hpdatatype* a, size_t parent, size_t size)
{
	size_t child = parent * 2   1;
	while (child < size)
	{
		if (child   1 =0; i--)
	{
		down(a,i, size);
	}
}

总结 

向上调整建堆
时间复杂度为o(n*logn)

向下调整建堆
时间复杂度为o(n)

因此采用向下调整建堆效率更高

排序 

升序建大堆

降序建小堆

思路分析

1. 注意：我们只是对数组进行向上或向下调整使它变成堆

           没有创建删除堆顶元素插入、入堆等功能接口

           因此heaptop入数组和heappop删堆顶不能用

2. 可能有小伙伴说，那我建立这两个函数接口再使用不就行了嘛？

不可以，如果这样做，那么必然会开辟新数组将堆顶元素放入

空间复杂度变为o(n)

原本建好的堆进行堆顶与末尾的交换删除

不符合我们的优化目标

3. 那么要使空间复杂度为o(1),就必须在原数组中进行排序

排序思想

1.交换堆顶与末尾节点的元素

2.对堆前n-1个节点从堆顶开始进行向下调整

3.此时堆顶元素为最大或最小的元素

4.交换堆顶元素与第n-1个元素

5.重复上述过程，完成升序或降序

注意：末尾节点的下标更新

降序建小堆证明

 升序建大堆同理分析即可。

结论：升序建大堆   降序建小堆

代码实现

先向下调整建堆(效率高)

i 为第一个非叶子节点下标

记录最后一个数据下标 end

当end=1时，结束交换和向下调整

注意：向下调整函数参数

a为数组起始地址

parent为双亲节点的下标

size为调整的元素个数

void down(hpdatatype* a, size_t parent, size_t size);

下面代码中要注意end代表的含义

while前代表最后一个元素下标

while中代表的是要调整的元素个数

void heapsort(int* a,int size)
{
	//升序建大堆
	//降序建小堆
	for (int i = (size-1-1)/2; i>=0; i--)
	{
		down(a,i, size);
	}
	//最后一个数据的下标
	size_t end = size - 1;
	while (end>0)
	{
		swap(&a[0],&a[end]);
		down(a,0,end);
		end--;
	}
}

这样堆排序就可以实现啦

决定升序还是降序，创建大堆或小堆即可

小堆变大堆：

改变建堆时的大于小于号即可

child和child 1、child和parent的比较符号

什么是top-k问题？

即求数据结合中前k个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于top-k问题，能想到的最简单直接的方式就是排序

如果数据量非常大(几十个g)，排序就不太可取了，内存会非常大，效率极低

最佳的方式就是用堆排序来解决

思路

1. 用数据集合中前k个元素来建堆
    前k个最大的元素，则建小堆
    前k个最小的元素，则建大堆
2. 用剩余的n-k个元素依次与堆顶元素来比较

    小堆时，比堆顶大的元素替换堆顶

    向下调整，保证堆的结构

    大堆时，比堆顶小的元素替换堆顶

    向下调整，保证堆的结构

依次比较完后，堆里面就是所有数据中最大或最小的前k个元素

只需要遍历一次即可

时间复杂度

建立堆为k，最坏情况下剩余的n-k个数都要进行调整

调整次数为logk*(n-k)次

o(k logk*(n-k))

k大小不确定，不能省略

空间复杂度

只需要开辟k个空间来建堆

o(k)

代码实现

//top-k问题
void printtopk(int* a, int n, int k)
{
	// 1. 建堆--用a中前k个元素建堆
	int* kheap = (int*)malloc(sizeof(int)*k);
	if (kheap == null)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	//将前k个数插入数组kheap中
	for (int i = 0;i= 0; i--)
	{
		down(a, i, k);
	}
	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
	for (int i = k;ikheap[0])
		{
			kheap[0] = a[i];
			down(kheap,0,k);
		}
	}
	// 3. 打印最大或最小的前k个
	for (int j = 0;j

//top-k问题
void printtopk(int* a, int n, int k)
{
	// 1. 建堆--用a中前k个元素建堆
	int* kheap = (int*)malloc(sizeof(int)*k);
	if (kheap == null)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	//将前k个数插入数组kheap中
	for (int i = 0;i= 0; i--)
	{
		down(a, i, k);
	}
	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
	for (int i = k;ikheap[0])
		{
			kheap[0] = a[i];
			down(kheap,0,k);
		}
	}
	// 3. 排序
	//最后一个数据的下标
	size_t end = k - 1;
	while (end>0)
	{
		swap(&kheap[0], &kheap[end]);
		down(kheap, 0, end);
		end--;
	}
	// 4. 打印排序后的前k个
	for (int j = 0;j