C語言實現(xiàn)堆的一些簡單接口-創(chuàng)新互聯(lián)

一.堆是什么？ 二.堆的簡單接口如何實現(xiàn)？ 三.堆的意義？

//////

成都創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),景德鎮(zhèn)企業(yè)網(wǎng)站建設(shè),景德鎮(zhèn)品牌網(wǎng)站建設(shè),網(wǎng)站定制,景德鎮(zhèn)網(wǎng)站建設(shè)報價,網(wǎng)絡(luò)營銷,網(wǎng)絡(luò)優(yōu)化,景德鎮(zhèn)網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競爭力。可充分滿足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時我們時刻保持專業(yè)、時尚、前沿，時刻以成就客戶成長自我，堅持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實用型網(wǎng)站。1.堆是什么？

含義：堆實質(zhì)上是用一維數(shù)組（比鏈表實現(xiàn)更優(yōu)）存貯一種特殊的二叉樹（完全二叉樹）的一種順序存貯方式；所以，堆總是一顆完全二叉樹，而且堆還有大小堆之分；

大堆：根節(jié)點是堆中大的數(shù)，且每一個父節(jié)點總是大于等于自己的子節(jié)點；

小堆：根節(jié)點是堆中最小的數(shù)，且每一個父節(jié)點總是小于自己的子節(jié)點

如下圖所示：（不一定是有序的數(shù)組，這只是方便舉例）

/////

2.堆的簡單接口實現(xiàn)

2.1 初始化堆：既然是用一維數(shù)組實現(xiàn)，根據(jù)之前對棧等線性表用數(shù)組實現(xiàn)的學(xué)習(xí)，我們應(yīng)該知道此時需要用結(jié)構(gòu)體來構(gòu)建其結(jié)構(gòu)，結(jié)構(gòu)體中包含 存貯完全二叉樹中的節(jié)點信息的數(shù)組array，記錄多少個節(jié)點的size， 以及用來判斷是否需要擴(kuò)容的capacity;，具體代碼如下所示：

//定義結(jié)構(gòu)體，表示堆的信息：
typedef int typedata;
typedef struct HeapNode
{
	typedata* arr;
	int size;
	int capacity;
}HP;




//初始化堆
void HeapInit(HP* ps)//這里我沒有先malloc空間，到后面插入的時候直接realloc就可以了；
{
	assert(ps);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

//

2.2 向堆中依次插入元素（向上調(diào)整法）：

//向堆中插入：
void swap(typedata* p1, typedata* p2)
{
	int temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}
void AdjustUP(typedata* ps, int child)
{
	int parent = (child - 1) / 2;//找到此時子節(jié)點的父節(jié)點，比較看是否需要向上調(diào)整；
	while (child >0)
	{
		if (ps[child] >ps[parent])//如果子節(jié)點的值大于父節(jié)點的值
		{
			swap(&ps[child], &ps[parent]);//交換函數(shù)：交換子節(jié)點與父節(jié)點的值；
			child = parent;//將父節(jié)點的數(shù)組下標(biāo)給子節(jié)點，
			parent = (child - 1) / 2;//讓子節(jié)點找到新的父節(jié)點，繼續(xù)比較；
		}
		else
		{
			break;
		}
	}
}
void HeapPush(HP* ps, typedata x)
{
	assert(ps);

	//擴(kuò)容:
	if (ps->size == ps->capacity)
	{
		ps->capacity = 0 ? 4 : ps->capacity * 2;
		typedata* ptr = realloc(ps->arr,sizeof(typedata) *(ps->capacity));
		if (ptr == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->arr = ptr;
	}
	ps->arr[ps->size] = x;
	ps->size++;

	//向上調(diào)整建堆：
	AdjustUP(ps->arr, ps->size - 1);
}



//定義數(shù)組，調(diào)用插入接口依次插入：
int arr[10] = { 17,11,12,25,36,46,71,42,29,100 };
for (int i = 0; i< sizeof(arr) / sizeof(arr[0]); i++)
{
	//向堆中依次插入元素：
	HeapPush(&ps, arr[i]);
}

//

2.3 刪除堆頂元素（向下調(diào)整法）：

void AdjustDown(typedata* ps, int n, int parent)
{
	assert(ps);
	int child = parent * 2 + 1;
	while (childps[parent])
		{
			swap(&ps[parent], &ps[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
//刪除堆頂元素接口：
void HeapPop(HP* ps)
{
	assert(!HeapEmpty(ps));
	swap(&ps->arr[0], &ps->arr[ps->size - 1]);//先將堆頂與堆底交換；
	ps->size--;//利用數(shù)組下標(biāo)刪除掉交換過來的堆頂；

	//向下調(diào)整建堆：
	AdjustDown(ps->arr, ps->size - 1, 0);

	
}

//

2.4 Topk問題（取堆中k個大或最小的元素）：

//Top(選取大或最小的元素)接口:
typedata HeapTop(HP* ps)//有返回值；
{
	assert(!HeapEmpty(ps));//調(diào)用判空接口對結(jié)構(gòu)體判空
	return ps->arr[0];//返回堆頂元素；
}	


//Topk問題：取堆中大或最小的前K個元素：
int k = 5;
while(k--)
{
	printf("%d ", HeapTop(&ps));//調(diào)用Top接口，獲取堆頂元素，并打印出來；
	HeapPop(&ps);//調(diào)用刪除堆頂元素接口，刪除掉打印過的堆頂，找堆中新的堆頂，實現(xiàn)多次尋找；
}

//

2.4 堆中元素個數(shù)，判空，打印以及銷毀：

這幾個接口比較簡單，直接給出代碼：

//判空：
bool HeapEmpty(HP* ps)
{
	assert(ps);
	return ps->size == 0;
}

//堆中元素個數(shù)：
size_t Heapsize(HP* ps)
{
	assert(!HeapEmpty(ps));
	return ps->size;
}

//打印堆：
void HeapPrint(HP* ps)
{
	assert(!HeapEmpty(ps));
	int i = 0;
	for (i = 0; i< ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

//銷毀堆：
void HeapDestroty(HP* ps)
{
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

/////

3，堆的意義？

意義：堆的意義在于存貯完全二叉樹時同時可以通過堆排序（時間復(fù)雜度為O(n*log N)），快速的進(jìn)行排序，此意義我將會在后面與其他幾種排序中盡我大的能力去說明與理解；

/////

至此，這是我對堆的創(chuàng)建，堆的一些簡單接口的實現(xiàn)的全部理解，如有不足之處，請各位大佬不吝賜教，謝謝！

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

分享標(biāo)題：C語言實現(xiàn)堆的一些簡單接口-創(chuàng)新互聯(lián)
網(wǎng)頁網(wǎng)址：http://muchs.cn/article12/dchddc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供自適應(yīng)網(wǎng)站、營銷型網(wǎng)站建設(shè)、企業(yè)建站、品牌網(wǎng)站建設(shè)、動態(tài)網(wǎng)站、Google

廣告

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

搜索引擎優(yōu)化