【數(shù)據(jù)結(jié)構(gòu)】建堆的方式、堆排序以及TopK問題-創(chuàng)新互聯(lián)

建堆的方式、堆排序以及TopK問題

• 1、建堆的兩種方式
• • 1.1 向上調(diào)整建堆
  • 1.2 向下調(diào)整建堆
• 2、堆排序
• 3、TopK問題
• 4、建堆、堆排序、TopK問題全部代碼

超過10多年行業(yè)經(jīng)驗，技術(shù)領(lǐng)先，服務(wù)至上的經(jīng)營模式，全靠網(wǎng)絡(luò)和口碑獲得客戶，為自己降低成本，也就是為客戶降低成本。到目前業(yè)務(wù)范圍包括了：成都網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計，成都網(wǎng)站推廣，成都網(wǎng)站優(yōu)化，整體網(wǎng)絡(luò)托管，微信平臺小程序開發(fā)，微信開發(fā)，重慶APP開發(fā)公司，同時也可以讓客戶的網(wǎng)站和網(wǎng)絡(luò)營銷和我們一樣獲得訂單和生意！1、建堆的兩種方式

我們知道，堆是二叉樹的一種，二叉樹的建立是借助結(jié)構(gòu)體與數(shù)組完成的（通過在結(jié)構(gòu)體中創(chuàng)建動態(tài)開辟的數(shù)組變量儲存堆中的元素）。
除了借助結(jié)構(gòu)體外，有沒有其他方式，直接建堆。

1.1 向上調(diào)整建堆

//交換函數(shù)
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//向上調(diào)整函數(shù)
typedef int HPDataType;
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;  //找到堆最后一個數(shù)的父親的下標
	while (child >0)   //孩子的下標等于0時，說明堆從最后一個數(shù)一路向上比較，已經(jīng)到達堆頂了
	{//小根堆，任意孩子的值要大于父節(jié)點的值，不是的話則要向上調(diào)整
		if (a[child]< a[parent])   //改為>，這個堆結(jié)構(gòu)就成為大堆了
		{	Swap(&a[child], &a[parent]);

			//修正父親與孩子的下標，通過循環(huán)不斷比較，直到成為堆的形狀
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{	break;
		}
	}
}

int main()
{int a[] = {15,1,19,25,8,34,65,4,27,7 };

   //建堆---向上調(diào)整建堆---O(N*LogN)
	int n = sizeof(a) / sizeof(a[0]);
	for (int i = 1; i< n; ++i)
	{AdjustUp(a, i);
	}

	for (int i = 0; i< n; ++i)
	{printf("%d ", a[i]);
	}
	printf("\n");

	return 0;
}

打印結(jié)果


1.打印結(jié)果將一串無序的數(shù)組建立成為小堆。只要將向上調(diào)整中的if語句中的小于符號改成大于符號，建成的就是大堆。
2.向上調(diào)整建堆從第二個節(jié)點開始向上調(diào)整（即數(shù)組下標為1的節(jié)點），因為第一個節(jié)點是根節(jié)點，根節(jié)點沒有父節(jié)點，再往上就沒有節(jié)點了。第二個節(jié)點向上調(diào)整完畢，接著第三個節(jié)點，然后第四個節(jié)點、第五個節(jié)點，直到最后一個節(jié)點向上調(diào)整完畢。
3.向上調(diào)整建堆的時間復(fù)雜度

可以看到，在一棵樹中，越往下的節(jié)點，向上調(diào)整的次數(shù)越多，并且越往下的層級包含的節(jié)點數(shù)越多，所以越往下的層級每個節(jié)點向上調(diào)整的次數(shù)加起來是越大的。由上述式子計算，最后一層所有節(jié)點總共需要向上調(diào)整的次數(shù)大為(N+1) * ((log(N+1)-1)/2)，即最后一層需要向上調(diào)整的時間復(fù)雜度為O(N * log(N))。因為最后一層的時間復(fù)雜度已經(jīng)是大的，前面所有層級加起來的時間復(fù)雜度也不會超過，所以向上調(diào)整總的時間復(fù)雜度為O(N * log(N))。

