目錄

• 堆的本質(zhì)
• • 堆的一般作用
  • 建堆的主要思想及動(dòng)圖解釋
  • 堆中數(shù)據(jù)的刪除及動(dòng)圖解釋
  • 堆的存儲(chǔ)方式 及 父親和孩子節(jié)點(diǎn)的計(jì)算
  • 堆的構(gòu)建
  • 堆的插入
  • 堆的刪除
  • 在無(wú)序數(shù)組上建堆（用數(shù)組中已有數(shù)據(jù)構(gòu)建）
  • 建堆時(shí)間復(fù)雜度
  • 堆排序
  • 堆排序的實(shí)現(xiàn)

創(chuàng)新互聯(lián)公司自2013年起，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目成都網(wǎng)站建設(shè)、成都網(wǎng)站制作網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元正陽(yáng)做網(wǎng)站,已為上家服務(wù),為正陽(yáng)各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:18982081108堆的本質(zhì)

堆的本質(zhì)是完全二叉樹(shù)，但堆分為大堆和小堆
大堆：樹(shù)中所以的父親都大于左右孩子
小堆：樹(shù)中所有的父親都小于左右孩子

堆的一般作用

選出前n個(gè)大或最小的值，選大用大堆選小用小堆，以及堆排序的應(yīng)用
但本文只涉及堆的建立及選出前n個(gè)大或最小的值

建堆的主要思想及動(dòng)圖解釋

以大堆為列，從二叉樹(shù)下方插入數(shù)據(jù)（暫且稱為孩子）然后讓此孩子與父親節(jié)點(diǎn)比較如果他大于父親節(jié)點(diǎn)。則父親節(jié)點(diǎn)與與孩子節(jié)點(diǎn)交換位置，交換完后再與當(dāng)前節(jié)點(diǎn)的父親節(jié)點(diǎn)比較如果仍比父親大則交換，如果小于等于則調(diào)整結(jié)束

這個(gè)調(diào)整過(guò)程由于是從二叉樹(shù)的下方向上比較并調(diào)整，所以咱可以把他稱為向上調(diào)整，如下圖是建大堆的過(guò)程建議觀看兩遍以上

堆中數(shù)據(jù)的刪除及動(dòng)圖解釋

上面已經(jīng)說(shuō)了堆一般都是用于解決前n個(gè)較大或較小的值，或者堆排序。所以堆中數(shù)據(jù)的刪除都是刪除堆頂，刪除中間的值意義不大但思想相同。所以這里主要講解如何刪除堆頂數(shù)據(jù)，以及刪除后如何調(diào)整。

總結(jié)：第一步將堆最后一位數(shù)據(jù)覆蓋到堆頂數(shù)據(jù)位置，然后與左右孩子中較大的一位比較，如比他小則交換位置。交換完后再與當(dāng)前位置的左右孩子中較大的孩子比較，如比他小則交換位置。直至沒(méi)有孩子或比左右孩子都大為止。

這個(gè)調(diào)整過(guò)程由于是從二叉樹(shù)的上方向下方比較并調(diào)整，所以咱可以把他稱為向下調(diào)整

堆的存儲(chǔ)方式 及 父親和孩子節(jié)點(diǎn)的計(jì)算

堆雖然是一顆完全二叉樹(shù)，但它的存儲(chǔ)方式一般為數(shù)組存儲(chǔ)，就是說(shuō)堆的所有節(jié)點(diǎn)都存儲(chǔ)在數(shù)組當(dāng)中。
如下圖

以下公式數(shù)據(jù)類型為int

孩子節(jié)點(diǎn)的計(jì)算
假設(shè)父節(jié)點(diǎn)的下標(biāo)是parent，那么它的左孩子下標(biāo)就是 2*parent+1；它的右孩子下標(biāo)就是 2*parent+2 。
比如父親節(jié)點(diǎn)下標(biāo)為 1 ， 則其左孩子下標(biāo)為 2 * 1 + 1 = 3 ；右孩子下標(biāo)為 2 * 1 + 2 = 4（不懂對(duì)照?qǐng)D多讀幾遍）

父親節(jié)點(diǎn)的計(jì)算
假設(shè)孩子節(jié)點(diǎn)下標(biāo)為son(左右孩子均可),那他的父節(jié)下標(biāo)(son-1)/2。
如孩子下標(biāo)為4 ，則父親下標(biāo)為 （4 - 1）/ 2 = 1；

