堆的簡單應(yīng)用-創(chuàng)新互聯(lián)

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

站在用戶的角度思考問題，與客戶深入溝通，找到延川網(wǎng)站設(shè)計與延川網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗，讓設(shè)計與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個性化、用戶體驗好的作品，建站類型包括：成都網(wǎng)站設(shè)計、成都做網(wǎng)站、企業(yè)官網(wǎng)、英文網(wǎng)站、手機端網(wǎng)站、網(wǎng)站推廣、國際域名空間、網(wǎng)絡(luò)空間、企業(yè)郵箱。業(yè)務(wù)覆蓋延川地區(qū)。

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

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

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

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

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

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

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

#include<iostream>
#include<algorithm>

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

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

void AdjustDown1(int a[], int size, int parent)  //建一個小堆
{
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個數(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個大數(shù)
{
cout << TopK[n] << " ";
}
cout << endl;
}

測試代碼

#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;
}

測試結(jié)果

為了便于調(diào)試，我用的測試栗子比較簡單，大家可以嘗試一下更一般的栗子哦~

二.堆排序

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

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

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

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

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

//2.堆排序：建大堆，每次找到大的數(shù)據(jù)交換到數(shù)組末尾，將剩下的數(shù)據(jù)AdjustDown，再進行交換
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;

}

測試代碼：

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;
}

測試結(jié)果：

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

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機房獨有T級流量清洗系統(tǒng)配攻擊溯源，準確進行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務(wù)器買多久送多久。

當前文章：堆的簡單應(yīng)用-創(chuàng)新互聯(lián)
分享地址：http://bm7419.com/article2/gjooc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站制作、小程序開發(fā)、網(wǎng)站收錄、網(wǎng)站策劃、軟件開發(fā)、關(guān)鍵詞優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)