1.2 向下調(diào)整建堆

//交換函數(shù)
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//向下調(diào)整函數(shù)
typedef int HPDataType;
void AdjustDown(HPDataType* a, int n, int parent)
{int minChild = parent * 2 + 1; //先默認左邊的孩子是整個小根堆中次小的孩子
	while (minChild< n)
	{//與右孩子比較一下，找出小的那個孩子的下標
		if (minChild + 1< n && a[minChild + 1]< a[minChild])
		{	minChild++;
		}
		//找到次小的孩子后將其與父節(jié)點比較
		if (a[minChild]< a[parent])
		{	Swap(&a[minChild], &a[parent]);
			//修正父親與孩子的下標，通過循環(huán)不斷比較，直到成為堆的形狀
			parent = minChild;
			minChild = parent * 2 + 1;
		}
		else
		{	break;
		}
	}

}

int main()
{int a[] = {15,1,19,25,8,34,65,4,27,7 };

	//建堆---向下調(diào)整建堆---O(N)
	//向下調(diào)整建堆要從倒數(shù)的第一個非葉子節(jié)點開始向下調(diào)整，一直調(diào)整到根節(jié)點位置
	int n = sizeof(a) / sizeof(a[0]);
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{AdjustDown(a, n, i);
	}

	for (int i = 0; i< n; ++i)
	{printf("%d ", a[i]);
	}
	printf("\n");

	return 0;
}

打印結(jié)果


1.打印結(jié)果將一串無序的數(shù)組建立成為小堆。只要將向下調(diào)整中的兩個if語句中的小于符號改成大于符號，建成的就是大堆。
2.向下調(diào)整建堆從倒數(shù)的第一個非葉子節(jié)點開始向下調(diào)整，因為葉子節(jié)點往下沒有子節(jié)點了，不用在往下調(diào)整了。倒數(shù)第一個非葉子節(jié)點調(diào)整完畢，接著倒數(shù)第二個非葉子節(jié)點向下調(diào)整，然后倒數(shù)第三個非葉子節(jié)點向下調(diào)整，一直到根節(jié)點位置向下調(diào)整。(n-1-1)/2 是在找倒數(shù)第一個非葉子節(jié)點。
3.向下調(diào)整時間復(fù)雜度

由上述式子算出，向下調(diào)整建堆最壞需要向下調(diào)整N-log(N+1)次，因此向下調(diào)整建堆的時間復(fù)雜度為O(N)。

總結(jié)： 經(jīng)由上述可知，向下調(diào)整建堆的時間復(fù)雜度與向上調(diào)整建堆的時間復(fù)雜度相比，向下調(diào)整建堆所需時間更少，因此在沒有結(jié)構(gòu)體構(gòu)造堆的情況下，選擇向下調(diào)整直接建堆。

2、堆排序

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//向下調(diào)整函數(shù)
typedef int HPDataType;
void AdjustDown(HPDataType* a, int n, int parent)
{int minChild = parent * 2 + 1; //先默認左邊的孩子是整個小根堆中次小的孩子
	while (minChild< n)
	{//與右孩子比較一下，找出小的那個孩子的下標
		if (minChild + 1< n && a[minChild + 1]< a[minChild])
		{	minChild++;
		}
		//找到次小的孩子后將其與父節(jié)點比較
		if (a[minChild]< a[parent])
		{	Swap(&a[minChild], &a[parent]);
			//修正父親與孩子的下標，通過循環(huán)不斷比較，直到成為堆的形狀
			parent = minChild;
			minChild = parent * 2 + 1;
		}
		else
		{	break;
		}
	}

}