堆的構(gòu)建 堆的插入

比如插入一個(gè)10到數(shù)組的尾上，再進(jìn)行向上調(diào)整算法，直到滿足堆的結(jié)構(gòu)要求。
向上調(diào)整：從二叉樹(shù)下方插入數(shù)據(jù)（暫且稱為孩子）然后讓此孩子與父親節(jié)點(diǎn)比較如果他大于父親節(jié)點(diǎn)。則父親節(jié)點(diǎn)與與孩子節(jié)點(diǎn)交換位置，交換完后再與當(dāng)前節(jié)點(diǎn)的父親節(jié)點(diǎn)比較如果仍比父親大則交換，如果小于等于則調(diào)整結(jié)束

堆的刪除

刪除堆是刪除堆頂?shù)臄?shù)據(jù)，將堆頂?shù)臄?shù)據(jù)根最后一個(gè)數(shù)據(jù)一換，然后刪除數(shù)組最后一個(gè)數(shù)據(jù)，再進(jìn)行向下調(diào)整算法。
向下調(diào)整：第一步將堆最后一位數(shù)據(jù)覆蓋到堆頂數(shù)據(jù)位置，然后與左右孩子中較大的一位比較，如比他小則交換位置。交換完后再與當(dāng)前位置的左右孩子中較大的孩子比較，如比他小則交換位置。直至沒(méi)有孩子或比左右孩子都大為止。

下面是代碼實(shí)現(xiàn)功能包括：初始化，堆的銷毀，插入數(shù)據(jù)，刪除堆頂數(shù)據(jù)，查看堆頂數(shù)據(jù)，打印堆中數(shù)據(jù)等；
分三個(gè)源文件Heap.h是程序頭文件，heap.c是堆的功能性函數(shù)源文件，main.c是測(cè)試heap.c中函數(shù)功能用的

下面是heap.c

#include"Heap.h"
void HpInit(HP* head)//初始化
{assert(head);
	head->data = NULL;
	head->size = head->capacity = 0;
}
void HpDestroy(HP* head)//銷毀
{assert(head);
	free(head->data);
	head->data = NULL;
	head->size = head->capacity = 0;
}
void Swp(HP* head, int sor, int parent)//交換函數(shù)
{HeapData cur = head->data[sor];
	head->data[sor] = head->data[parent];
	head->data[parent] = cur;
}
//插入調(diào)整函數(shù)
void Adjustup(HP* head)
{assert(head);
	int sor = head->size;//要調(diào)整的數(shù)
	while (sor >0)
	{int parent = (sor - 1) / 2;//求其父親節(jié)點(diǎn)
		if (head->data[sor]<= head->data[parent])
		{	break;//比父親節(jié)點(diǎn)小或等于跳出
		}
		Swp(head, sor, parent);//如果比父親節(jié)點(diǎn)大就交換
		sor = parent;
	}
}
void HpPus(HP* head , HeapData data)//插入數(shù)據(jù)
{assert(head);//
	if (head->capacity == head->size)//相等說(shuō)明存滿了
	{head->capacity == 0 ? (head->capacity = 4) : (head->capacity *= 2);
		//head->capacity = 4;
		HeapData* cur = (HeapData*)realloc(head->data, sizeof(HeapData) * head->capacity);
		if (cur == NULL)//如果內(nèi)存申請(qǐng)失敗
		{	perror("realloc");
			exit(-1);
		}
		head->data = cur;
	}
	//開(kāi)始插入
	head->data[head->size] = data;
	//調(diào)整部分
	Adjustup(head);
	head->size++;//插入完成
}
void print(HP* head)//打印
{assert(head);
	int i = 0;
	while (i< head->size)
	{printf("%d ", head->data[i]);
		if ( i != 0 && i % 10 == 0 )
		{	printf("\n");
		}
		i++;
	}
}
//堆判空
bool HpEmpty(HP* head)
{assert(head);
	return !head->size;//為空返回真
}
void AdjustDown(HP* head)//刪除后向下調(diào)整
{assert(head);
	int parent = 0;
	while (parent< head->size)
	{int leftsor = parent * 2 + 1;//左孩子下標(biāo)
		if (leftsor >= head->size)//已經(jīng)調(diào)整完成，沒(méi)有這個(gè)不會(huì)有bug，誤打誤撞對(duì)了而已
		{	break;
		}
		if (leftsor + 1< head->size && head->data[leftsor]< head->data[leftsor + 1])
		{	leftsor++;//找出左右孩子中較大的一位，注意leftsor + 1不要越界
		}
		if (head->data[parent] >= head->data[leftsor])//已經(jīng)調(diào)整完成
		{	break;
		}
		//如果parent小于他的孩子則交換
		Swp(head, leftsor, parent);
		parent = leftsor;
	}
	//調(diào)整完成結(jié)束
}
//堆的中間刪沒(méi)意義，一般都是刪除堆頂
void HpPop(HP* head)
{assert(head);
	if (HpEmpty(head))
	{printf("無(wú)數(shù)據(jù)\n");
		return;
	}
	head->data[0] = head->data[head->size - 1];//刪除頭部數(shù)據(jù)
	head->size--;
	//向下調(diào)整數(shù)據(jù)
	AdjustDown(head);
	//刪除完成
}
HeapData HpTop(HP* head)//查看頭部數(shù)據(jù)
{assert(head);
	if (HpEmpty(head))
	{printf("無(wú)數(shù)據(jù)\n");
		return -1;
	}
	 return head->data[0];
}
int Hpsize(HP* head)//查看數(shù)據(jù)個(gè)數(shù)
{assert(head);
	return head->size;
}

