一.前言

前面我們講解了二叉樹(shù)的概念以及二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)：https://blog.csdn.net/yiqingaa/article/details/139224974?spm=1001.2014.3001.5502

今天我們主要講講二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，以及堆的實(shí)現(xiàn)。

二.正文

1.二叉樹(shù)的順序結(jié)構(gòu)及實(shí)現(xiàn)

1.1二叉樹(shù)的順序結(jié)構(gòu)

?普通的二叉樹(shù)是不適合用數(shù)組來(lái)存儲(chǔ)的，因?yàn)榭赡軙?huì)存在大量的空間浪費(fèi)。而完全二叉樹(shù)更適合使用順序結(jié)構(gòu)存儲(chǔ)。現(xiàn)實(shí)中我們通常把堆(一種二叉樹(shù))使用順序結(jié)構(gòu)的數(shù)組來(lái)存儲(chǔ)，需要注意的是這里的堆和操作系統(tǒng)虛擬進(jìn)程地址空間中的堆是兩回事，一個(gè)是數(shù)據(jù)結(jié)構(gòu)，一個(gè)是操作系統(tǒng)中管理內(nèi)存的一塊區(qū)域分段。

1.2堆的概念及結(jié)構(gòu)

如果有一個(gè)關(guān)鍵碼的集合K?=?{ k?，k?，k? ，…，k_(n-1)(注意：_()在這里表示（）里是下標(biāo) ，如我們這里表示的是k的下標(biāo)是n-1}，把它的所有元素按完全二叉樹(shù)的順序存儲(chǔ)方式存儲(chǔ)在一個(gè)一維數(shù)組中，并滿足：K_(i)?<=K_(2*i+1) 且K_(i)?<=K_(2*i+2)?(K_(i)?>=K_(2*i+1) 且 K_(i)>=K_(2*i+2) )?i?=?0，1，2…，則稱為小堆(或大堆)。將根結(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根結(jié)點(diǎn)最小的堆叫做最小堆或小根堆。

堆的性質(zhì)：

1. 堆中某個(gè)結(jié)點(diǎn)的值總是不大于或不小于其父結(jié)點(diǎn)的值。
2. 堆總是一棵完全二叉樹(shù)。

值得注意的是：這里我們雖然把它想像成樹(shù)的形狀，但其實(shí)我們的底層是數(shù)組，我們是通過(guò)改變數(shù)組，來(lái)控制這棵“樹(shù)”的。

打個(gè)比方來(lái)說(shuō)：螞蟻上樹(shù)這道菜，這盤(pán)菜里面真的有螞蟻嗎？其實(shí)沒(méi)有，只不過(guò)是人為想像成的而已。在這里的二叉樹(shù)也是同樣的道理。

?2.堆的實(shí)現(xiàn)

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

現(xiàn)在我們給出一個(gè)數(shù)組，邏輯上看做一顆完全二叉樹(shù)。我們通過(guò)從根結(jié)點(diǎn)開(kāi)始的向下調(diào)整算法可以把它調(diào)整成一個(gè)小堆。向下調(diào)整算法有一個(gè)前提：左右子樹(shù)必須是一個(gè)堆，才能調(diào)整。

這里我們給了一個(gè)數(shù)組。

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

//向下調(diào)整算法
void AdjustDown(HPDataType* php,int n ,int parent )//php是數(shù)組指針
{int child = parent * 2 + 1;if (php[child] > php[child + 1])child = parent * 2 + 2;while (child < n){if (php[child] < php[parent]){Swap(&(php[child]), &(php[parent]));parent = child;child = parent * 2 + 1;}else{break;}}
}

2.2向上調(diào)整算法

?現(xiàn)在我們給出一個(gè)數(shù)組，邏輯上看做一顆完全二叉樹(shù)。我們通過(guò)從根結(jié)點(diǎn)開(kāi)始的向上調(diào)整算法可以把它調(diào)整成一個(gè)小堆。

我們給出了一個(gè)數(shù)組：

int?array[]?=?{15,18,19,25,28,34,65,49,27,37，2};

void AdjustUp(HPDataType* php,int child)//向上調(diào)整算法
{int parent = (child - 1) / 2;while (child > 0){if (php[child] < php[parent]){Swap(&(php[child]), &(php[parent]));child = parent;parent = (child - 1) / 2;}else{break;}}
}

2.3堆的插入

先插入一個(gè)10到數(shù)組的尾上，再進(jìn)行向上調(diào)整算法，直到滿足堆。

void HPPush(HP* ps,HPDataType x)//堆尾插入數(shù)據(jù)，ps是我們堆指針
{assert(ps);if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4: ps->capacity * 2;HPDataType* arr = (HPDataType*)realloc(ps->a,sizeof(HPDataType) * newcapacity);if (arr == NULL){perror("realloc false");return;}ps->a = arr;ps->capacity = newcapacity;}ps->a[ps->size] = x;ps->size++;AdjustUp(ps->a,ps->size-1);
}

2.4堆的刪除?

刪除堆是刪除堆頂?shù)臄?shù)據(jù)，將堆頂?shù)臄?shù)據(jù)根最后一個(gè)數(shù)據(jù)一換，然后刪除數(shù)組最后一個(gè)數(shù)據(jù)，再進(jìn)行向下調(diào)整算法。