//堆排序函數(shù)
//大思路：選擇排序，依次選數(shù)，從后往前排
//升序---先建大堆，建堆完畢后，此時大的數(shù)在第一位，把第一個和最后一個的位置進行交換，
// 交換完畢后，把最后一個不看做堆里面的，進行向下調(diào)整，選出次大的。后續(xù)依次類似處理。

//降序---先建小堆，建堆完畢后，此時最小的數(shù)在第一位，把第一個和最后一個的位置進行交換，
//交換完畢后，把最后一個不看做堆里面的，進行向下調(diào)整，選出次小的。后續(xù)依次類似處理。
void HeapSort(int* a, int n)
{//建堆---向下調(diào)整建堆---O(N)
	//向下調(diào)整建堆要從倒數(shù)的第一個非葉子節(jié)點開始向下調(diào)整，一直調(diào)整到根節(jié)點位置
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{AdjustDown(a, n, i);
	}

	//選數(shù)
	int i = 1;
	while (i< n)
	{Swap(&a[0], &a[n - i]);  //交換第一個數(shù)跟最后一個數(shù)
		AdjustDown(a, n - i, 0);
		++i;
	}
}

int main()
{int a[] = {15,1,19,25,8,34,65,4,27,7 };
	HeapSort(a, sizeof(a) / sizeof(int));

	for (size_t i = 0; i< sizeof(a) / sizeof(int); ++i)
	{printf("%d ", a[i]);
	}
	printf("\n");

	return 0;
}

打印結(jié)果


1.打印結(jié)果將一串無序的數(shù)組建立成為降序的小堆。
2.堆排序的思路：
大思路：選擇排序，依次選數(shù)，從后往前排

2.1升序—先建大堆，建堆完畢后，此時大的數(shù)在第一位，把第一個和最后一個的位置進行交換，
交換完畢后，把最后一個不看做堆里面的，進行向下調(diào)整，選出次大的。后續(xù)依次類似處理。
2.2降序—先建小堆，建堆完畢后，此時最小的數(shù)在第一位，把第一個和最后一個的位置進行交換，
交換完畢后，把最后一個不看做堆里面的，進行向下調(diào)整，選出次小的。后續(xù)依次類似處理。

3、TopK問題

TopK問題就是在N個數(shù)中選出大的前K個數(shù)或者最小的前K個數(shù)來。
這個問題有兩種思路，例如選出大的前K個數(shù)，
思路1，建大堆（用向下調(diào)整建堆的方式），將根節(jié)點與尾節(jié)點進行交換(此時根節(jié)點上的數(shù)為大的數(shù))，交換后不將尾節(jié)點算入堆中，剩余的N-1個數(shù)重新建堆，重復(fù)K次，這樣大的前K個數(shù)就被篩選出來了。
時間復(fù)雜度為O(N+(logN)* K)。
思路2，建小堆（用向下調(diào)整建堆的方式），用N個數(shù)中的前K個數(shù)建一個K個數(shù)的小堆，剩余的N-K個數(shù)一一與堆頂比較，只要比堆頂大就入隊，入堆后再重新向下調(diào)整建成小堆。當(dāng)比較完畢后，小堆中的K個數(shù)就是在N個數(shù)中選出的大前K個數(shù)。時間復(fù)雜度為K+(log(k)) *(N-K)。

分析思路1與思路2的優(yōu)劣： 當(dāng)N很大，K很小的時候，選第二種方式，例如當(dāng)N=100億，K=100，100億個整數(shù)有400億個字節(jié)(Byte)，一個G有1024 *1024 *1024(Byte)=1073741824個字節(jié)(Byte)≈1000000000=10億字節(jié)(Byte)，所以當(dāng)N=100億時，要占用的空間為400÷10=40個G，所占內(nèi)存過大，所以一般選用思路2的方式，即：
在N個數(shù)中選出大的前K個數(shù)-----建小堆
在N個數(shù)中選出最小的前K個數(shù)-----建大堆

在文件中先寫入10個數(shù)，選取這十個數(shù)中大的前3個數(shù)，代碼如下：

