中文字幕日韩精品一区二区免费_精品一区二区三区国产精品无卡在_国精品无码专区一区二区三区_国产αv三级中文在线

堆（C語言實(shí)現(xiàn)）-創(chuàng)新互聯(lián)

文章目錄：
  • 1.堆的概念
  • 2.堆的性質(zhì)
  • 3.堆的結(jié)構(gòu)
  • 4.接口實(shí)現(xiàn)
    • 4.1初始化堆
    • 4.2銷毀堆
    • 4.3打印堆內(nèi)元素
    • 4.4向上調(diào)整
    • 4.5向堆中插入數(shù)據(jù)
    • 4.6向下調(diào)整
    • 4.7刪除堆頂元素
    • 4.8查看堆頂元素
    • 4.9統(tǒng)計(jì)堆內(nèi)數(shù)據(jù)個(gè)數(shù)
    • 4.10判斷堆是否為空
    • 4.11堆的構(gòu)建

在達(dá)拉特等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè) 網(wǎng)站設(shè)計(jì)制作按需網(wǎng)站設(shè)計(jì),公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),品牌網(wǎng)站設(shè)計(jì),成都全網(wǎng)營銷推廣,成都外貿(mào)網(wǎng)站制作,達(dá)拉特網(wǎng)站建設(shè)費(fèi)用合理。1.堆的概念

如果有一個(gè)關(guān)鍵碼的集合，把它的所有元素按完全二叉樹的順序存儲(chǔ)方式存儲(chǔ)在一個(gè)一維數(shù)組中，孩子節(jié)點(diǎn)都不大于父節(jié)點(diǎn)的稱為小堆，孩子節(jié)點(diǎn)都不大于其父節(jié)點(diǎn)的稱為大堆

圖示：

由此可以看出：任何數(shù)組都可以看做完全二叉樹，但不一定是堆

2.堆的性質(zhì)

1.堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值
2.堆總是一棵完全二叉樹
3.孩子節(jié)點(diǎn)和父親節(jié)點(diǎn)下標(biāo)的關(guān)系：

  • parent = (child - 1) / 2
  • leftchild = parent * 2 + 1
  • rightchild = parent * 2 + 2
3.堆的結(jié)構(gòu)

堆總是一棵完全二叉樹，堆是用數(shù)組來存儲(chǔ)的

typedef int HPDataType;//數(shù)據(jù)類型
typedef struct Heap
{HPDataType* a;//數(shù)組
	int size;//數(shù)據(jù)個(gè)數(shù)
	int capacity;//容量
}HP;
4.接口實(shí)現(xiàn) 4.1初始化堆

將數(shù)組指針指向NULL，將數(shù)據(jù)個(gè)數(shù)和容量置零方便后面統(tǒng)計(jì)和判斷容量，這里斷言php是防止人為不小心傳入了空指針

//初始化堆
void HeapInit(HP* php)
{assert(php);
	php->a = NULL;// 指空
	php->size = php->capacity = 0;// 置零
}
4.2銷毀堆

釋放掉數(shù)組，并將數(shù)組指針指空，將數(shù)據(jù)個(gè)數(shù)和容量置零即可

//銷毀堆
void HeapDestroy(HP* php)
{assert(php);
	free(php->a);//釋放
	php->a = NULL;//指空
	php->size = php->capacity = 0;//置零
}
4.3打印堆內(nèi)元素

遍歷數(shù)組將其內(nèi)的元素打印出來即可

//打印堆內(nèi)元素
void HeapPrint(HP* php)
{assert(php);	
	//遍歷打印
	for(int i = 0; i< php->size; ++i)
	{printf("%d ", php->a[i]);
	}
	printf("\n");
}
4.4向上調(diào)整

將孩子節(jié)點(diǎn)的數(shù)據(jù)和其父結(jié)點(diǎn)的數(shù)據(jù)進(jìn)行比較，若孩子節(jié)點(diǎn)的數(shù)據(jù)大于（小于）父節(jié)點(diǎn)的數(shù)據(jù)就交換并繼續(xù)向上調(diào)整，直到根結(jié)點(diǎn)（數(shù)組中下標(biāo)為0的元素）位置就停止，這里對(duì)父子節(jié)點(diǎn)的比較是根據(jù)堆是大堆還是小堆來決定的

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

//向上調(diào)整
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;
	while (child >0)
	{//孩子大于(小于)父親，就交換并繼續(xù)向上調(diào)整，反之則調(diào)整結(jié)束
		//if (a[child] >a[parent])
		if (a[child]< a[parent])
		{	Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{	break;
		}
	}
}
4.5向堆中插入數(shù)據(jù)

首先創(chuàng)建一個(gè)新節(jié)點(diǎn)，并判斷數(shù)組是否需要擴(kuò)容，然后直接向數(shù)組尾部插入一個(gè)數(shù)據(jù)，將該數(shù)據(jù)向上調(diào)整（保證結(jié)構(gòu)繼續(xù)是個(gè)堆）即可

//向堆中插入數(shù)據(jù)
void HeapPush(HP* php, HPDataType x)
{assert(php);
	//判斷擴(kuò)容
	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)//判斷防止擴(kuò)容失敗
		{	perror("realloc fail");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	//將新的數(shù)據(jù)插入數(shù)組尾部
	php->a[php->size] = x;
	php->size++;//數(shù)據(jù)個(gè)數(shù)+1
	AdjustUp(php->a, php->size - 1);//從尾節(jié)點(diǎn)開始向上調(diào)整
}
4.6向下調(diào)整

