【数据结构】堆排序及TOP-K问题

前面我们已经学了堆的实现，今天一起来看一下堆的应用：1.堆排序  2.TOP-K问题

堆排序就是利用堆的思想进行排序，它分为两个步骤：

1.建堆  2. 利用堆删除的思想进行排序

假设我们现在想要将一组数据进行升序排列，那我们该怎么怎么做的？

我们刚刚也说了是利用堆的思想进行排序，那肯定是先建堆了。

那么问题来了，我们是想进行排序，结果在排序之前我要把堆的实现代码敲出来，这不是很费事吗，其实我们不用敲出堆实现的代码，我们都知道堆在物理层面是数组，在逻辑层面是堆，我们只要将要排序的一组数改成堆就行，实际上不用堆实现的那么多接口。

现在假设我们已经将堆建好，那么怎样利用堆删除的思想进行排序呢，一起来看一下吧！

假设我们要排的一组数据为 4 3 2 1，我们都知道堆有大堆和小堆，这里我们先建立小堆，即：

 

 下面我们开始利用堆删除的思想进行排序：

 这样我们就将顺序排列好了，可以看出它是依照降序排列而我们要的呢是升序，所以这里我们要建立大堆。

即 升序：建大堆

     降序：建小堆

代码：

//交换
void Swap(HDType* data1, HDType* data2)
{
	HDType temp = *data1;
	*data1 = *data2;
	*data2 = temp;
}
 
//向上调整
void AdjustUp(HDType* data, int child)
{
	HDType parent = (child - 1) / 2;
 
	while (child > 0)
	{
		if (data[child] > data[parent])
		{
			Swap(&data[child], &data[parent]);
		}
		child = parent;
		parent = (child - 1) / 2;
	}
}
 
//向下调整
void AdjustDown(HDType* data,int size,int parent)
{
	int child = 2 * parent + 1;
	while (child < size)
	{
 
		if (child + 1 < size && data[child + 1] > data[child])
		{
			child++;
		}
		if (data[child] > data[parent])
		{
			Swap(&data[parent], &data[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
 
void sort(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		AdjustUp(arr, i);
	}
 
while (n > 0)
	{
		Swap(&arr[0], &arr[n - 1]);
		n--;
		AdjustDown(arr, n, 0);
	}
}
void test2() 
{
	int arr[] = { 10, 9, 8, 7, 6, 5, 4, 3,2, 1 };
	int len = sizeof(arr) / sizeof(arr[0]);
	sort(arr, len);
 
	for (int i = 0; i < len; i++)
	{
		printf("%d ",arr[i]);
	}
}
 
int main()
{
	//test();
	test2();
	return 0;
}

这里建堆的方式我选择的是向上建堆，小伙伴们也可以试试先向下建堆的方式。

2.TOP-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。比如：专业的前100名、世界500强企业、富豪榜等等。

对于TOP-K问题我们首先想到的方法应该是排序，即将所有数据进行升序或者降序排列取前K个或者后K个，但我们要考虑这样一个问题，如果数据量非常大，如果我们进行排序那内存可能出现存不下这么多数据的问题，那排序就不能实现。最佳的方法还是用堆来实现，基本思路如下：

1.用数据的前K个元素来建堆

要找出前K个最大的数据就要建小堆，相反找前K个最小的数据要建大堆。

为什么呢？假如我们要找出一组数据中前10个最大的数，按照上述我们要建立小堆，即堆顶最小，然后我们一次将剩下的数据与堆顶元素比较，若比堆顶大，则将堆顶元素替换下来，然后我们在调整堆，这样堆顶的元素始终是堆中最小的，遇到比他大的就替换、调整，一直遍历到数据的最后一个那么最大的K个数据也就被选了出来。找K个最小的数据思路也是相同。

2.用剩余的N-K个元素一次与堆顶元素比较，比堆顶大就进堆（比堆顶小就进堆）也就是上面解释的那样

代码：

void PrintTopk(int* arr, int n, int k)
{
 
	int* Topk = (int*)malloc(sizeof(int) * k);
	assert(Topk);
	for (int i = 0; i < k; i++)
	{
		Topk[i] = arr[i];
	}
 
	//向上建堆
	/*for (int i = 0; i < k; i++)
	{
		AdjustUp(arr, i);
	}*/
 
	//向下建堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(Topk, k, i);
	}
 
 
	for (int i = k; i < n; i++)
	{
		if (arr[i] > Topk[0])
		{
			Topk[0] = arr[i];
			AdjustDown(Topk, k, 0);
		}
	}
 
	for (int i = 0; i < k; i++)
	{
		printf("%d ", Topk[i]);
	}
}
 
void test3()
{
	int arr[] = { 100, 22, 45, 6, 9, 45, 12, 33, 78, 69, 10, 44, 59, 58 };
	int len = sizeof(arr) / sizeof(arr[0]);
	PrintTopk(arr, len, 5);
}
 
int main()
{
	test3();
	return 0;
}

今天的分享就到这了，以上若有错误，恳请指正，感激不尽！！！