void HPPop(HP* ps)//刪除堆頂數(shù)據(jù)
{assert(ps);assert(ps->size > 0);Swap(&(ps->a[0]), &(ps->a[ps->size - 1]));ps->size--;AdjustDown(ps->a,ps->size,0);
}

3.堆代碼的實(shí)現(xiàn)

Heap.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDataType;
struct Heap
{HPDataType* a;int size;int capacity;
};
typedef struct Heap HP;
void HPInit(HP* ps);//堆的初始化
void HPDestroy(HP* ps);//堆的刪除void HPPush(HP* ps, HPDataType x);//堆尾插入數(shù)據(jù)
void HPPop(HP* ps);//刪除堆頂數(shù)據(jù)HPDataType HPTop(HP* ps);//取出堆頂數(shù)據(jù)
bool HPEmpty(HP* ps);//判斷堆是否為空void Swap(HPDataType* a, HPDataType* b);//交換兩個(gè)數(shù)據(jù)
void AdjustUp(HPDataType* php, int child);//向上調(diào)整算法
void AdjustDown(HPDataType* php, int n, int parent);//向下調(diào)整算法
int HPSize(HP* ps);//返回堆的有效數(shù)據(jù)個(gè)數(shù)
void HPSort(HPDataType* php, int n);//堆排序

Heap.c?

#include"Heap.h"
void HPInit(HP* ps)//堆初始化實(shí)現(xiàn)
{assert(ps);ps->a = NULL;ps->size = ps->capacity = 0;}void HPDestroy(HP* ps)//堆銷(xiāo)毀實(shí)現(xiàn)
{assert(ps);free(ps->a);ps->a = NULL;ps->size = ps->capacity = 0;
}void Swap(HPDataType* a,HPDataType* b)//兩個(gè)數(shù)據(jù)的交換
{HPDataType tmp =*a;*a = *b;*b = tmp;
}void AdjustUp(HPDataType* php,int child)//向上調(diào)整算法
{int parent = (child - 1) / 2;while (child > 0){if (php[child] < php[parent]){Swap(&(php[child]), &(php[parent]));child = parent;parent = (child - 1) / 2;}else{break;}}
}void HPPush(HP* ps,HPDataType x)//堆尾插入數(shù)據(jù)
{assert(ps);if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4: ps->capacity * 2;HPDataType* arr = (HPDataType*)realloc(ps->a,sizeof(HPDataType) * newcapacity);if (arr == NULL){perror("realloc false");return;}ps->a = arr;ps->capacity = newcapacity;}ps->a[ps->size] = x;ps->size++;AdjustUp(ps->a,ps->size-1);
}
void AdjustDown(HPDataType* php,int n ,int parent )//向下調(diào)整算法
{int child = parent * 2 + 1;if (php[child] > php[child + 1])child = parent * 2 + 2;while (child < n){if (php[child] < php[parent]){Swap(&(php[child]), &(php[parent]));parent = child;child = parent * 2 + 1;}else{break;}}
}
void HPPop(HP* ps)//刪除堆頂數(shù)據(jù)
{assert(ps);assert(ps->size > 0);Swap(&(ps->a[0]), &(ps->a[ps->size - 1]));ps->size--;AdjustDown(ps->a,ps->size,0);
}
bool HPEmpty(HP* ps)//判斷堆是否為空
{assert(ps);if (ps->size == 0){return true;}return false;
}
HPDataType HPTop(HP* ps)//取出堆頂數(shù)據(jù)
{assert(ps);assert(ps->size > 0);return ps->a[0];
}
HPDataType HPSize(HP* ps)//返回堆有效數(shù)據(jù)個(gè)數(shù)
{assert(ps);return ps->size;
}
void HPSort(HPDataType* php,int n)//堆排序
{//降序 建小堆//升序 建大堆//建堆的第一種方法/*for (int i = 1; i < n; i++){AdjustUp(php, i);}*///建堆的第二種方法：for (int i = (n - 1 - 1) / 2; i < n; i++)//(n-1-1)/2是為了找最后一個(gè)數(shù)據(jù)的父親{AdjustDown(php, n, i);}int end = n - 1;while (end > 0){Swap(&(php[0]), &(php[end]));AdjustDown(php, end, 0);end--;}
}

test.c?

#include"Heap.h"
void test01()
{HP hp;HPInit(&hp);HPPush(&hp, 6);HPPush(&hp, 2);HPPush(&hp, 3);HPPush(&hp, 4);HPPush(&hp, 10);HPPush(&hp, 9);HPPush(&hp, 7);HPPop(&hp);printf("%d\n", HPTop(&hp));printf("%d\n", HPSize(&hp));
//	HPDestroy(&hp);
}
void test02()
{int arr[] = { 1,2,6,4,5,8,9,7 };HPSort(&arr,sizeof(arr)/sizeof(int));
}
int main()
{//test01();test02();return 0;
}

值得注意的是test.c是本人為了測(cè)試各函數(shù)是否正常而寫(xiě)出來(lái)的。

三.結(jié)言

?堆的分享就到這了。覺(jué)得對(duì)自己有幫助的同學(xué)，可不可以給個(gè)三連。

好啦，同學(xué)們我們下期再見(jiàn)，拜拜嘍。