欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

堆排序和TopK问题

程序员文章站 2024-03-15 21:48:12
...

堆是一种很有趣的数据结构,有最大堆和最小堆两种形式,在上一篇文章里已经讲到了最大最小堆的建立;

这里用一下堆的方法解决问题。

     1.首先是在一大堆数字中找到K个最大或最小的数字(topK问题)

topK问题是生活中很常见的问题;比如找到N个在某个科目成绩最好的同学,或者在很多游戏中都会有很多数据分析结果,年度评价之列的都是什么游戏时间最长啦,与你开黑时间最多的K个小伙伴啦,都会用到。

若是用普通的方式遍历所有元素,让元素个数很大,几亿或者几十亿,每次遍历出一个数都要比较K个数,则时间复杂度为N*K,K个数有序的话这个复杂度会少,但是排一个序也需要很多时间复杂度。所以这里可以利用堆最大K个数我们可以用这K个数组成一个最小堆(最小堆算的上是一个不完整的排序),堆顶则是这K个数中最小的数,新来的数只要比这K个数中最小的大即可入堆;再次调整堆,消耗的时间复杂度也不高(lg  K)。所以使用堆求TopK 时间复杂度只有 O(K*lgK)。

下面看一下代码↓

void TopK(int* arr, size_t k, size_t n)
{
	Heap<int,Less<int>> _a(arr, k); //建立最小堆 
	for (int i = k; i < n; i++)
	{
		if (_a.Top()< arr[i])          //比堆顶大进入堆
		{
			_a.Push(arr[i]);           
			_a.Pop();                    //原堆顶数据出堆 会自动将刚最后入堆的数据放到堆顶
		}
	}
	_a.Printf();
}

看一下测试:

void TestTopK()
{
	srand((int)time(NULL));
	int a[100] = { 0 };
	for (int i = 0; i < 100; i++)
	{
		a[i] = rand() % 200;
	}
	a[20] += 200;   //使其中10个数大于200 结果就是这大于200的10个数
	a[30] += 200;
	a[40] += 200;
	a[50] += 200;
	a[60] += 200;
	a[70] += 200;
	a[80] += 200;
	a[90] += 200;
	a[10] += 200;
	a[0] += 200;
	TopK(a, 10, 100);
}
堆排序和TopK问题

求出了这K个数;

堆排序和TopK问题

2.堆选择排序

简单选择排序的时间复杂度为O(n^2),每次遍历并选择最小或最大的一个数其实消耗了很多时间,利用堆来选择可以节约一些时间,最大最小堆的堆顶即为最大或最小的数,这对于选择便不用再遍历了,只需每次调整堆,调整堆的时间复杂堆只有lgN。

先建堆(比如需要升序就建最大堆),每次将堆顶a[0]数与a[n-1],再使n--;调整新堆。

void MaxHeap(int * a,int root,int n)
{
	int parent = root;
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			swap(a[child], a[parent]);
			parent = child; child = parent * 2 + 1;
		}
		else break;    //循环到孩子小于父亲便可停止
	}
}

void CreatHeap(int *a, int n)   //大堆
{	int root = (n - 2) / 2;
	for (; root >= 0; root--)
	{
		MaxHeap(a, root, n);
	}
}
void HeapSort(int *a,int n)
{
	CreatHeap(a, n);  //先最大建堆
	for (; n > 0; n--)
	{
		swap(a[0], a[n - 1]);
		MaxHeap(a, 0, n-1);  //调整新堆O(lgN)
	}
}



void TestHeapSort()  
{
	srand((int)time(NULL));
	int a[50] = { 0 };
	for (int i = 0; i < 50; i++)
	{
		a[i] = rand() % 100;
	}
	HeapSort(a, 50);  //堆排序
	for (int i = 0; i < 50; i++)
	{
		cout << a[i] << "  ";
	}
	cout << endl;
}
int main()
{
	TestHeapSort();
	system("pause");
	return 0;
}

排序完成

堆排序和TopK问题堆排序和TopK问题