堆的簡(jiǎn)單應(yīng)用

一、大數(shù)據(jù)的處理

給出N個(gè)數(shù)據(jù)，要求找到并輸出這N個(gè)數(shù)里面最大的K個(gè)數(shù)

思路：利用堆，先建一個(gè)開辟一個(gè)大小為K的數(shù)組，從N個(gè)數(shù)據(jù)里拿出K個(gè)數(shù)據(jù)放到堆里面，然后再通過(guò)向

下調(diào)整法把堆調(diào)整為最小堆，此時(shí)數(shù)組的第一個(gè)元素就是堆里面最小的元素，然后在剩下的N-K個(gè)

數(shù)據(jù)中依次和堆里面最小的數(shù)據(jù)進(jìn)行比較，若比第一個(gè)元素大，則交換兩個(gè)的值，每交換一次就向下調(diào)

整一次，保證在最上面的是最小元素，這樣一直到所有數(shù)據(jù)比較完畢，此時(shí)堆里面存儲(chǔ)的k個(gè)數(shù)據(jù)就是最

大的k個(gè)數(shù)據(jù)。

下面是實(shí)現(xiàn)代碼

#include<iostream>
#include<algorithm>


using namespace std;
//1.在N個(gè)數(shù)據(jù)當(dāng)中找出最大的K個(gè)數(shù)

const int N = 10000;
const int K = 100;

void AdjustDown1(int a[], int size, int parent)  //建一個(gè)小堆
{
	int child = parent * 2 + 1;

	while (child < K)
	{
		if ((child + 1 < K) && (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 GetTopK(int a[],int TopK[])
{
	assert(K < N);
	int i = 0;
	int j = 0;
	int m = 0;
	int n = 0;

	for (i = 0; i < K; i++)
	{
		TopK[i] = a[i];     //取出a中的前k個(gè)數(shù)字放到topk[]里面
	}

	//建堆

	for (j = (K - 2) / 2; j >0; --j)
	{
		AdjustDown1(TopK,K,j);
	}

	for (int m = 0; m < N; ++m)
	{
		if (a[m]>TopK[0])
		{
			TopK[0] = a[m];
			AdjustDown1(TopK, K, 0);
		}
	}


	for (int n = 0; n < K; ++n)  //一次輸出K個(gè)最大數(shù)
	{
		cout << TopK[n] << " ";
	}
	cout << endl;
}

測(cè)試代碼

#include"BIgData.h"



void TestTopK()
{
	int a[N];
	int TopK[K];

	for (int i = 0; i < N; ++i)
	{
		a[i] = i;
	}

	GetTopK(a, TopK);


}
int main()
{
	TestTopK();
	system("pause");
	return 0;
}

測(cè)試結(jié)果

為了便于調(diào)試，我用的測(cè)試?yán)踝颖容^簡(jiǎn)單，大家可以嘗試一下更一般的栗子哦~

二.堆排序

思路：利用堆，建一個(gè)最大堆，每次選出最大的數(shù)據(jù)與數(shù)組末尾的數(shù)據(jù)進(jìn)行交換，然后再進(jìn)行一次向下

調(diào)整變成最大堆，始終保持最上面的為當(dāng)前最大的數(shù)據(jù)，假設(shè)數(shù)組由n個(gè)數(shù)據(jù)，則下次就讓第一個(gè)數(shù)據(jù)與

數(shù)組的第n-1個(gè)數(shù)據(jù)作比較，因?yàn)榈趎個(gè)數(shù)據(jù)已經(jīng)是最大的了，每交換一次要調(diào)整一次，這樣當(dāng)比較到第

一個(gè)數(shù)據(jù)時(shí)這個(gè)堆就是一個(gè)有序的了。

實(shí)現(xiàn)代碼如下：

//2.堆排序：建大堆，每次找到最大的數(shù)據(jù)交換到數(shù)組末尾，將剩下的數(shù)據(jù)AdjustDown，再進(jìn)行交換
void AdjustDown2(int a[],int size,size_t parent)
{
	int child = parent * 2 + 1;

	while (child<size)
	{
		if ((child + 1 < size)&&a[child] < a[child + 1])
		{
			++child;
		}

		if (a[child] > a[parent])   
		{
			swap(a[child], a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void Heap_Sort(int a[], size_t n)
{
	for (int i = (n - 2) / 2; i >= 0; i--)  //注意邊界條件
	{
		AdjustDown2(a, n, i);
	}

	for (int i = 0; i < n; ++i)
	{
		swap(a[0], a[n - 1-i]);

		AdjustDown2(a, n - 1 - i, 0);
	}

	for (int i = 0; i < n; ++i)
	{
		cout << a[i] << " ";
	}
	cout << endl;

}

測(cè)試代碼：

void TestHeap_Sort()
{
	int a[] = { 10, 12, 9, 15, 13, 17, 16, 18, 20,14 };
	Heap_Sort(a, 10);
}


int main()
{
	TestHeap_Sort();
	system("pause");
	return 0;
}

測(cè)試結(jié)果：

以上便是堆的兩種簡(jiǎn)單應(yīng)用啦，不足之處還請(qǐng)大家指出哦~