將孩子節(jié)點(diǎn)的數(shù)據(jù)和其父結(jié)點(diǎn)的數(shù)據(jù)進(jìn)行比較，若孩子節(jié)點(diǎn)的數(shù)據(jù)大于（小于）父節(jié)點(diǎn)的數(shù)據(jù)就交換并繼續(xù)向小調(diào)整，直到最后一個(gè)節(jié)點(diǎn)（數(shù)組中的最后一個(gè)的元素）就停止，這里對(duì)父子節(jié)點(diǎn)的比較是根據(jù)堆是大堆還是小堆來決定的

//向下調(diào)整
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;//默認(rèn)是左孩子
	while (child< n)
	{//確認(rèn)child指向大的(小的)那個(gè)孩子
		//if (a[child + 1] >a[child] && child + 1< n)
		if (a[child + 1]< a[child] && child + 1< n)
		{	++child;//換成右孩子
		}
		//孩子大于(小于)父親，就交換并繼續(xù)向下調(diào)整，反之則調(diào)整結(jié)束
		//if (a[child] >a[parent])
		if (a[child]< a[parent])
		{	Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{	break;
		}
	}
}
4.7刪除堆頂元素

將堆頂元素和堆尾數(shù)據(jù)元素交換并刪除堆尾(此時(shí)堆尾數(shù)據(jù)也就是堆頂數(shù)據(jù)），再從根節(jié)點(diǎn)開始向下調(diào)整（保證它繼續(xù)是個(gè)堆）即可，這里需要斷言堆為空的情況，為空不能刪

//刪除堆頂元素
void HeapPop(HP* php)
{assert(php);
	//斷言堆為空
	assert(php->size >0);
	//交換堆頂元素和堆尾元素
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;//數(shù)據(jù)個(gè)數(shù)-1
	AdjustDown(php->a, php->size, 0);//從根節(jié)點(diǎn)開始向下調(diào)整
}
4.8查看堆頂元素

數(shù)組首元素就是堆頂元素，直接將其返回即可，這里需要斷言堆為空的情況，為空無堆頂元素

//查看堆頂元素
HPDataType HeapTop(HP* php)
{assert(php);
	//斷言堆為空
	assert(php->size >0);
	//返回?cái)?shù)組首元素（堆頂元素）
	return php->a[0];
}
4.9統(tǒng)計(jì)堆內(nèi)數(shù)據(jù)個(gè)數(shù)

結(jié)構(gòu)體中的size就是有效數(shù)據(jù)的個(gè)數(shù)，直接將其返回即可

//統(tǒng)計(jì)堆內(nèi)數(shù)據(jù)個(gè)數(shù)
int HeapSize(HP* php)
{assert(php);
	//返回有效數(shù)據(jù)個(gè)數(shù)
	return php->size;
}
4.10判斷堆是否為空

如果堆內(nèi)的有效數(shù)據(jù)個(gè)數(shù)為0，則堆為空，直接返回其布爾值即可

//判斷堆是否為空
bool HeapEmpty(HP* php)
{assert(php);
	//有效數(shù)據(jù)個(gè)數(shù)為0則堆為空
	return php->size == 0;
}
4.11堆的構(gòu)建

我們可以人為傳入一個(gè)數(shù)組來建堆，首先需要開辟一個(gè)與傳入的數(shù)組大小相同的空間，用來將數(shù)組中的內(nèi)容復(fù)制到該空間中，然后從最后一個(gè)元素的父節(jié)點(diǎn)開始（(size-1-1)/2）依次向前可以遍歷到每顆子樹的父節(jié)點(diǎn)，并對(duì)每顆子樹向下調(diào)整

//堆的構(gòu)建
void HeapCreate(HP* php, HPDataType* a, int n)
{assert(php);
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{perror("malloc fail");
		exit(-1);
	}
	//將數(shù)組復(fù)制到開辟的空間中
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->size = php->capacity = n;

	//建堆算法
	//從最后一個(gè)元素的父節(jié)點(diǎn)開始依次向前可以遍歷到每顆子樹的父節(jié)點(diǎn)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{AdjustDown(php->a, n, i);
	}
}

圖解：

堆的實(shí)現(xiàn)到這里就介紹結(jié)束了，期待大佬們的三連！你們的支持是我大的動(dòng)力！
文章有寫的不足或是錯(cuò)誤的地方，歡迎評(píng)論或私信指出，我會(huì)在第一時(shí)間改正。

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

新聞名稱：堆（C語言實(shí)現(xiàn)）-創(chuàng)新互聯(lián)
當(dāng)前鏈接：http://www.rwnh.cn/article4/jcdoe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)頁設(shè)計(jì)公司、域名注冊(cè)、建站公司、微信小程序、網(wǎng)站營銷、品牌網(wǎng)站制作

廣告

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

成都網(wǎng)站建設(shè)公司
刚察县| 小金县| 三河市| 安阳县| 土默特右旗| 京山县| 仪陇县| 宁南县| 阿拉善右旗| 汾阳市| 东源县| 江源县| 济阳县| 舟曲县| 辛集市| 和政县| 阜平县| 镇赉县| 如东县| 五原县| 固原市| 壶关县| 尤溪县| 福泉市| 临潭县| 铁岭县| 镇赉县| 翁源县| 宿松县| 辉县市| 阿鲁科尔沁旗| 新余市| 夏津县| 嘉荫县| 新安县| 林州市| 杭州市| 尚义县| 且末县| 鲁甸县| 马公市|