void PrintTopK(const char* filename, int k)
{assert(filename);

	FILE* fout = fopen(filename, "r");   //r--->在Test,c這個源文件路徑下打開一個本身已經(jīng)存在的叫Data.txt的文件，將這個文件的地址賦值給文件指針
	if (fout == NULL)
	{perror("fopen fail");
		return;
	}

	int* minHeap = (int*)malloc(sizeof(int) * k);
	if (minHeap == NULL)
	{perror("malloc fail");
		return;
	}
	//如何讀取前k個數(shù)
	for (int i = 0; i< k; ++i)
	{fscanf(fout, "%d", &minHeap[i]);
	}

	//建堆,將讀取的前k個數(shù)建成小堆，向下調(diào)整建堆
	for (int j = (k - 1 - 1) / 2; j >= 0; --j)
	{AdjustDown(minHeap, k, j);
	}
	//繼續(xù)讀取N-k個數(shù)
	int val = 0;
	while (fscanf(fout, "%d", &val) != EOF)
	{if (val >minHeap[0])
		{	minHeap[0] = val;
			AdjustDown(minHeap, k, 0);
		}
	}

	for (int i = 0; i< k; ++i)
	{printf("%d ", minHeap[i]);
	}

	free(minHeap);
	fclose(fout);
}

//top k問題  N個數(shù)，找出這N個數(shù)中大的前k個數(shù)
int main()
{const char* filename = "Data.txt";
	int k = 3;
	PrintTopK(filename, k);

	return 0;
}

1.Fopen：打開文件，F(xiàn)close：關(guān)閉文件，fscanf：從文件中讀取數(shù)據(jù)(即從文件中輸入數(shù)據(jù)到屏幕上，sanf是從鍵盤上輸入數(shù)據(jù)到屏幕上)
2.fscanf(fout, “%d”, &val)；從fout中以 %d的類型讀取數(shù)據(jù)到變量val中。
3.已經(jīng)存在的data.txt文件中10個數(shù)為 0 3 11 2 4 1 100 2 200 5。文件放在與Tsetc同一級的目錄下。
4.打印結(jié)果為

前3個大的數(shù)被選出來了，被選出來的數(shù)并不是有序的，這里有序只不過是巧合而已。
5. 向下調(diào)整函數(shù)的實現(xiàn)被寫在了Heap.c中，在第一節(jié)中，向下調(diào)整的實現(xiàn)已經(jīng)寫過了，這里就不搬上來了。

在文件中隨機生成10000個數(shù)（1~10000中的任意數(shù)，包含了重復(fù)的數(shù)），選出其中大的前10個數(shù)來，如何實現(xiàn)？
這個只要多寫一個在文件中隨機生成數(shù)的函數(shù)就行，代碼如下。

//在文件中隨機數(shù)的生成
void CreateDataFile(const char* filename, int k)
{assert(filename);
	FILE* fin = fopen(filename, "w"); //w--->在test.c這個源文件路徑下創(chuàng)建一個test.txt的文件，如果這個文件已經(jīng)存在，則將
	                                  //這個文件里的內(nèi)容全部銷毀，相當(dāng)于重新創(chuàng)建了這個文件。
	if (fin == NULL)
	{perror("fin fail");
		return;
	}
	srand(time(0));
	for (int i = 0; i< k; ++i)
	{fprintf(fin, "%d\n", rand()%10000);
	}

	fclose(fin);
}

