? ? ? ? ? ? ? ? ? ? ? ? ? ?🌹個(gè)人主頁🌹：喜歡草莓熊的bear

? ? ? ? ? ? ? ? ? ? ? ? ? ?🌹專欄🌹：數(shù)據(jù)結(jié)構(gòu)

目錄

前言

一、堆的實(shí)現(xiàn)

1.1 堆的向下調(diào)整算法

思路：

1.2 堆的向上調(diào)整算法

1.3?堆的創(chuàng)建

1.4?堆的復(fù)雜度計(jì)算

向下調(diào)整建堆的復(fù)雜度：

? 向上調(diào)整建堆的復(fù)雜度：

1.5?堆的插入

1.6?堆的刪除

1.7?堆的代碼實(shí)現(xiàn)

總結(jié)

前言

在上期內(nèi)容介紹了二叉樹、還簡單提了一下堆的概念和大堆、小堆?；仡櫼幌露咽鞘紫仁峭耆鏄?#xff0c;因?yàn)槭峭耆鏄渌允褂脭?shù)組儲(chǔ)存比較合理。

一、堆的實(shí)現(xiàn)

1.1 堆的向下調(diào)整算法

int arr[] = {27,15,19,18,28,34,65,49,25,37};

?上面這幅圖就是向下調(diào)整的算法的過程圖

思路：

?假設(shè)我們通過向下調(diào)整算法建立小堆，我們就需要從根的左右子樹開始，比較得出左右子樹小的那一個(gè)和根比較，誰小誰就是根。我們之前還介紹父親節(jié)點(diǎn)和孩子節(jié)點(diǎn)的概念，我們這里就要使用到。根據(jù)我們上面的思路，向下調(diào)整算法需要通過比較還在節(jié)點(diǎn)后進(jìn)行調(diào)整。所以我們需要知道父親節(jié)點(diǎn)然后再找到孩子節(jié)點(diǎn)為什么要知道父親節(jié)點(diǎn)呢？我們通過數(shù)組儲(chǔ)存著堆，下標(biāo)就可以幫助我們找到孩子節(jié)點(diǎn)。

?大致思路就是這樣我們來寫代碼：

void Swap(HPDataType* x, HPDataType* y)//交換數(shù)據(jù)
{HPDataType tmp = *x;*x = *y;*y = tmp;
}void ADjustDown(HPDataType* a, int n,int parent)//向下調(diào)整
{int child = parent * 2 + 1;while (child < n){//假設(shè)法if (a[child] > a[child + 1] && child + 1 < n)//比較左右子樹，找到較小的子樹。{child++;}if (a[parent] > a[child])//數(shù)據(jù)交換{Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

?解釋一下個(gè)別代碼，child + 1? < n 防止數(shù)組越界。?

1.2 堆的向上調(diào)整算法

?向上調(diào)整我們需要從最后一層向上調(diào)整，所以我們是通過孩子節(jié)點(diǎn)得到父親節(jié)點(diǎn)。大致思路和向下調(diào)整一樣，比較孩子節(jié)點(diǎn)的大小后再和父親節(jié)點(diǎn)比較一直比較到根節(jié)點(diǎn)。根據(jù)child = parent *2+1 反推得到 parent = （ child -1 ）/2 。

直接上代碼：

void Swap(HPDataType* x, HPDataType* y)//交換數(shù)據(jù)
{HPDataType tmp = *x;*x = *y;*y = tmp;
}void ADjustUp(HPDataType* a,int child)//向上調(diào)整
{int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent= (child - 1) / 2;}else{break;}}
}

1.3?堆的創(chuàng)建

int a[] = {1,5,3,8,7,6};

1.4?堆的復(fù)雜度計(jì)算

向下調(diào)整建堆的復(fù)雜度：

? 向上調(diào)整建堆的復(fù)雜度：

是O(N) = N * logN 得到方法和向下調(diào)整一樣推導(dǎo)就可以了。

1.5?堆的插入

?堆的插入需要用的向上調(diào)整

1.6?堆的刪除

?

1.7?堆的代碼實(shí)現(xiàn)

堆的初始化、銷毀都是很簡單和之前寫的棧啊等等都十分相似。剩下一些 獲取堆頂元素、堆的個(gè)數(shù)、堆的判斷都比較簡單就不講解了給上了代碼。

typedef int HPDataType;typedef struct Heap//因?yàn)槎训亩x就是滿二叉樹與完全二叉樹，用數(shù)組儲(chǔ)存非常好。
{HPDataType* a;//數(shù)組int size;int capacity;
}Heap;//小堆情況下的初始化
void HPInit(Heap* php)
{assert(php);php->a = NULL;php->size = php->capacity = 0;
}//銷毀
void HPDestory(Heap* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}void Swap(HPDataType* x, HPDataType* y)//交換數(shù)據(jù)
{HPDataType tmp = *x;*x = *y;*y = tmp;
}void ADjustUp(HPDataType* a,int child)//向上調(diào)整
{int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent= (child - 1) / 2;}else{break;}}
}void ADjustDown(HPDataType* a, int n,int parent)//向下調(diào)整
{int child = parent * 2 + 1;while (child < n){//假設(shè)法if (a[child] > a[child + 1] && child + 1 < n){child++;}if (a[parent] > a[child]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//入堆
void HPPush(Heap* 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, Newcapacity * sizeof(HPDataType));if (tmp == NULL){perror("ralloc fail");return;}php->a = tmp;php->capacity = Newcapacity;}php->a[php->size++] = x; ADjustUp(php->a,php->size - 1);
}//出堆（消除堆頂數(shù)據(jù)）
void HPPop(Heap* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;ADjustDown(php->a,php->size,0);
}//取堆頂數(shù)據(jù)
HPDataType HPTop(Heap* php)
{assert(php);assert(php->size > 0);return php->a[0];
}//堆的數(shù)據(jù)個(gè)數(shù)
int HPSize(Heap* php)
{assert(php);return php->size;
}//堆的判空
bool HPEmpty(Heap* php)
{assert(php);return php->size == 0;
}

總結(jié)

本節(jié)重點(diǎn)堆的向上、向下調(diào)整算法的代碼實(shí)現(xiàn) 和 復(fù)雜度計(jì)算。