借助堆，查找最小的k个数代码,C代码库,德仔网

代码语言

代码分类

【C】借助堆，查找最小的k个数

作者:Dezai.CN / 发布于2013/7/30/ 701


	//借助堆，查找最小的k个数
	#include <iostream>
	#include <assert.h>
	using namespace std;
	void maxheap(int heap[], int i, int len);
	/*-------------------
	build-min-heap(a)
	1 heap-size[a] &larr; length[a]
	2 for i &larr; |_length[a]/2_| downto 1
	3 do max-heapify(a, i)
	*/
	// 建立大根堆
	void buildheap(int heap[], int len)
	{
	if (heap == null)
	return;

	int index = len / 2;
	for (int i = index; i >= 1; i--)
	maxheap(heap, i, len);
	}
	/*----------------------------
	parent(i)
	return |_i/2_|
	left(i)
	return 2i
	right(i)
	return 2i + 1
	min-heapify(a, i)
	1 l &larr; left(i)
	2 r &larr; right(i)
	3 if l &le; heap-size[a] and a[l] < a[i]
	4 then smallest &larr; l
	5 else smallest &larr; i
	6 if r &le; heap-size[a] and a[r] < a[smallest]
	7 then smallest &larr; r
	8 if smallest &ne; i
	9 then exchange a[i] <-> a[smallest]
	10 min-heapify(a, smallest)
	*/
	//调整大根堆
	void maxheap(int heap[], int i, int len)
	{
	int largeindex = -1;
	int left = i * 2;
	int right = i * 2 + 1;

	if (left <= len && heap[left] > heap[i])
	largeindex = left;
	else
	largeindex = i;

	if (right <= len && heap[right] > heap[largeindex])
	largeindex = right;

	if (largeindex != i)
	{
	swap(heap[i], heap[largeindex]);
	maxheap(heap, largeindex, len);
	}
	}
	int main()
	{
	// 定义数组存储堆元素
	int k;
	cin >> k;
	int *heap = new int [k+1]; //注，只需申请存储k个数的数组
	file *fp = fopen("data.txt", "r"); //从文件导入海量数据（便于测试，只截取了9m的数据大小）
	assert(fp);

	for (int i = 1; i <= k; i++)
	fscanf(fp, "%d ", &heap[i]);

	buildheap(heap, k); //建堆

	int newdata;
	while (fscanf(fp, "%d", &newdata) != eof)
	{
	if (newdata < heap[1]) //如果遇到比堆顶元素kmax更小的，则更新堆
	{
	heap[1] = newdata;
	maxheap(heap, 1, k); //调整堆
	}

	}

	for (int j = 1; j <= k; j++)
	cout << heap[j] << " ";
	cout << endl;

	fclose(fp);
	return 0;
	}

评论列表

本站所提供的代码，版权归原作者所有，若有侵犯作者版权，请与我们联系，我们将立即删除或修改。谢谢!
本站所有代码发布及提供者。

试试其它关键字

　查找最小的k　

同语言下

可能有用的

Dezai.CN贡献的其它代码(4037)