void PrintTopK(const char* filename, int k)
{assert(filename);

	FILE* fout = fopen(filename, "r");  //r--->在Test,c這個源文件路徑下打開一個本身已經(jīng)存在的叫Data.txt的文件，將這個文件的地址賦值給文件指針
	if (fout == NULL)
	{perror("fopen fail");
		return;
	}

	int* minHeap = (int*)malloc(sizeof(int) * k);
	if (minHeap == NULL)
	{perror("malloc fail");
		return;
	}
	//如何讀取前k個數(shù)
	for (int i = 0; i< k; ++i)
	{fscanf(fout, "%d", &minHeap[i]);
	}

	//建堆,將讀取的前k個數(shù)建成小堆
	for (int j = (k - 1 - 1) / 2; j >= 0; --j)
	{AdjustDown(minHeap, k, j);
	}
	//繼續(xù)讀取N-k個數(shù)
	int val = 0;
	while (fscanf(fout, "%d", &val) != EOF)
	{if (val >minHeap[0])
		{	minHeap[0] = val;
			AdjustDown(minHeap, k, 0);
		}
	}

	for (int i = 0; i< k; ++i)
	{printf("%d ", minHeap[i]);
	}

	free(minHeap);
	fclose(fout);
}

int main()
{const char* filename = "Data.txt";
	int N = 10000;
	int k = 10;

	CreateDataFile(filename, N);
	PrintTopK(filename, k);
	
	return 0;
}

1.void CreateDataFile(const char* filename, int k);---->在文件中生成隨機數(shù)
2.如何生成隨機數(shù)?
rand()函數(shù)能夠生成不同的偽隨機數(shù)，如果要生成0到10000之間的偽隨機數(shù)，則rand()%10000，這樣生成的偽隨機數(shù)就是0~9999。不過如果直接使用rand(),每次生成的偽隨機數(shù)都是一樣的，比如第一次生成的是1 4 99 3……，下一次運行程序生成的還是1 4 99 3……，因此每次使用rand()前都要先使用srand()初始化一遍，如果srand()中的參數(shù)是固定的話，每次初始化的值也是一樣的，即每次調(diào)用rand()生成的偽隨機數(shù)還是一樣的，因此需要srand()中的參數(shù)不是固定的，這樣每次調(diào)用rand()時，生成的偽隨機數(shù)才能不是一樣的。剛好，電腦上流動的時間是在變化的，運用時間戳函數(shù)time(),能夠?qū)⒚繒r每刻的時間轉(zhuǎn)換為time_t類型的值，不同時間調(diào)用time()，生成的值都不同，因此這個值作為srand()的參數(shù)，隨著srand()中的參數(shù)變化，每次初始化的值也不一樣了，rand()生成的偽隨機數(shù)也不一樣了。
time()的頭文件是time.h
3.fprintf(fin, “%d\n”, rand()%10000)；—>將參數(shù)3以%d的類型寫進文件指針fin指向的文件。
打印結(jié)果


上述文本文件是在文件中隨機生成的1000個數(shù)中截取的一部份，運行結(jié)果是這一萬個數(shù)種大的前十個數(shù)。因為隨機生成的數(shù)有重復(fù)的，因此大的前十個數(shù)也有重復(fù)的。
4.如何驗證這個程序的正確性？
答：首相將隨機生成數(shù)函數(shù)屏蔽，然后在之前已經(jīng)生成的隨機數(shù)種中手動加入十個比這一萬個數(shù)都大的數(shù)，如果程序運行后，能把這手動添加的數(shù)全部選出來，說明程序無誤。現(xiàn)在加入 10001 10002 10003……10010。

int main()
{const char* filename = "Data.txt";
	int N = 10000;
	int k = 10;

	//CreateDataFile(filename, N);
	PrintTopK(filename, k);

	return 0;
}

打印結(jié)果

手動加入的十個大的數(shù)全部被挑選出來，說明程序無誤。

4、建堆、堆排序、TopK問題全部代碼

Heap.h部分：寫函數(shù)的聲明，函數(shù)的頭文件。

#pragma once

