圖解代碼堆的構(gòu)建及堆排序-創(chuàng)新互聯(lián)

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

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

堆的本質(zhì)是完全二叉樹，但堆分為大堆和小堆
大堆：樹中所以的父親都大于左右孩子
小堆：樹中所有的父親都小于左右孩子
在這里插入圖片描述

堆的一般作用

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

建堆的主要思想及動圖解釋

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

這個調(diào)整過程由于是從二叉樹的下方向上比較并調(diào)整，所以咱可以把他稱為向上調(diào)整，如下圖是建大堆的過程建議觀看兩遍以上
請?zhí)砑訄D片描述

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

上面已經(jīng)說了堆一般都是用于解決前n個較大或較小的值，或者堆排序。所以堆中數(shù)據(jù)的刪除都是刪除堆頂，刪除中間的值意義不大但思想相同。所以這里主要講解如何刪除堆頂數(shù)據(jù)，以及刪除后如何調(diào)整。
請?zhí)砑訄D片描述
總結(jié)：第一步將堆最后一位數(shù)據(jù)覆蓋到堆頂數(shù)據(jù)位置，然后與左右孩子中較大的一位比較，如比他小則交換位置。交換完后再與當(dāng)前位置的左右孩子中較大的孩子比較，如比他小則交換位置。直至沒有孩子或比左右孩子都大為止。

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

堆的存儲方式 及 父親和孩子節(jié)點的計算

堆雖然是一顆完全二叉樹，但它的存儲方式一般為數(shù)組存儲，就是說堆的所有節(jié)點都存儲在數(shù)組當(dāng)中。
如下圖
在這里插入圖片描述
以下公式數(shù)據(jù)類型為int

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

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

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

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

堆的刪除

刪除堆是刪除堆頂?shù)臄?shù)據(jù)，將堆頂?shù)臄?shù)據(jù)根最后一個數(shù)據(jù)一換，然后刪除數(shù)組最后一個數(shù)據(jù)，再進行向下調(diào)整算法。
向下調(diào)整：第一步將堆最后一位數(shù)據(jù)覆蓋到堆頂數(shù)據(jù)位置，然后與左右孩子中較大的一位比較，如比他小則交換位置。交換完后再與當(dāng)前位置的左右孩子中較大的孩子比較，如比他小則交換位置。直至沒有孩子或比左右孩子都大為止。
在這里插入圖片描述
下面是代碼實現(xiàn)功能包括：初始化，堆的銷毀，插入數(shù)據(jù)，刪除堆頂數(shù)據(jù)，查看堆頂數(shù)據(jù)，打印堆中數(shù)據(jù)等；
分三個源文件Heap.h是程序頭文件，heap.c是堆的功能性函數(shù)源文件，main.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é)點
		if (head->data[sor]<= head->data[parent])
		{	break;//比父親節(jié)點小或等于跳出
		}
		Swp(head, sor, parent);//如果比父親節(jié)點大就交換
		sor = parent;
	}
}
void HpPus(HP* head , HeapData data)//插入數(shù)據(jù)
{assert(head);//
	if (head->capacity == head->size)//相等說明存滿了
	{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)存申請失敗
		{	perror("realloc");
			exit(-1);
		}
		head->data = cur;
	}
	//開始插入
	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)整完成，沒有這個不會有bug，誤打誤撞對了而已
		{	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é)束
}
//堆的中間刪沒意義，一般都是刪除堆頂
void HpPop(HP* head)
{assert(head);
	if (HpEmpty(head))
	{printf("無數(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("無數(shù)據(jù)\n");
		return -1;
	}
	 return head->data[0];
}
int Hpsize(HP* head)//查看數(shù)據(jù)個數(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("請輸入需要的功能\n");
		scanf("%d", &i);
		switch (i)
		{case 1:
			printf("請輸入數(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ù)據(jù)個數(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ù)個數(shù)
在無序數(shù)組上建堆（用數(shù)組中已有數(shù)據(jù)構(gòu)建）

下面我們給出一個數(shù)組，這個數(shù)組邏輯上可以看做一顆完全二叉樹，但是還不是一個堆，現(xiàn)在我們通過算法，把它構(gòu)建成一個堆。根節(jié)點左右子樹不是堆，我們怎么調(diào)整呢？這里我們從倒數(shù)的第一個非葉子節(jié)點的子樹開始調(diào)整，一直調(diào)整到根節(jié)點的樹，就可以調(diào)整成堆。
在這里插入圖片描述
下面是調(diào)整圖解，第一次調(diào)整的是最后一個數(shù)據(jù)的父親節(jié)點（假設(shè)孩子節(jié)點下標(biāo)為son(左右孩子均可),那他的父節(jié)下標(biāo)(son-1)/2。如孩子下標(biāo)為4 ，則父親下標(biāo)為 （4 - 1）/ 2 = 1；）；

調(diào)整完后如最后一個數(shù)據(jù)的父親節(jié)點下標(biāo)為，i ,則直接 i-- ,繼續(xù)將 i 下標(biāo)視為堆頂繼續(xù)向下調(diào)整，直至i< 0 為止；
在這里插入圖片描述

建堆時間復(fù)雜度

因為堆是完全二叉樹，而滿二叉樹也是完全二叉樹，此處為了簡化使用滿二叉樹來證明(時間復(fù)雜度本來看的就是近似值，多幾個節(jié)點不影響最終結(jié)果)：
在這里插入圖片描述
下面是代碼實現(xiàn)（為不破壞原有數(shù)組我是復(fù)制數(shù)組內(nèi)容后再進行建堆的）：

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ù)制開辟空間
	if (NULL == head->data)//如果開辟失敗
	{perror("malloc");
		exit(-1);
	}
	memcpy(head->data, arr, sizeof(int) * size);//拷貝需要建堆的數(shù)組
	head->capacity = head->size = size;//開區(qū)間
	for (parent = (son - 1) / 2; parent >= 0; parent--)//傳最后一個數(shù)字據(jù)的父親開始建堆
	{AdjustDown(head->data, parent,head->size);//將父節(jié)點首地址傳過去
	}
}
堆排序

堆排序即利用堆的思想來進行排序，總共分為兩個步驟：

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

首先得用上面的的方法先建一個堆，再如下圖，先把堆頂數(shù)據(jù)與最后一位互換，交換結(jié)束再進行一次向下調(diào)整把換上來的數(shù)調(diào)整到合適的地方要滿足堆的結(jié)構(gòu)要求。注意堆頂數(shù)據(jù)換到尾部后就不參與建堆了讓其保持不動
不斷的換，及調(diào)整直至堆只剩一個數(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--)//傳最后一個數(shù)據(jù)的父親開始建堆
	{AdjustDown(arr, parent, size);//將父節(jié)點首地址傳過去
	}
	//上面是建堆，下面需要進行堆排序
	int Hpsize = size-1;//數(shù)組最后一位
	for (Hpsize; Hpsize >0; Hpsize--)
	{Sawp(arr, 0, Hpsize);//每次將較大值換到最后一位
		AdjustDown(arr, 0 , Hpsize);//交換完后調(diào)整,不調(diào)整剛剛換的那一位
	}
}

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

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

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

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

廣告

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

成都app開發(fā)公司