【數(shù)據(jù)結(jié)構(gòu)】堆的實(shí)現(xiàn)，堆排序以及TOP-K問(wèn)題

這篇具有很好參考價(jià)值的文章主要介紹了【數(shù)據(jù)結(jié)構(gòu)】堆的實(shí)現(xiàn)，堆排序以及TOP-K問(wèn)題。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

1.堆的概念及結(jié)構(gòu)

2.堆的實(shí)現(xiàn)

2.1初始化堆

2.2銷毀堆

2.3取堆頂元素

2.4返回堆的大小

2.5判斷是否為空

2.6打印堆

2.7插入元素

2.8堆的向上調(diào)整

2.9彈出元素

2.10堆的向下調(diào)整

3. 建堆時(shí)間復(fù)雜度

4.?堆的應(yīng)用

4.1 堆排序

4.2 TOP-K問(wèn)題

1.堆的概念及結(jié)構(gòu)

堆是一種數(shù)據(jù)結(jié)構(gòu)，它是由一組元素組成的，并按照一定的規(guī)則進(jìn)行排序和訪問(wèn)。堆可以看作是一個(gè)完全二叉樹(shù)，其中每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)（對(duì)于最大堆）或小于或等于其子節(jié)點(diǎn)（對(duì)于最小堆）。堆通常用來(lái)解決具有優(yōu)先級(jí)的問(wèn)題，例如找到最大或最小的元素。

【數(shù)據(jù)結(jié)構(gòu)】堆的實(shí)現(xiàn)，堆排序以及TOP-K問(wèn)題,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法

?堆的性質(zhì)：

堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
堆總是一棵完全二叉樹(shù)。

【數(shù)據(jù)結(jié)構(gòu)】堆的實(shí)現(xiàn)，堆排序以及TOP-K問(wèn)題,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法

2.堆的實(shí)現(xiàn)

這里寫(xiě)的是小根堆，大根堆可以在小根堆的基礎(chǔ)上稍作修改。下面是堆要實(shí)現(xiàn)的一些接口函數(shù)：

//初始化堆
void HeapInit(HP* php);
//銷毀堆
void HeapDestory(HP* php);
//插入元素
void HeapPush(HP* php, HPDataType x);
//堆向上調(diào)整算法
void AdjustUp(HP* php, int x);
//彈出堆頂元素
void HeapPop(HP* php);
//堆向下調(diào)整算法
void AdjustDwon(HPDataType* a, int size, int x);
//取堆頂元素
HPDataType HeapTop(HP* php);
//返回堆的大小
int HeapSize(HP* php);
//判斷是否為空
bool HeapEmpty(HP* php);
//打印堆
void HeapPrint(HP* php);

堆的定義：

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

對(duì)于一些簡(jiǎn)單的接口函數(shù)，我們就不詳細(xì)介紹了，在堆中，我們主要要學(xué)習(xí)的是向上調(diào)整算法和向下調(diào)整算法。這兩個(gè)函數(shù)分別在插入元素和彈出元素的時(shí)候會(huì)調(diào)用。

2.1初始化堆

void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}

2.2銷毀堆

void HeapDestory(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

2.3取堆頂元素

HPDataType HeapTop(HP* php)
{
	assert(php);
	return php->a[0];
}

2.4返回堆的大小

int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

2.5判斷是否為空

bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

2.6打印堆

void HeapPrint(HP* php)
{
	assert(php);
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

2.7插入元素

向堆中插入一個(gè)元素，我們可以將這個(gè)元素插入到堆的尾部，因?yàn)槎训膶?shí)際存儲(chǔ)結(jié)構(gòu)是一個(gè)數(shù)組，我們可以將元素放到數(shù)組末尾，但如果僅僅是插入到數(shù)組末尾的話，會(huì)將堆的結(jié)構(gòu)給破環(huán)，我們還需要調(diào)用一個(gè)向上調(diào)整的函數(shù)，來(lái)調(diào)整各個(gè)節(jié)點(diǎn)間的大小關(guān)系。

