堆數(shù)據(jù)結(jié)構(gòu)是一種數(shù)組對象，它可以被視為一顆完全二叉樹結(jié)構(gòu)。

網(wǎng)站建設哪家好，找成都創(chuàng)新互聯(lián)！專注于網(wǎng)頁設計、網(wǎng)站建設、微信開發(fā)、微信小程序開發(fā)、集團企業(yè)網(wǎng)站建設等服務項目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了朝陽免費建站歡迎大家使用！

最大堆：每個父節(jié)點都大于孩子節(jié)點。

最小堆：每個父節(jié)點都小于孩子節(jié)點。

堆排序的思想：對于給定的N個數(shù)據(jù)，初始時把這些記錄看作是一顆順序存儲的二叉樹，然后將其調(diào)整為一個最大堆，然后將堆的最后一個元素與堆頂元素（即二叉樹的根節(jié)點）進行交換，堆的最后一個元素即為最大記錄；接著將（N-1）個元素（即不包括最大記錄）重新調(diào)整為一個最大堆，再將堆頂元素與堆的最后一個元素進行交換后得到次大的記錄，重復該過程直到調(diào)整的堆只剩下一個元素為止，該元素即為最小記錄，此時可得到一個有序序列。

堆排序主要包括兩個過程：一是構(gòu)建堆；二是交換堆頂元素與最后一個元素的位置。

程序如下：

#include<iostream>
#include<assert.h>
using namespace std;

void AdjustDown(int *array,int size,int root)
{
	assert(array);
	int child = 2 * root + 1;
	while (child < size)
	{
		if (child + 1 < size&&array[child] < array[child + 1])
		{
			++child;
		}
		if (array[child]>array[root])
		{
			swap(array[root],array[child]);
			root = child;
			child = 2 * root + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int *array, int size, int root)
{
	//找到第一個非葉子節(jié)點構(gòu)建堆
	for (int i = (size - 2) / 2; i >= 0; --i)
	{
		AdjustDown(array,size,0);
	}
	for (int i = 0; i < size; ++i)
	{
		swap(array[0],array[size-1-i]);
		AdjustDown(array,size-1-i,0);
	}
}

int main()
{
	int array[10] = {12,10,16,6,8,9,11,9,7,13};
	for (int i = 0; i < 10; ++i)
	{
		cout << array[i] << " ";
	}
	cout << endl;
	HeapSort(array,10,0);
	for (int i = 0; i < 10; ++i)
	{
		cout << array[i] << " ";
	}
	cout << endl;
	return 0;
}

程序運行結(jié)果：

    

        堆排序方法對記錄較少的文件效果一般，但對于 記錄較多的文件還是很有效的，其運行時間主要耗費在創(chuàng)建堆和反復調(diào)整堆上。堆排序即使在最壞的情況下，其時間復雜度也為O（N*logN）。         

文章標題：用C++實現(xiàn)堆排序
網(wǎng)頁路徑：http://chinadenli.net/article44/pigche.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站改版、虛擬主機、網(wǎng)站制作、靜態(tài)網(wǎng)站、網(wǎng)站設計公司、網(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)