#include#include 
#include#include#include//堆是完全二叉樹
//堆的二叉樹用數(shù)組表示，在數(shù)組的順序從上至下，從左至右
//小根堆，任何節(jié)點的值小于等于孩子的值
//大根堆，任何節(jié)點的值大于等于孩子的值
//數(shù)組下標計算父子關(guān)系的公式
//leftchild = parent*2 + 1   左孩子的數(shù)組下標都是奇數(shù)
//rightchild = parent*2 + 2  右孩子的數(shù)組下標都是偶數(shù)
//parent = (child - 1)/2


typedef int HPDataType;

//向上調(diào)整
void AdjustUp(HPDataType* a, int child);

//向下調(diào)整
void AdjustDown(HPDataType* a, int n, int parent);

//交換函數(shù)
void Swap(HPDataType* p1, HPDataType* p2);

//在文件中隨機數(shù)的生成
void CreateDataFile(const char* filename, int k);

//TopK函數(shù)
void PrintTopK(const char* filename, int k);

Heap.c部分：各自定義函數(shù)的實現(xiàn)

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}


//向上調(diào)整函數(shù)
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;  //找到堆最后一個數(shù)的父親的下標
	while (child >0)   //孩子的下標等于0時，說明堆從最后一個數(shù)一路向上比較，已經(jīng)到達堆頂了
	{//小根堆，任意孩子的值要大于父節(jié)點的值，不是的話則要向上調(diào)整
		if (a[child]< a[parent])   //改為>，這個堆結(jié)構(gòu)就成為大堆了
		{	Swap(&a[child], &a[parent]);

			//修正父親與孩子的下標，通過循環(huán)不斷比較，直到成為堆的形狀
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{	break;
		}
	}
}


//向下調(diào)整函數(shù)
void AdjustDown(HPDataType* a, int n, int parent)
{int minChild = parent * 2 + 1; //先默認左邊的孩子是整個小根堆中次小的孩子
	while (minChild< n)
	{//與右孩子比較一下，找出小的那個孩子的下標
		if (minChild + 1< n && a[minChild + 1]< a[minChild])
		{	minChild++;
		}
		//找到次小的孩子后將其與父節(jié)點比較
		if (a[minChild]< a[parent])
		{	Swap(&a[minChild], &a[parent]);
			//修正父親與孩子的下標，通過循環(huán)不斷比較，直到成為堆的形狀
			parent = minChild;
			minChild = parent * 2 + 1;
		}
		else
		{	break;
		}
	}

}


//在文件中隨機數(shù)的生成
void CreateDataFile(const char* filename, int k)
{assert(filename);
	FILE* fin = fopen(filename, "w"); //w--->在test.c這個源文件路徑下創(chuàng)建一個test.txt的文件，如果這個文件已經(jīng)存在，則將
	//這個文件里的內(nèi)容全部銷毀，相當(dāng)于重新創(chuàng)建了這個文件。
	if (fin == NULL)
	{perror("fin fail");
		return;
	}
	srand(time(0));
	for (int i = 0; i< k; ++i)
	{fprintf(fin, "%d\n", rand() % 10000);
	}

	fclose(fin);
}


//TopK函數(shù)
void PrintTopK(const char* filename, int k)
{assert(filename);

	FILE* fout = fopen(filename, "r");  //r--->在Test,c這個源文件路徑下打開一個本身已經(jīng)存在的叫Data.txt的文件，將這個文件的地址賦值給文件指針
	if (fout == NULL)
	{perror("fopen fail");
		return;
	}

	int* minHeap = (int*)malloc(sizeof(int) * k);
	if (minHeap == NULL)
	{perror("malloc fail");
		return;
	}
	//如何讀取前k個數(shù)
	for (int i = 0; i< k; ++i)
	{fscanf(fout, "%d", &minHeap[i]);
	}

	//建堆,將讀取的前k個數(shù)建成小堆
	for (int j = (k - 1 - 1) / 2; j >= 0; --j)
	{AdjustDown(minHeap, k, j);
	}
	//繼續(xù)讀取N-k個數(shù)
	int val = 0;
	while (fscanf(fout, "%d", &val) != EOF)
	{if (val >minHeap[0])
		{	minHeap[0] = val;
			AdjustDown(minHeap, k, 0);
		}
	}

	for (int i = 0; i< k; ++i)
	{printf("%d ", minHeap[i]);
	}

	free(minHeap);
	fclose(fout);
}