在插入之前，需要判斷堆的容量是否足夠，如果堆的容量已滿，需要擴(kuò)容，這里每次擴(kuò)容實(shí)在原來(lái)的基礎(chǔ)上擴(kuò)2倍。

void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}

	php->a[php->size] = x;
	AdjustUp(php->a, php->size);//向上調(diào)整
	php->size++;
}

2.8堆的向上調(diào)整

在上面插入元素的過(guò)程中，我們已經(jīng)使用了堆的向上調(diào)整算法，下面，我們來(lái)看看怎么實(shí)現(xiàn)這個(gè)向上調(diào)整算法吧：

【數(shù)據(jù)結(jié)構(gòu)】堆的實(shí)現(xiàn)，堆排序以及TOP-K問(wèn)題,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法

先插入一個(gè)10到數(shù)組的尾上，再進(jìn)行向上調(diào)整算法，直到滿足堆。

圖示過(guò)程：

【數(shù)據(jù)結(jié)構(gòu)】堆的實(shí)現(xiàn)，堆排序以及TOP-K問(wèn)題,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法

void AdjustUp(HPDataType* a, int x)
{
	int child = x;
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
		}
		else
		{
			break;
		}
		child = parent;
		parent = (child - 1) / 2;
	}
}

代碼分析：?

初始化變量child為節(jié)點(diǎn)x，parent為其父節(jié)點(diǎn)的索引，也即 (child - 1) / 2。
進(jìn)入一個(gè)循環(huán)，該循環(huán)會(huì)一直執(zhí)行直到節(jié)點(diǎn)x上浮到合適的位置或者到達(dá)堆頂。
在循環(huán)中，判斷節(jié)點(diǎn)x的值是否小于其父節(jié)點(diǎn)的值，若成立則交換兩者的值。
若節(jié)點(diǎn)x的值不小于父節(jié)點(diǎn)的值，則跳出循環(huán)，因?yàn)榇藭r(shí)堆的性質(zhì)已滿足。
更新child和parent的值，將child更新為parent，parent更新為其父節(jié)點(diǎn)的索引，也即 (child - 1) / 2。
重復(fù)步驟3-5，直到節(jié)點(diǎn)x的值大于或等于其父節(jié)點(diǎn)的值，或者到達(dá)堆頂。

2.9彈出元素

彈出元素就是將堆頂?shù)脑亟o刪除，但我們不能直接進(jìn)行刪除，這樣會(huì)將堆的結(jié)構(gòu)給破壞，正確的方法是先將堆頂?shù)脑睾妥詈蟮脑剡M(jìn)行交換，這樣保證的首元素的左子樹(shù)和右子樹(shù)依然是堆的形態(tài)，然后將size自減，最后調(diào)用一個(gè)堆的向下調(diào)整函數(shù)。

【數(shù)據(jù)結(jié)構(gòu)】堆的實(shí)現(xiàn)，堆排序以及TOP-K問(wèn)題,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法

void HeapPop(HP* php)
{
	assert(php);
	Swap(&php->a[0], &php->a[php->size-1]);
	php->size--;
	AdjustDwon(php->a, php->size, 0);
}

2.10堆的向下調(diào)整

堆的向下調(diào)整：每次將父節(jié)點(diǎn)和左右孩子的較小值進(jìn)行交換（小根堆），不斷地更新父節(jié)點(diǎn)的孩子節(jié)點(diǎn)的值。

【數(shù)據(jù)結(jié)構(gòu)】堆的實(shí)現(xiàn)，堆排序以及TOP-K問(wèn)題,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法

void AdjustDwon(HPDataType* a, int size, int x)
{
	int parent = x;
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && a[child + 1] < a[child])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
		}
		else
		{
			break;
		}
		parent = child;
		child = parent * 2 + 1;
	}
}