下面是main.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void Text1()
{HP head;
	HpInit(&head);
	int i = 0;
	int x = 0;
	do
	{printf("\n1 插入  2 刪除  3 打印  4 查看頭部數(shù)據(jù) \n");
		printf("請(qǐng)輸入需要的功能\n");
		scanf("%d", &i);
		switch (i)
		{case 1:
			printf("請(qǐng)輸入數(shù)據(jù)\n");
			scanf("%d", &x);
			HpPus(&head, x);
			break;
		case 2:
			HpPop(&head);
			break;
		case 3:
			print(&head);
			break;
		case 4:
			printf("%d", HpTop(&head));
			break;
		}

	} while (i);
}
int main()
{Text1();

	return 0;
}

下面是Heap.h

#pragma once
#include#include#include#include
#includetypedef int HeapData;

typedef struct heap
{HeapData* data;
	int size;//實(shí)際數(shù)據(jù)個(gè)數(shù)
	int capacity;//空間容量
}HP; 

void HpInit(HP* head);//初始化
void HpDestroy(HP* head);//銷毀
void HpPus(HP* head, HeapData data);//插入數(shù)據(jù)
void print(HP* head);//打印
void HpPop(HP* head);//頭刪
HeapData HpTop(HP* head);//查看頭部數(shù)據(jù)
int Hpsize(HP* head);//查看數(shù)據(jù)個(gè)數(shù)

在無(wú)序數(shù)組上建堆（用數(shù)組中已有數(shù)據(jù)構(gòu)建）