Test.c部分：主函數(shù)放在這，在主函數(shù)中調(diào)用各自定義函數(shù)。在實現(xiàn)各函數(shù)時，可以用來測試各函數(shù)的功能。

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"

//向上調(diào)整建堆
int main()
{int a[] = {15,1,19,25,8,34,65,4,27,7 };

    //建堆---向上調(diào)整建堆---O(N*LogN)
	int n = sizeof(a) / sizeof(a[0]);
	for (int i = 1; i< n; ++i)
	{AdjustUp(a, i);
	}

	for (int i = 0; i< n; ++i)
	{printf("%d ", a[i]);
	}
	printf("\n");

	return 0;
}

//向下調(diào)整建堆
int main()
{int a[] = {15,1,19,25,8,34,65,4,27,7 };

	//建堆---向下調(diào)整建堆---O(N)
	//向下調(diào)整建堆要從倒數(shù)的第一個非葉子節(jié)點開始向下調(diào)整，一直調(diào)整到根節(jié)點位置
	int n = sizeof(a) / sizeof(a[0]);
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{AdjustDown(a, n, i);
	}

	for (int i = 0; i< n; ++i)
	{printf("%d ", a[i]);
	}
	printf("\n");

	return 0;
}


//堆排序函數(shù)
//大思路：選擇排序，依次選數(shù)，從后往前排
//升序---先建大堆，建堆完畢后，此時大的數(shù)在第一位，把第一個和最后一個的位置進行交換，
// 交換完畢后，把最后一個不看做堆里面的，進行向下調(diào)整，選出次大的。后續(xù)依次類似處理。

//降序---先建小堆，建堆完畢后，此時最小的數(shù)在第一位，把第一個和最后一個的位置進行交換，
//交換完畢后，把最后一個不看做堆里面的，進行向下調(diào)整，選出次小的。后續(xù)依次類似處理。
void HeapSort(int* a, int n)
{//建堆---向下調(diào)整建堆---O(N)
	//向下調(diào)整建堆要從倒數(shù)的第一個非葉子節(jié)點開始向下調(diào)整，一直調(diào)整到根節(jié)點位置
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{AdjustDown(a, n, i);
	}

	//選數(shù)
	int i = 1;
	while (i< n)
	{Swap(&a[0], &a[n - i]);  //交換第一個數(shù)跟最后一個數(shù)
		AdjustDown(a, n - i, 0);
		++i;
	}
}
int main()
{int a[] = {15,1,19,25,8,34,65,4,27,7 };
	HeapSort(a, sizeof(a) / sizeof(int));

	for (size_t i = 0; i< sizeof(a) / sizeof(int); ++i)
	{printf("%d ", a[i]);
	}
	printf("\n");

	return 0;
}




//top k問題  N個數(shù)，找出這N個數(shù)中大的前k個數(shù)
int main()
{const char* filename = "Data.txt";
	int k = 3;
	PrintTopK(filename, k);

	return 0;
}

//在文件中隨機生成10000個數(shù)，然后找出其中前十個大數(shù)。
int main()
{const char* filename = "Data.txt";
	int N = 10000;
	int k = 10;

	CreateDataFile(filename, N);
	PrintTopK(filename, k);

	return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前文章：【數(shù)據(jù)結(jié)構(gòu)】建堆的方式、堆排序以及TopK問題-創(chuàng)新互聯(lián)
網(wǎng)頁地址：http://muchs.cn/article36/djjcpg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站收錄、關(guān)鍵詞優(yōu)化、網(wǎng)頁設(shè)計公司、用戶體驗、服務(wù)器托管、全網(wǎng)營銷推廣

廣告

聲明：本網(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)