初始化變量parent為節(jié)點(diǎn)x，child為其左子節(jié)點(diǎn)的索引，也即 parent * 2 + 1。
進(jìn)入一個(gè)循環(huán)，該循環(huán)會(huì)一直執(zhí)行直到節(jié)點(diǎn)x下沉到合適的位置或者沒(méi)有子節(jié)點(diǎn)。
在循環(huán)中，首先判斷節(jié)點(diǎn)x是否有右子節(jié)點(diǎn)，并且右子節(jié)點(diǎn)的值小于左子節(jié)點(diǎn)的值，如果成立則將child更新為右子節(jié)點(diǎn)的索引。
接著判斷節(jié)點(diǎn)x的值是否大于其子節(jié)點(diǎn)的值，若成立則交換兩者的值。
若節(jié)點(diǎn)x的值不大于子節(jié)點(diǎn)的值，則跳出循環(huán)，因?yàn)榇藭r(shí)堆的性質(zhì)已滿足。
更新parent和child的值，將parent更新為child，child更新為parent的左子節(jié)點(diǎn)的索引，也即 parent * 2 + 1。
重復(fù)步驟3-6，直到節(jié)點(diǎn)x的值小于或等于其子節(jié)點(diǎn)的值，或者沒(méi)有子節(jié)點(diǎn)。

3. 建堆時(shí)間復(fù)雜度

因?yàn)槎咽峭耆鏄?shù)，而滿二叉樹(shù)也是完全二叉樹(shù)，此處為了簡(jiǎn)化使用滿二叉樹(shù)來(lái)證明(時(shí)間復(fù)雜度本來(lái)看的就是近似值，多幾個(gè)節(jié)點(diǎn)不影響最終結(jié)果)：

向下調(diào)整：

【數(shù)據(jù)結(jié)構(gòu)】堆的實(shí)現(xiàn)，堆排序以及TOP-K問(wèn)題,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法

因此：向下調(diào)整建堆的時(shí)間復(fù)雜度為O(N)。

向上調(diào)整：

【數(shù)據(jù)結(jié)構(gòu)】堆的實(shí)現(xiàn)，堆排序以及TOP-K問(wèn)題,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法

?因此：向上調(diào)整建堆的時(shí)間復(fù)雜度為N*logN;

4.?堆的應(yīng)用

4.1 堆排序

利用堆排序數(shù)組并打印出來(lái)：

void testHeapSort()
{
	HP hp;
	HeapInit(&hp);

	int a[] = { 1,4,7,5,10,2,8,9,3,6 };
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(&hp, a[i]);
	}
	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	//釋放內(nèi)存
	HeapDestory(&hp);
}
int main()
{
	testHeapSort();
	return 0;
}

輸出結(jié)果：

【數(shù)據(jù)結(jié)構(gòu)】堆的實(shí)現(xiàn)，堆排序以及TOP-K問(wèn)題,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法

?但是，使用這種方法是不是有點(diǎn)復(fù)雜了呢？我們要進(jìn)行堆排序，還得先寫(xiě)一個(gè)堆的數(shù)據(jù)結(jié)構(gòu)，當(dāng)然并不是這樣的，我們可以將代碼進(jìn)行修改，在原數(shù)組上進(jìn)行建堆：

思路：

對(duì)于在原數(shù)組上進(jìn)行建堆，我們可以使用兩種方式：

第一種是向上建堆，向上建堆的時(shí)間復(fù)雜度是 O(N*logN)，我們不推薦使用這種方法。

