做人要謙虛，多聽聽別人的意見，然后記錄下來，看看誰對你有意見
一、二叉樹的順序（堆）結(jié)構(gòu)及實(shí)現(xiàn)
1.二叉樹的順序結(jié)構(gòu)
2.堆的概念及結(jié)構(gòu)
3.堆的實(shí)現(xiàn)
3.1 向下調(diào)整算法 AdJustDown
3.2 向上調(diào)整算法 AdJustUP
3.3 堆的創(chuàng)建
3.3.1 向上建堆
3.3.2 向下建堆
3.3.3 堆的初始化與銷毀
3.3.4 堆的插入（壓棧）
3.3.5 取堆頂?shù)臄?shù)據(jù)
3.3.6 堆的刪除
3.3.7 堆的數(shù)據(jù)個(gè)數(shù)
3.3.8 堆的判空
二、堆的完整實(shí)現(xiàn)代碼
三、完結(jié)撒?
–?–?–?–?–?–?–?–?–?–?–?–?–?–?–?-正文開始-?–?–?–?–?–?–?–?–?–?–?–?–?–?–?–
一、二叉樹的順序（堆）結(jié)構(gòu)及實(shí)現(xiàn)
1.二叉樹的順序結(jié)構(gòu)
堆
物理結(jié)構(gòu)：數(shù)組
邏輯結(jié)構(gòu)：二叉樹
順序結(jié)構(gòu)存儲就是使用數(shù)組來存儲，普通的二叉樹是不適合用數(shù)組來存儲的，因?yàn)榭赡軙嬖诖罅康目臻g浪費(fèi)，而完全二叉樹更適合使用順序結(jié)構(gòu)存儲。
可能有些同學(xué)不太清楚普通二叉樹使用數(shù)組來存儲為什么會造成空間上的浪費(fèi)，這里給大家講解一下：
我們使用數(shù)組進(jìn)行二叉樹的存儲時(shí)，父子節(jié)點(diǎn)之間需要滿足的關(guān)系為：
parent = (child+1)/2;
leftchild = parent2-1;
rightchild = parent2+2;
ps:parent指父節(jié)點(diǎn)在數(shù)組中的下標(biāo)位置，leftchild指左子節(jié)點(diǎn)在數(shù)組中的下標(biāo)位置，rightchild指右子節(jié)點(diǎn)在數(shù)組中的下標(biāo)位置
那么對于滿二叉樹和完全二叉樹，我們按照一層一層（層序）往數(shù)組中進(jìn)行存儲。
舉例如下圖所示，大家可以按照下圖簡單計(jì)算驗(yàn)證一下父子之間是否滿足父子關(guān)系：
可以知道，對于滿二叉樹和完全二叉樹進(jìn)行層序存儲在數(shù)組中，按照下標(biāo)計(jì)算都是滿足上面所述的父子關(guān)系。
而對于普通二叉樹（非滿二叉樹，非完全二叉樹），我們依然按照上面存儲進(jìn)行計(jì)算
可以發(fā)現(xiàn)不符合父子節(jié)點(diǎn)之間的關(guān)系，問題在于2節(jié)點(diǎn)的右節(jié)點(diǎn)為空，而在存儲時(shí)對于空節(jié)點(diǎn)我們并沒有在數(shù)組中進(jìn)行存儲記錄，相當(dāng)于在數(shù)組中少了一個(gè)位置，那么我們?nèi)绻芽展?jié)點(diǎn)加上，如下圖：
這樣就滿足了父子間的關(guān)系，但是對于下標(biāo)為4的位置并沒有存儲數(shù)據(jù)，就造成了空間浪費(fèi)。
所以，對于普通二叉樹我們一般使用鏈?zhǔn)浇Y(jié)構(gòu)進(jìn)行存儲，避免空間浪費(fèi)。
現(xiàn)實(shí)中我們通常把堆(一種二叉樹)使用順序結(jié)構(gòu)的數(shù)組來存儲，需要注意的是這里的堆和操作系統(tǒng)虛擬進(jìn)程地址空間中的堆是兩回事，一個(gè)是數(shù)據(jù)結(jié)構(gòu)，一個(gè)是操作系統(tǒng)中管理內(nèi)存的一塊區(qū)域分段。
2.堆的概念及結(jié)構(gòu)
如果有一個(gè)關(guān)鍵碼的集合K = {K0，K1，K2，…，Kn-1}，把它的所有元素按完全二叉樹的順序存儲方式存儲在一個(gè)一維數(shù)組中，并滿足：Ki<=K2i+1且Ki<=K2i+2(Ki>=K2i+1且Ki>=K2i+2)i = 0，1，2…，則稱為小堆(或大堆)。將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。
堆的性質(zhì)：
1.堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
2.堆總是一棵完全二叉樹;
堆的兄弟節(jié)點(diǎn)（同一父節(jié)點(diǎn)的子兩個(gè)子節(jié)點(diǎn)）之間是不論大小的，而對于小堆其父節(jié)點(diǎn)的值一定小于子節(jié)點(diǎn)，對于大堆其父節(jié)點(diǎn)的值一定大于子節(jié)點(diǎn)。
3.堆的實(shí)現(xiàn)
堆初始化結(jié)構(gòu)：
//堆初始化
void HPInit(HP* php)
{
assert(php);
php->a = NULL;
php->capacity = php->size = 0;
}
在給定一個(gè)數(shù)組去實(shí)現(xiàn)成堆之前我們需要先了解內(nèi)部實(shí)現(xiàn)的核心邏輯。
3.1 向下調(diào)整算法 AdJustDown
現(xiàn)在我們給出一個(gè)數(shù)組，邏輯上看做一顆完全二叉樹。
int arr[] = {27,15,19,18,28,34,65,49,25,37}
我們通過從根節(jié)點(diǎn)開始的向下調(diào)整算法可以把它調(diào)整成一個(gè)小堆。
向下調(diào)整算法有一個(gè)前提：左右子樹必須是一個(gè)堆，才能調(diào)整。
上面數(shù)組邏輯上的二叉樹可畫為：
可以看出來，根節(jié)點(diǎn)27影響了整體的小堆結(jié)構(gòu)，那么我們?nèi)绾螌⑵滢D(zhuǎn)變?yōu)樾《涯兀?br>
（制作不是很好大家將就著看看就行）
按照上面圖片顯示的流程，我們在邏輯上就把之前的二叉樹變成了小堆排序，而其邏輯實(shí)現(xiàn)思想就是向下調(diào)整。
向下調(diào)整：
再強(qiáng)調(diào)一邊：
向下調(diào)整算法有一個(gè)前提：左右子樹必須是一個(gè)堆，才能調(diào)整。
從根開始，比較其子節(jié)點(diǎn)的大小，如果為大堆排序就將父節(jié)點(diǎn)與子節(jié)點(diǎn)中較大的節(jié)點(diǎn)交換，如果為小堆就將父節(jié)點(diǎn)與子節(jié)點(diǎn)中較小的節(jié)點(diǎn)交換。交換完畢繼續(xù)重復(fù)以上邏輯，直到父節(jié)點(diǎn)大于子節(jié)點(diǎn)（大堆）或是父節(jié)點(diǎn)小于子節(jié)點(diǎn)（小堆）即可完成堆排序。
代碼實(shí)現(xiàn)：
void Swap(HPDataType* px, HPDataType* py)
{
HPDataType tmp = *px;
*px = *py;
*py = tmp;
}
//向下調(diào)整O(logN)
void AdJustDown(HPDataType* a, int n, int parent)
{
//從左孩子開始,child為小孩子那個(gè)
int child = parent * 2 + 1;
while (child<n)
{
if (child + 1 < n && a[child] > a[child + 1])
{
++child;
}
if (a[child] < a[parent])//小堆<,大堆>
{
Swap(&a[parent], &a[child]);
parent = child;
child = child * 2 + 1;
}
else
{
break;
}
}
}
3.2 向上調(diào)整算法 AdJustUP
在一個(gè)二叉樹的數(shù)組中如果我們尾插了一個(gè)數(shù)據(jù)，可能就導(dǎo)致結(jié)構(gòu)不再是堆。
所以我們?nèi)绻窃诂F(xiàn)有的一個(gè)堆里進(jìn)行數(shù)據(jù)尾插存儲，那么我們要保證數(shù)據(jù)插入后還是堆，這時(shí)一般使用向上調(diào)整算法。
下面我們給出一個(gè)數(shù)組，請畫出其邏輯結(jié)構(gòu)二叉樹：
int arr[] = {10,15,56,25,30,70}
二叉樹：
如果我將5尾插在數(shù)組當(dāng)中，那么就相當(dāng)于是將56節(jié)點(diǎn)的右孩子連了一個(gè)5節(jié)點(diǎn)：
這顯然已經(jīng)不是小堆了，調(diào)整邏輯如下：
這就是向上調(diào)整的整體邏輯：
如果是進(jìn)行小堆排序，將尾節(jié)點(diǎn)值與其父節(jié)點(diǎn)的值進(jìn)行比較，如果小于父節(jié)點(diǎn)就交換，如果進(jìn)行大堆，那就判斷子節(jié)點(diǎn)是否大于父節(jié)點(diǎn)，若是大于就交換。
代碼實(shí)現(xiàn)：
void Swap(HPDataType* px, HPDataType* py)
{
HPDataType tmp = *px;
*px = *py;
*py = tmp;
}
//向上調(diào)整 O(logN)
void AdJustUP(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
//while (1)嚴(yán)格來說不行
while(child>0)
{
if (a[child] < a[parent])//小堆<,大堆>
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (parent - 1) / 2;
}
else
{
break;
}
}
}
向下調(diào)整算法和向上調(diào)整算法的時(shí)間復(fù)雜度都為O（logN），大家感興趣可以算一下。
3.3 堆的創(chuàng)建
向上調(diào)整和向下調(diào)整都是基于已經(jīng)形成了堆上面，那么如果隨便給一個(gè)本就不是堆的數(shù)組，我們該如何進(jìn)行建堆呢？
3.3.1 向上建堆
下面我們給出一個(gè)數(shù)組，這個(gè)數(shù)組邏輯上可以看做一顆完全二叉樹，但是還不是一個(gè)小堆，現(xiàn)在我們通過算法，把它構(gòu)建成一個(gè)小堆。
int a[] = {5，3，6，8，2，1};
根節(jié)點(diǎn)左右子樹不是小堆，我們怎么調(diào)整呢？
這里我們從根的左孩子節(jié)點(diǎn)開始向上調(diào)整，根據(jù)數(shù)組存儲順序向后以此執(zhí)行，直到最后一個(gè)節(jié)點(diǎn)為止。
其二叉樹為：
調(diào)整邏輯：
從根節(jié)點(diǎn)的子節(jié)點(diǎn)開始，進(jìn)行向上調(diào)整，一次調(diào)整完畢將子節(jié)點(diǎn)對應(yīng)數(shù)組下標(biāo)加1進(jìn)入下一個(gè)節(jié)點(diǎn)進(jìn)行向上調(diào)整，直到除了根的所有節(jié)點(diǎn)都調(diào)整完畢，二叉樹便變成了堆。
代碼實(shí)現(xiàn)：
//向上調(diào)整 O(logN)
void AdJustUP(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
//while (1)嚴(yán)格來說不行
while(child>0)
{
if (a[child] < a[parent])//小堆<,大堆>
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (parent - 1) / 2;
}
else
{
break;
}
}
}
//初始化建堆
void HPInitArray(HP* php, HPDataType* a, int n)
{
assert(php);
php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
if (php->a == NULL)
{
perror("malloc fail");
return;
}
memcpy(php->a, a, sizeof(HPDataType) * n);
php->size = php->capacity = n;
//向上建堆 O(N*logN)
for (int i = 1; i < php->size; i++)
{
AdjustUp(php->a, i);
}
}
3.3.2 向下建堆
向下建堆就是根據(jù)向下調(diào)整的邏輯進(jìn)行。
我們把二叉樹分為其根和子樹，再把子樹分為其根和子樹，將每一個(gè)分好的子樹都進(jìn)行向下調(diào)整，直到葉子節(jié)點(diǎn)為止。
我們還拿上面數(shù)組為例：
int a[] = {5，3，6，8，2，1};
這里我們從倒數(shù)的第一個(gè)非葉子節(jié)點(diǎn)的子樹開始調(diào)整，一直調(diào)整到根節(jié)點(diǎn)的樹，就可以調(diào)整成小堆。
調(diào)整邏輯：
代碼實(shí)現(xiàn)：
//向下調(diào)整O(logN)
void AdJustDown(HPDataType* a, int n, int parent)
{
//從左孩子開始,child為小孩子那個(gè)
int child = parent * 2 + 1;
while (child<n)
{
//假設(shè)法選出左右節(jié)點(diǎn)中大/小的節(jié)點(diǎn)
if (child + 1 < n && a[child] > a[child + 1])
{
++child;
}
if (a[child] < a[parent])//小堆<,大堆>
{
Swap(&a[parent], &a[child]);
parent = child;
child = child * 2 + 1;
}
else
{
break;
}
}
}
//初始化建堆
void HPInitArray(HP* php, HPDataType* a, int n)
{
assert(php);
php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
if (php->a == NULL)
{
perror("malloc fail");
return;
}
memcpy(php->a, a, sizeof(HPDataType) * n);
php->size = php->capacity = n;
//向下建堆 O(N)
for (int i = (php->size - 1 - 1) / 2; i >= 0; i--)
{
AdJustDown(php->a, php->size, i);
}
}
向上建堆和向下建堆的時(shí)間復(fù)雜度分別為O（N*logN），O（N）。
因?yàn)橄蛳陆ǘ训臅r(shí)間復(fù)雜度小，所以我們在實(shí)際工作中進(jìn)行建堆一般是選擇向下建堆。
3.3.3 堆的初始化與銷毀
在數(shù)據(jù)結(jié)構(gòu)中，創(chuàng)建任何結(jié)構(gòu)，都需要對其進(jìn)行初始化和銷毀。
代碼實(shí)現(xiàn)：
//堆初始化
void HPInit(HP* php)
{
assert(php);
php->a = NULL;
php->capacity = php->size = 0;
}
//堆銷毀
void HPDestory(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->capacity = php->size = 0;
}
3.3.4 堆的插入（壓棧）
插入一個(gè)數(shù)到數(shù)組的尾上，再進(jìn)行向上調(diào)整算法，直到滿足堆。
代碼實(shí)現(xiàn)：
//向上調(diào)整 O(logN)
void AdJustUP(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
//while (1)嚴(yán)格來說不行
while(child>0)
{
if (a[child] < a[parent])//小堆<,大堆>
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (parent - 1) / 2;
}
else
{
break;
}
}
}
//壓棧 O(logN)
void HPPush(HP* php, HPDataType x)
{
assert(php);
//判斷空間是否足夠
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("realloc fail");
return;
}
php->a = tmp;
php->capacity = newcapacity;
}
php->a[php->size] = x;
php->size++;
//數(shù)據(jù)尾插向上調(diào)整
AdJustUP(php->a, php->size-1);
}
3.3.5 取堆頂?shù)臄?shù)據(jù)
在建好的堆中返回其根部數(shù)據(jù)。
代碼實(shí)現(xiàn)：
//返回根數(shù)據(jù)
HPDataType HPTop(HP* php)
{
assert(php);
assert(php->size);
return php->a[0];
}
3.3.6 堆的刪除
刪除堆是刪除堆頂?shù)臄?shù)據(jù)，將堆頂?shù)臄?shù)據(jù)根最后一個(gè)數(shù)據(jù)一換，然后刪除數(shù)組最后一個(gè)數(shù)據(jù)，再進(jìn)行向下調(diào)整算法。
代碼實(shí)現(xiàn)：
//向下調(diào)整O(logN)
void AdJustDown(HPDataType* a, int n, int parent)
{
//從左孩子開始,child為小孩子那個(gè)
int child = parent * 2 + 1;
while (child<n)
{
if (child + 1 < n && a[child] > a[child + 1])
{
++child;
}
if (a[child] < a[parent])//小堆<,大堆>
{
Swap(&a[parent], &a[child]);
parent = child;
child = child * 2 + 1;
}
else
{
break;
}
}
}
//刪除根數(shù)據(jù)O(logN)
void HPPop(HP* php)
{
assert(php);
assert(php->size);
//將根數(shù)據(jù)與最后一個(gè)子葉交換，再刪除最后一個(gè)數(shù)據(jù)
Swap(&php->a[0], &php->a[php->size-1]);
php->size--;
//向下調(diào)整
AdJustDown(php->a, php->size, 0);
}
3.3.7 堆的數(shù)據(jù)個(gè)數(shù)
代碼實(shí)現(xiàn)：
int HeapSize(HP* php)
{
assert(php);
return php->size;
}
3.3.8 堆的判空
代碼實(shí)現(xiàn)：
//判斷堆是否為空
bool HPEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
二、堆的完整實(shí)現(xiàn)代碼
Heap.h:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>
#include <time.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
//小堆
//堆初始化
void HPInit(HP* php);
//初始化建堆
void HPInitArray(HP* php, HPDataType* a, int n);
//堆銷毀
void HPDestory(HP* php);
//壓棧
void HPPush(HP* php, HPDataType x);
//返回根數(shù)據(jù)
HPDataType HPTop(HP* php);
//刪除根數(shù)據(jù)
void HPPop(HP* php);
//堆的數(shù)據(jù)個(gè)數(shù)
int HPSize(HP* php);
//判斷堆是否為空
bool HPEmpty(HP* php);
Heap.c:文章來源：http://www.zghlxwxcb.cn/news/detail-854123.html
#include "Heap.h"
//堆初始化
void HPInit(HP* php)
{
assert(php);
php->a = NULL;
php->capacity = php->size = 0;
}
//堆銷毀
void HPDestory(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->capacity = php->size = 0;
}
void Swap(HPDataType* px, HPDataType* py)
{
HPDataType tmp = *px;
*px = *py;
*py = tmp;
}
//向上調(diào)整 O(logN)
void AdJustUP(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
//while (1)嚴(yán)格來說不行
while(child>0)
{
if (a[child] < a[parent])//小堆<,大堆>
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (parent - 1) / 2;
}
else
{
break;
}
}
}
//壓棧 O(logN)
void HPPush(HP* php, HPDataType x)
{
assert(php);
//判斷空間是否足夠
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("realloc fail");
return;
}
php->a = tmp;
php->capacity = newcapacity;
}
php->a[php->size] = x;
php->size++;
//數(shù)據(jù)尾插向上調(diào)整
AdJustUP(php->a, php->size-1);
}
//返回根數(shù)據(jù)
HPDataType HPTop(HP* php)
{
assert(php);
assert(php->size);
return php->a[0];
}
//向下調(diào)整O(logN)
void AdJustDown(HPDataType* a, int n, int parent)
{
//從左孩子開始,child為小孩子那個(gè)
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child] > a[child + 1])
{
++child;
}
if (a[child] < a[parent])//小堆<,大堆>
{
Swap(&a[parent], &a[child]);
parent = child;
child = child * 2 + 1;
}
else
{
break;
}
}
}
//刪除根數(shù)據(jù)O(logN)
void HPPop(HP* php)
{
assert(php);
assert(php->size);
//將根數(shù)據(jù)與最后一個(gè)子葉交換，再刪除最后一個(gè)數(shù)據(jù)
Swap(&php->a[0], &php->a[php->size-1]);
php->size--;
//向下調(diào)整
AdJustDown(php->a, php->size, 0);
}
int HeapSize(HP* php)
{
assert(php);
return php->size;
}
//判斷堆是否為空
bool HPEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
//初始化建堆
void HPInitArray(HP* php, HPDataType* a, int n)
{
assert(php);
php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
if (php->a == NULL)
{
perror("malloc fail");
return;
}
memcpy(php->a, a, sizeof(HPDataType) * n);
php->size = php->capacity = n;
//向上建堆 O(N*logN)
/*for (int i = 1; i < php->size; i++)
{
AdjustUp(php->a, i);
}*/
//向下建堆 O(N)
for (int i = (php->size - 1 - 1) / 2; i >= 0; i--)
{
AdJustDown(php->a, php->size, i);
}
}
//建堆排序
//排序
// 升序
//小堆時(shí)間復(fù)雜度太大O(N^2),用大堆進(jìn)行排序O(N*logN)
//大堆
//升序 大堆 O(N*logN)
//降序 小堆 O(N*logN)
void HeapSort(HPDataType* a, int n)
{
//根據(jù)數(shù)組直接建堆 O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdJustDown(a, n, i);
}
//交換根和尾的位置，刪除尾，再向上調(diào)整 O(N*logN)
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdJustDown(a, end, 0);
--end;
}
}
三、完結(jié)撒?
如果以上內(nèi)容對你有幫助不妨點(diǎn)贊支持一下，以后還會分享更多編程知識，我們一起進(jìn)步。
最后我想講的是，據(jù)說點(diǎn)贊的都能找到漂亮女朋友?
文章來源地址http://www.zghlxwxcb.cn/news/detail-854123.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)進(jìn)階篇 之 【二叉樹順序存儲（堆）】的整體實(shí)現(xiàn)講解（賦完整實(shí)現(xiàn)代碼）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