下面我們給出一個(gè)數(shù)組，這個(gè)數(shù)組邏輯上可以看做一顆完全二叉樹(shù)，但是還不是一個(gè)堆，現(xiàn)在我們通過(guò)算法，把它構(gòu)建成一個(gè)堆。根節(jié)點(diǎn)左右子樹(shù)不是堆，我們?cè)趺凑{(diào)整呢？這里我們從倒數(shù)的第一個(gè)非葉子節(jié)點(diǎn)的子樹(shù)開(kāi)始調(diào)整，一直調(diào)整到根節(jié)點(diǎn)的樹(shù)，就可以調(diào)整成堆。

下面是調(diào)整圖解，第一次調(diào)整的是最后一個(gè)數(shù)據(jù)的父親節(jié)點(diǎn)（假設(shè)孩子節(jié)點(diǎn)下標(biāo)為son(左右孩子均可),那他的父節(jié)下標(biāo)(son-1)/2。如孩子下標(biāo)為4 ，則父親下標(biāo)為 （4 - 1）/ 2 = 1；）；

調(diào)整完后如最后一個(gè)數(shù)據(jù)的父親節(jié)點(diǎn)下標(biāo)為，i ,則直接 i-- ,繼續(xù)將 i 下標(biāo)視為堆頂繼續(xù)向下調(diào)整，直至i< 0 為止；

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

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

下面是代碼實(shí)現(xiàn)（為不破壞原有數(shù)組我是復(fù)制數(shù)組內(nèi)容后再進(jìn)行建堆的）：

void AdjustDown(HeapData* arr,int parent, int size)
{int leftson = parent * 2 + 1;//左孩子
	while (leftson< size)//
	{if (leftson + 1< size && arr[leftson + 1] >arr[leftson])
		{	leftson++;//如果右孩子大于左孩子
		}
		if (arr[leftson]< arr[parent])//如果孩子小于父親
		{	break;
		}
		Sawp(arr, leftson, parent);
		parent = leftson;
		leftson = parent * 2 + 1;
	}
}
void CreateHeap(HP* head, int* arr, int size)
{assert(head);
	int parent, son = size - 1;
	head->data = (HeapData*)malloc(sizeof(int) * size);//給數(shù)組的復(fù)制開(kāi)辟空間
	if (NULL == head->data)//如果開(kāi)辟失敗
	{perror("malloc");
		exit(-1);
	}
	memcpy(head->data, arr, sizeof(int) * size);//拷貝需要建堆的數(shù)組
	head->capacity = head->size = size;//開(kāi)區(qū)間
	for (parent = (son - 1) / 2; parent >= 0; parent--)//傳最后一個(gè)數(shù)字據(jù)的父親開(kāi)始建堆
	{AdjustDown(head->data, parent,head->size);//將父節(jié)點(diǎn)首地址傳過(guò)去
	}
}

堆排序

堆排序即利用堆的思想來(lái)進(jìn)行排序，總共分為兩個(gè)步驟：

1. 建堆
   升序：建大堆
   降序：建小堆
2. 利用堆刪除思想來(lái)進(jìn)行排序
   建堆和堆刪除中都用到了向下調(diào)整，因此掌握了向下調(diào)整，就可以完成堆序。

堆排序的實(shí)現(xiàn)

首先得用上面的的方法先建一個(gè)堆，再如下圖，先把堆頂數(shù)據(jù)與最后一位互換，交換結(jié)束再進(jìn)行一次向下調(diào)整把換上來(lái)的數(shù)調(diào)整到合適的地方要滿足堆的結(jié)構(gòu)要求。注意堆頂數(shù)據(jù)換到尾部后就不參與建堆了讓其保持不動(dòng)
不斷的換，及調(diào)整直至堆只剩一個(gè)數(shù)

下面是代碼實(shí)現(xiàn)：

void Sawp(HeapData* arr, int x, int y)//交換函數(shù)
{HeapData ch = arr[x];
	arr[x] = arr[y];
	arr[y] = ch;
}
void AdjustDown(HeapData* arr,int parent, int size)//向下調(diào)整
{int leftson = parent * 2 + 1;//左孩子
	while (leftson< size)//
	{if (leftson + 1< size && arr[leftson + 1] >arr[leftson])
		{	leftson++;//如果右孩子大于左孩子
		}
		if (arr[leftson]< arr[parent])//如果孩子小于父親
		{	break;
		}
		Sawp(arr, leftson, parent);
		parent = leftson;
		leftson = parent * 2 + 1;
	}
}
//堆排序
void HeapSort(int* arr, int size)
{assert(arr);
	int parent, son = size - 1;
	for (parent = (son - 1) / 2; parent >= 0; parent--)//傳最后一個(gè)數(shù)據(jù)的父親開(kāi)始建堆
	{AdjustDown(arr, parent, size);//將父節(jié)點(diǎn)首地址傳過(guò)去
	}
	//上面是建堆，下面需要進(jìn)行堆排序
	int Hpsize = size-1;//數(shù)組最后一位
	for (Hpsize; Hpsize >0; Hpsize--)
	{Sawp(arr, 0, Hpsize);//每次將較大值換到最后一位
		AdjustDown(arr, 0 , Hpsize);//交換完后調(diào)整,不調(diào)整剛剛換的那一位
	}
}

到這就結(jié)束啦，不足的地方歡迎評(píng)論區(qū)指教

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

標(biāo)題名稱：圖解代碼堆的構(gòu)建及堆排序-創(chuàng)新互聯(lián)
分享鏈接：http://aaarwkj.com/article4/hchie.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站營(yíng)銷、用戶體驗(yàn)、軟件開(kāi)發(fā)、靜態(tài)網(wǎng)站、服務(wù)器托管、外貿(mào)網(wǎng)站建設(shè)

廣告

聲明：本網(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í)需注明來(lái)源： 創(chuàng)新互聯(lián)