第二種是向下建堆，它的時(shí)間復(fù)雜度是O(N），它的效率比向上建堆要高。我們推薦使用向下建堆。

還有一個(gè)比較讓人難以理解的一點(diǎn)是：如果要進(jìn)行升序，我們要建大堆，如果要進(jìn)行降序，我們要建小堆。

【數(shù)據(jù)結(jié)構(gòu)】堆的實(shí)現(xiàn)，堆排序以及TOP-K問(wèn)題,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法

void swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
void HeapSort(int* a, int n)
{
	//從倒數(shù)第一個(gè)非葉子節(jié)點(diǎn)開(kāi)始調(diào)
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDwon(a, n, i);//向下調(diào)整建堆
	}
	int end = n - 1;
	while (end > 0)
	{
		swap(&a[0], &a[end]);
		AdjustDwon(a, end, 0);//向下調(diào)整[0,end]的元素
		--end;
	}
}
int main()
{
	int a[] = { 1,4,7,5,10,2,8,9,3,6 };
	int n = sizeof(a) / sizeof(a[0]);
	HeapSort(a,n);//堆排序
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

4.2 TOP-K問(wèn)題

TOP-K問(wèn)題：即求數(shù)據(jù)結(jié)合中前K個(gè)最大的元素或者最小的元素，一般情況下數(shù)據(jù)量都比較大。

比如：專業(yè)前10名、世界500強(qiáng)、富豪榜、游戲中前100的活躍玩家等。

對(duì)于Top-K問(wèn)題，能想到的最簡(jiǎn)單直接的方式就是排序，但是：如果數(shù)據(jù)量非常大，排序就不太可取了(可能數(shù)據(jù)都不能一下子全部加載到內(nèi)存中)。最佳的方式就是用堆來(lái)解決，基本思路如下：

1. 用數(shù)據(jù)集合中前K個(gè)元素來(lái)建堆

前k個(gè)最大的元素，則建小堆
前k個(gè)最小的元素，則建大堆

2. 用剩余的N-K個(gè)元素依次與堆頂元素來(lái)比較，不滿足則替換堆頂元素

將剩余N-K個(gè)元素依次與堆頂元素比完之后，堆中剩余的K個(gè)元素就是所求的前K個(gè)最小或者最大的元素。

實(shí)際應(yīng)用：在10000000個(gè)隨機(jī)數(shù)中找出前十個(gè)最大的數(shù)字

void AdjustDwon(int* a, int size, int x)
{
	int parent = x;
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && a[child + 1] < a[child])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			int tmp = a[child];
			a[child] = a[parent];
			a[parent] = tmp;
		}
		else
		{
			break;
		}
		parent = child;
		child = parent * 2 + 1;
	}
}

void PrintTopK(int* a, int n, int k)
{
	int* KMaxHeap = (int*)malloc(sizeof(int) * k);
	assert(KMaxHeap);
	for (int i = 0; i < k; i++)
	{
		KMaxHeap[i] = a[i];
	}
	//建小根堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDwon(KMaxHeap, k, i);
	}
	//依次比較a數(shù)組中剩余的元素
	for (int i = k; i < n; i++)
	{
		if (a[i] > KMaxHeap[0])
		{
			KMaxHeap[0] = a[i];
		}
		AdjustDwon(KMaxHeap, k, 0);
	}
	//打印
	for (int i = 0; i < k; i++)
	{
		printf("%d ", KMaxHeap[i]);
	}
}
void testTopK()
{
	srand(time(0));
	int n = 10000000;
	int* a = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++)
	{
		a[i] = rand() % n;//a[i]的范圍[1,n]
	}
	//手動(dòng)設(shè)定10個(gè)最大的數(shù)
	a[2] = n + 3;
	a[122] = n + 5;
	a[1233] = n + 1;
	a[12333] = n + 2;
	a[1322] = n + 8;
	a[2312] = n + 6;
	a[54612] = n + 7;
	a[546612] = n + 9;
	a[5612] = n + 10;
	a[46612] = n + 4;
	PrintTopK(a, n, 10);
}
int main()
{
	testTopK();
	return 0;
}

【數(shù)據(jù)結(jié)構(gòu)】堆的實(shí)現(xiàn)，堆排序以及TOP-K問(wèn)題,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-650380.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】堆的實(shí)現(xiàn)，堆排序以及TOP-K問(wèn)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！