1、堆的概念及結(jié)構(gòu)
堆就是以二叉樹的順序存儲方式來存儲元素，同時(shí)又要滿足父親結(jié)點(diǎn)存儲數(shù)據(jù)都要大于等于兒子結(jié)點(diǎn)存儲數(shù)據(jù)（也可以是父親結(jié)點(diǎn)數(shù)據(jù)都要小于等于兒子結(jié)點(diǎn)數(shù)據(jù)）的一種數(shù)據(jù)結(jié)構(gòu)。堆只有兩種即大堆和小堆，大堆就是父親結(jié)點(diǎn)數(shù)據(jù)大于等于兒子結(jié)點(diǎn)數(shù)據(jù)，小堆則反之。
2、堆的性質(zhì)
堆中某個節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
堆總是一棵完全二叉樹。
3、堆的調(diào)整算法
3.1、向下調(diào)整算法
現(xiàn)在我們給出一個數(shù)組，邏輯上看作一棵完全二叉樹。我們通過從根節(jié)點(diǎn)開始的向下調(diào)整算法可以把它調(diào)整成一個小堆。
但是，使用向下調(diào)整算法需要滿足一個前提：
?若想將其調(diào)整為小堆，那么根結(jié)點(diǎn)的左右子樹必須都為小堆。
?若想將其調(diào)整為大堆，那么根結(jié)點(diǎn)的左右子樹必須都為大堆。
?
?
向下調(diào)整算法的基本思想（小堆）：
?1.從根結(jié)點(diǎn)處開始，選出左右孩子中值較小的孩子。
?2.讓小的孩子與其父親進(jìn)行比較。
?若小的孩子比父親還小，則該孩子與其父親的位置進(jìn)行交換。并將原來小的孩子的位置當(dāng)成父親繼續(xù)向下進(jìn)行調(diào)整，直到調(diào)整到葉子結(jié)點(diǎn)為止。
?若小的孩子比父親大，則不需處理了，調(diào)整完成，整個樹已經(jīng)是小堆了。
代碼實(shí)現(xiàn)
void Swap(HPDataType* a, HPDataType* b)
{
HPDataType tmp = *a;
*a = *b;
*b = tmp;
}
void AdjustDown(HPDataType* a, int size, int parent)
{
//1.假設(shè)左孩子為小的數(shù)據(jù)
int child = parent * 2 + 1;
while (child < size)
{
//2.如果左孩子>右孩子 則將右孩子賦值
//有可能只有左孩子 所以加條件
//以下未有左右孩子且左孩子>右孩子情況，則將child++
if (child + 1 < size && a[child] > a[child + 1])
{
child++;
}
//3.將孩子與父親進(jìn)行比較 如果孩子小則交換
//然后將父親和孩子移動到下一個位置
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
交換數(shù)值函數(shù)注意
使用堆的向下調(diào)整算法需要滿足其根結(jié)點(diǎn)的左右子樹均為大堆或是小堆才行，那么如何才能將一個任意樹調(diào)整為堆呢？
?答案很簡單，我們只需要從倒數(shù)第一個非葉子結(jié)點(diǎn)開始，從后往前，按下標(biāo)，依次作為根去向下調(diào)整即可。
?
向下調(diào)整算法的時(shí)間復(fù)雜度：
根據(jù)計(jì)算可知，向下調(diào)整算法的時(shí)間復(fù)雜度為O(N)。
3.2、向上調(diào)整算法
當(dāng)我們在一個堆的末尾插入一個數(shù)據(jù)后，需要對堆進(jìn)行調(diào)整，使其仍然是一個堆，這時(shí)需要用到堆的向上調(diào)整算法。
向上調(diào)整算法的基本思想（小堆）：
?1.將目標(biāo)結(jié)點(diǎn)與其父結(jié)點(diǎn)比較。
?2.若目標(biāo)結(jié)點(diǎn)的值比其父結(jié)點(diǎn)的值小，則交換目標(biāo)結(jié)點(diǎn)與其父結(jié)點(diǎn)的位置，并將原目標(biāo)結(jié)點(diǎn)的父結(jié)點(diǎn)當(dāng)作新的目標(biāo)結(jié)點(diǎn)繼續(xù)進(jìn)行向上調(diào)整。若目標(biāo)結(jié)點(diǎn)的值比其父結(jié)點(diǎn)的值大，則停止向上調(diào)整，此時(shí)該樹已經(jīng)是小堆了。
但是，使用向上調(diào)整算法需要滿足一個前提：
?若想將其調(diào)整為小堆，那么原來的數(shù)據(jù)為小堆。
?若想將其調(diào)整為大堆，那么原來的數(shù)據(jù)為大堆。
?
?代碼實(shí)現(xiàn)
void Swap(HPDataType* a, HPDataType* b)
{
HPDataType tmp = *a;
*a = *b;
*b = tmp;
}
void AdjustUp(HPDataType* p, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (p[parent] > p[child])
{
Swap(&p[parent], &p[child]);
child = parent;
parent = (parent - 1) / 2;
}
else
{
break;
}
}
}
向上調(diào)整算法時(shí)間復(fù)雜度
因此向上調(diào)整算法的時(shí)間復(fù)雜度為O(N*logN)。
4、堆的實(shí)現(xiàn)
實(shí)現(xiàn)一個數(shù)據(jù)結(jié)構(gòu)的第一步需要創(chuàng)建一個工程。(下圖為vs 2022)
Heap.h（堆的類型定義、接口函數(shù)聲明、引用的頭文件）
Heap.c（堆接口函數(shù)的實(shí)現(xiàn)）
test.c （主函數(shù)、測試順序表各個接口功能）
4.1、頭文件包含和結(jié)構(gòu)定義
以下是實(shí)現(xiàn)堆可能用到的頭文件。
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
堆的結(jié)構(gòu)定義
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;//存放數(shù)據(jù)的動態(tài)數(shù)組
int size; //有效數(shù)據(jù)個數(shù)
int capacity; //數(shù)組容量
}HP;
4.2、初始化
void HeapInit(HP* php)
{
assert(php);//斷言避免出現(xiàn)空指針
php->a = NULL;
php->capacity = php->size = 0;
}
4.3、銷毀
void HeapDestory(HP* php)
{
assert(php);
free(php->a);//釋放動態(tài)數(shù)組
php->size = php->capacity = 0;
}
4.4、插入數(shù)據(jù)
插入數(shù)據(jù)的同時(shí)需要保證插入之后的數(shù)據(jù)依然是堆，由于插入數(shù)據(jù)之前的所有數(shù)據(jù)是堆，可以使用向上調(diào)整數(shù)據(jù)進(jìn)行調(diào)整。
void HeapPush(HP* php, HPDataType x)
{
assert(php);
//1.檢查容量
if (php->size == php->capacity)
{
int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)*newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
php->a = tmp;
php->capacity = newCapacity;
}
//2.插入數(shù)據(jù)
php->a[php->size] = x;
php->size++;
//3.調(diào)整數(shù)據(jù)
AdjustUp(php->a, php->size-1);
}
測試
4.5、刪除數(shù)據(jù) 刪除堆頂
刪除堆頂元素，首先需要有數(shù)據(jù)，通過斷言判斷，有數(shù)據(jù)的情況下先將堆頂元素和數(shù)組尾的數(shù)據(jù)進(jìn)行交換，然后將size–，因?yàn)槌硕秧斣夭粷M足堆結(jié)構(gòu)之外，其他都滿足，所以使用向下調(diào)整數(shù)據(jù)算法。
void HeapPop(HP* php)
{
assert(php);
//有數(shù)據(jù)才刪除
assert(php->size > 0);
//1.將首位數(shù)據(jù)交換
Swap(&php->a[0], &php->a[php->size - 1]);
//2.刪除尾數(shù)據(jù)
php->size--;
//3.向下調(diào)整
AdjustDown(php->a, php->size, 0);
}
測試
4.6、獲取堆頂元素
根據(jù)堆的定義可知，堆頂元素就是數(shù)組首元素，返回首元素即可。
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
測試
4.7、獲取有效數(shù)據(jù)個數(shù)
根據(jù)堆的結(jié)構(gòu)設(shè)計(jì)，size就是堆的有效數(shù)據(jù)個數(shù)，返回size即可。
size_t HeapSize(HP* php)
{
assert(php);
return php->size;
}
測試
4.8、判斷是否為空
根據(jù)堆結(jié)構(gòu)的設(shè)計(jì)，size代表堆的有效數(shù)據(jù)個數(shù)，size等于0則為空，不等于0則不為空。
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
文章來源：http://www.zghlxwxcb.cn/news/detail-778666.html
5、代碼匯總
5.1、Heap.h
#pragma once //防止頭文件重復(fù)包含
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;//存放數(shù)據(jù)的數(shù)組
int size; //有效數(shù)據(jù)個數(shù)
int capacity; //數(shù)組容量
}HP;
//初始化
void HeapInit(HP* php);
//銷毀
void HeapDestory(HP* php);
//插入數(shù)據(jù)
void HeapPush(HP* php, HPDataType x);
//刪除數(shù)據(jù) 刪除堆頂數(shù)據(jù)
void HeapPop(HP* php);
//取堆頂元素
HPDataType HeapTop(HP* php);
//獲取有效數(shù)據(jù)個數(shù)
size_t HeapSize(HP* php);
//判斷是否為空
bool HeapEmpty(HP* php);
//兩個元素交換
void Swap(HPDataType* a, HPDataType* b);
//向上調(diào)整數(shù)據(jù) 小堆
void AdjustUp(HPDataType* p, int child);
//向下調(diào)整算法 小堆
void AdjustDown(HPDataType* a, int size, int parent);
5.2、Heap.c
#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"
//初始化 小堆
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->capacity = php->size = 0;
}
//銷毀
void HeapDestory(HP* php)
{
assert(php);
free(php->a);
php->size = php->capacity = 0;
}
void Swap(HPDataType* a, HPDataType* b)
{
HPDataType tmp = *a;
*a = *b;
*b = tmp;
}
log N
//向上調(diào)整數(shù)據(jù) 小堆
void AdjustUp(HPDataType* p, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (p[parent] > p[child])
{
Swap(&p[parent], &p[child]);
child = parent;
parent = (parent - 1) / 2;
}
else
{
break;
}
}
}
//插入數(shù)據(jù)
void HeapPush(HP* php, HPDataType x)
{
assert(php);
//1.檢查容量
if (php->size == php->capacity)
{
int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)*newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
php->a = tmp;
php->capacity = newCapacity;
}
//2.插入數(shù)據(jù)
php->a[php->size] = x;
php->size++;
//3.調(diào)整數(shù)據(jù)
AdjustUp(php->a, php->size-1);
}
//向下調(diào)整算法 小堆
void AdjustDown(HPDataType* a, int size, int parent)
{
//1.假設(shè)左孩子為小的數(shù)據(jù)
int child = parent * 2 + 1;
while (child < size)
{
//2.如果左孩子>右孩子 則將右孩子賦值
//有可能只有左孩子 所以加條件
//以下未有左右孩子且左孩子>右孩子情況，則將child++
if (child + 1 < size && a[child] > a[child + 1])
{
child++;
}
//3.將孩子與父親進(jìn)行比較 如果孩子小則交換
//然后將父親和孩子移動到下一個位置
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//刪除數(shù)據(jù) 刪除堆頂數(shù)據(jù)
void HeapPop(HP* php)
{
assert(php);
//有數(shù)據(jù)才刪除
assert(php->size > 0);
//1.將首位數(shù)據(jù)交換
Swap(&php->a[0], &php->a[php->size - 1]);
//2.刪除尾數(shù)據(jù)
php->size--;
//3.向下調(diào)整
AdjustDown(php->a, php->size, 0);
}
//取堆頂元素
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
size_t HeapSize(HP* php)
{
assert(php);
return php->size;
}
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
總結(jié)
本篇博客就結(jié)束啦，謝謝大家的觀看，如果公主少年們有好的建議可以留言喔，謝謝大家啦！文章來源地址http://www.zghlxwxcb.cn/news/detail-778666.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)第十一彈---堆的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
