一、前言：二叉樹的順序結(jié)構(gòu)
普通的二叉樹是不適合用數(shù)組來存儲的，因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結(jié)構(gòu)存儲。
?
現(xiàn)實中我們通常把堆(一種二叉樹)使用順序結(jié)構(gòu)的數(shù)組來存儲，需要注意的是這里的堆和操作系統(tǒng)虛擬進程地址空間中的堆是兩回事，一個是數(shù)據(jù)結(jié)構(gòu)，一個是操作系統(tǒng)中管理內(nèi)存的一塊區(qū)域分段。
二、堆的概念及結(jié)構(gòu)
堆是一種特殊的數(shù)據(jù)結(jié)構(gòu),可以將堆分為大頂堆和小頂堆兩種形式。堆中的每個節(jié)點都有一個值，并且滿足以下兩個條件：
?
①：堆的父節(jié)點的值總是大于或等于其子節(jié)點的值（大頂堆）或者小于或等于其子節(jié)點的值（小頂堆）。
②：堆是完全二叉樹，即除了最底層外，其他層的節(jié)點都是滿的，并且最底層的節(jié)點都盡量靠左排列。
大(小)堆示意圖：
三、堆的實現(xiàn)（本篇博客以實現(xiàn)小堆為例）
3.1 準備工作
由于堆是通過數(shù)組來實現(xiàn)的，所以我們也和順序表一樣，首先要創(chuàng)建一個結(jié)構(gòu)體來存儲：數(shù)組指針 + 容量 + 存儲數(shù)據(jù)大小。
代碼實現(xiàn)：
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;//數(shù)組指針
int size;//存儲數(shù)據(jù)大小
int capacity;//容量
}HP;
3.2 初始化
初始化有兩種方式：
①:初始化時為數(shù)組開辟一定大小空間。②：直接將數(shù)組指針置為NULL，插入數(shù)據(jù)過程中在進一步處理。（本篇博客采用第二種）
代碼實現(xiàn)：
void HPInit(HP* php)
{
assert(php);
php->a = NULL;
php->capacity = 0;
php->size = 0;
}
3.3 堆的插入
【代碼思路】：
①：在插入數(shù)據(jù)前，我們首先要判斷是否要擴容的問題。由于前面初始化時我們直接置空，所以我們先判斷容量是否為空。如果為空開4個空間，否則空間擴大到原來的2倍。（為空時，第一次具體開辟多少空間讀者可自行選擇，本篇博客開4）
②：接下來就是插入數(shù)據(jù)了！但有一個問題，直接插入數(shù)據(jù)可能會破壞堆的結(jié)構(gòu)，所以我們采用了向上調(diào)整算法。
代碼：
void HPPush(HP* php, HPDataType x)
{
assert(php);
//擴容
if (php->size == php->capacity)
{
int newcapacity = php->size == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newcapacity);
if (tmp == NULL)
{
perror("malloc fail");
exit(-1);
}
php->a = tmp;
php->capacity = newcapacity;
}
//插入數(shù)據(jù)
php->a[php->size] = x;
php->size++;
//向上調(diào)整
AdjustUp(php->a, php->size - 1);
}
3.3.1 向上調(diào)整算法
【代碼思路】：由于插入數(shù)據(jù)時，影響的只是插入數(shù)據(jù)到根節(jié)點間的關(guān)系。所以我們只需將插入數(shù)據(jù)通過雙親節(jié)點調(diào)到合適位置即可。
?
Tips:父節(jié)點和子節(jié)點關(guān)系
- leftchild = parent *2 + 1
- rightchild = parent * 2 + 2
- parent = (child - 1)/2
代碼：
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void AdjustUp(HPDataType* a, int child)
{
assert(a);
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;
}
}
}
3.4 堆的刪除
【代碼思路】：堆的刪除默認是頭刪。刪除有兩種思路：
?
①：將根節(jié)點刪除，再將其余數(shù)據(jù)全部向前移動。但這樣做會造成一個問題：挪動覆蓋導(dǎo)致父子節(jié)點的關(guān)系全亂了，需要重新建堆。為了刪個數(shù)據(jù)，重新建堆，得不償失，所以我們采用下面這種方法。
?
②:將堆頂?shù)?數(shù)據(jù)和最后一個數(shù)據(jù)交換，在刪除最后一個數(shù)據(jù)。堆頂數(shù)據(jù)在通過向下調(diào)整算法調(diào)到合適位置即可。
代碼：
void HPPop(HP* php)
{
assert(php);
assert(!HPEmpty(php));//非空，還有數(shù)據(jù)可刪。該接口后面實現(xiàn)
Swap(&php->a[0], &php->a[php->size - 1]);//交換
php->size--;//刪除
//向下調(diào)整
AdjustDown(php->a, php->size, 0);
}
3.4.1 向下調(diào)整算法
【代碼思路】：向下調(diào)整算法有一個前提：左右子樹必須是一個堆，才能調(diào)整。同時還要注意是調(diào)大堆還是小堆。
調(diào)小堆：堆頂元素和孩子中最小的節(jié)點比較，如果父節(jié)點大于較小的子節(jié)點子，兩者交換。不斷向下調(diào)整到合適位置。（調(diào)大堆，和較大孩子比較）
代碼：
//這里博主在多說一句，為什么向下調(diào)整算法不直接傳結(jié)構(gòu)體指針，
//而是分別傳數(shù)組指針和數(shù)據(jù)大小呢？
//這里是博主有意為之的，目的在于讓向下調(diào)整算法通用性更強，在做其他題時，也可以直接調(diào)用此接口
void AdjustDown(HPDataType* a, int n, int parent)
{
assert(a);
int child = parent * 2 + 1;//假設(shè)左孩子更小
while (child < n)
{
//如果右孩子存在，且右孩子更小，則左孩子加1移到右孩子
if ((child + 1) < n && a[child] > a[child + 1])
{
child++;
}
if (a[parent] > a[child])//交換
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
//父節(jié)點小于較小的子節(jié)點，說明已經(jīng)調(diào)到合適位置，此時break跳出
break;
}
}
}
3.5 堆的判空（接下的過于簡單直接給出代碼）
bool HPEmpty(HP* php)
{
return php->size == 0;
}
3.6 取堆頂?shù)臄?shù)據(jù)
assert(php);
assert(!HPEmpty(php));//斷言堆中還有元素
return php->a[0];
3.7 堆的個數(shù)
int HPSize(HP* php)
{
assert(php);
return php->size;
}
3.8 堆的銷毀
void HPDestory(HP* php)
{
assert(php);
php->a = NULL;
php->capacity = php->size = 0;
}
四、所有代碼
Heap.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
void HPInit(HP* php);//初始化
void HPPush(HP* php, HPDataType x);//插入數(shù)據(jù)
void HPPop(HP* php);//刪除數(shù)據(jù)
int HPTop(HP* php);//堆頂元素
bool HPEmpty(HP* php);//判空
int HPSize(HP* php);//數(shù)據(jù)個數(shù)
void HPDestory(HP* php);//銷毀
Heap.c文章來源：http://www.zghlxwxcb.cn/news/detail-663669.html
#include "Heap.h"
void HPInit(HP* php)
{
assert(php);
php->a = NULL;
php->capacity = 0;
php->size = 0;
}
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void AdjustUp(HPDataType* a, int child)
{
assert(a);
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)
{
assert(a);
int child = parent * 2 + 1;
while (child < n)
{
if ((child + 1) < n && a[child] > a[child + 1])
{
child++;
}
if (a[parent] > a[child])
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HPPush(HP* php, HPDataType x)
{
assert(php);
//擴容
if (php->size == php->capacity)
{
int newcapacity = php->size == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newcapacity);
if (tmp == NULL)
{
perror("malloc fail");
exit(-1);
}
php->a = tmp;
php->capacity = newcapacity;
}
php->a[php->size] = x;
php->size++;
//向上調(diào)整
AdjustUp(php->a, php->size - 1);
}
bool HPEmpty(HP* php)
{
return php->size == 0;
}
void HPPop(HP* php)
{
assert(php);
assert(!HPEmpty(php));
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
//向下調(diào)整
AdjustDown(php->a, php->size, 0);
}
int HPTop(HP* php)
{
assert(php);
assert(!HPEmpty(php));
return php->a[0];
}
int HPSize(HP* php)
{
assert(php);
return php->size;
}
void HPDestory(HP* php)
{
assert(php);
php->a = NULL;
php->capacity = php->size = 0;
}
文章來源地址http://www.zghlxwxcb.cn/news/detail-663669.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)入門指南】二叉樹順序結(jié)構(gòu): 堆及實現(xiàn)（全程配圖，非常經(jīng)典）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
