? ?
??博客昵稱：博客小夢(mèng)
??最喜歡的座右銘：全神貫注的上吧?。?！
??作者簡(jiǎn)介：一名熱愛(ài)C/C++，算法等技術(shù)、喜愛(ài)運(yùn)動(dòng)、熱愛(ài)K歌、敢于追夢(mèng)的小博主！
??博主小留言：哈嘍！??各位CSDN的uu們，我是你的博客好友小夢(mèng)，希望我的文章可以給您帶來(lái)一定的幫助，話不多說(shuō)，文章推上！歡迎大家在評(píng)論區(qū)嘮嗑指正，覺(jué)得好的話別忘了一鍵三連哦！??
前言??
? ? 哈嘍各位友友們??，我今天又學(xué)到了很多有趣的知識(shí)，現(xiàn)在迫不及待的想和大家分享一下！??我僅已此文，手把手帶領(lǐng)大家追夢(mèng)之旅【數(shù)據(jù)結(jié)構(gòu)篇】——詳解小白如何使用C語(yǔ)言實(shí)現(xiàn)堆數(shù)據(jù)結(jié)構(gòu)~ 都是精華內(nèi)容，可不要錯(cuò)過(guò)喲?。?！??????
什么是堆？
堆的概念及結(jié)構(gòu)
如果有一個(gè)關(guān)鍵碼的集合K = { ， ， ，…， }，把它的所有元素按完全二叉樹(shù)的順序存儲(chǔ)方式存儲(chǔ)在一個(gè)一維數(shù)組中，并滿足：
- 父結(jié)點(diǎn)的值都大于孩子結(jié)點(diǎn)的值，則稱為大堆；
- 父結(jié)點(diǎn)的值都小于孩子結(jié)點(diǎn)的值，則稱為小堆；
大堆也稱為大根堆，小堆也叫做小根堆。
堆的性質(zhì)：
- 堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
-
堆總是一棵完全二叉樹(shù)。
堆的實(shí)現(xiàn)
堆向下調(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)整。
畫(huà)圖分析：
堆向下調(diào)整算法源代碼分享：
向下調(diào)整建小堆
//向下調(diào)整--建小堆
void AdjustDown(int* a, int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
if (child + 1 < size && a[child + 1] < a[child])
{
child++;
}
if (a[child] < a[parent])
{
Swap(&(a[parent]), &(a[child]));
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
向下調(diào)整建大堆
//建大堆
void AdjustDown(int* a, int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
if (child + 1 < size && a[child + 1] > a[child])
{
child++;
}
if (a[child] > a[parent])
{
Swap(&(a[parent]), &(a[child]));
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
堆向上調(diào)整算法源代碼分享：
畫(huà)圖分析：
向上調(diào)整建小堆
void AdjustUp(HPDataType* a, int child)
{
assert(a);
while (child > 0)
{
int parent = (child - 1) / 2;
if (a[child] < a[parent])
{
Swap(&(a[child]), &(a[parent]));
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
向上調(diào)整建大堆
//向上調(diào)整建大堆
void AdjustUp(HPDataType* a, int child)
{
assert(a);
while (child > 0)
{
int parent = (child - 1) / 2;
if (a[child] > a[parent])
{
Swap(&(a[child]), &(a[parent]));
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
C語(yǔ)言整體實(shí)現(xiàn)堆數(shù)據(jù)結(jié)構(gòu)源代碼分享
堆的插入：
先插入一個(gè)10到數(shù)組的尾上，再進(jìn)行向上調(diào)整算法，直到滿足堆。
void HeapPush(HP* php, HPDataType x)
{
assert(php);
//擴(kuò)容
if (php->capacity == php->size)
{
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tem = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
if (tem == NULL)
{
printf("realloc fail\n");
exit(-1);
}
php->a = tem;
php->capacity = newcapacity;
}
php->a[php->size] = x;
//向上調(diào)整--建小堆
if(php->size > 0)
AdjustUp(php->a, php->size);
php->size++;
}
堆的刪除：
刪除堆是刪除堆頂?shù)臄?shù)據(jù)，將堆頂?shù)臄?shù)據(jù)和最后一個(gè)數(shù)據(jù)一換，然后刪除數(shù)組最后一個(gè)數(shù)據(jù)，再進(jìn)行向下調(diào)整算法。
畫(huà)圖分析：
void HeapPop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
Swap(&(php->a[0]), &(php->a[php->size - 1]));
php->size--;
AdjustDwon(php->a, php->size,0);
}
頭文件(Heap.h)編寫：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
void Swap(HPDataType* p1, HPDataType* p2);
// O(logN)
void AdjustDwon(HPDataType* a, int size, int parent);
void AdjustUp(HPDataType* a, int child);
void HeapPrint(HP* php);
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);
功能文件（Heap.c）編寫：
#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void Swap(HPDataType* p1, HPDataType* p2)
{
int tem = *p1;
*p1 = *p2;
*p2 = tem;
}
// O(logN)
//建小堆
void AdjustDwon(HPDataType* a, int size, int parent)
{
assert(a);
int child = parent * 2 + 1;
while (child < size)
{
//選出最小的那個(gè)
if (child + 1 < size && a[child + 1] < a[child])
{
child++;
}
if (a[child] < a[parent] )
{
Swap(&(a[parent]), &(a[child]));
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void AdjustUp(HPDataType* a, int child)
{
assert(a);
while (child > 0)
{
int parent = (child - 1) / 2;
if (a[child] < a[parent])
{
Swap(&(a[child]), &(a[parent]));
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void HeapPrint(HP* php)
{
assert(php);
for (int i = 0; i < php->size; i++)
{
printf("%d ", php->a[i]);
}
printf("\n");
}
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->capacity = php->size = 0;
}
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->capacity = php->size = 0;
}
void HeapPush(HP* php, HPDataType x)
{
assert(php);
//擴(kuò)容
if (php->capacity == php->size)
{
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tem = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
if (tem == NULL)
{
printf("realloc fail\n");
exit(-1);
}
php->a = tem;
php->capacity = newcapacity;
}
php->a[php->size] = x;
//向上調(diào)整--建小堆
if(php->size > 0)
AdjustUp(php->a, php->size);
php->size++;
}
void HeapPop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
Swap(&(php->a[0]), &(php->a[php->size - 1]));
php->size--;
AdjustDwon(php->a, php->size,0);
}
HPDataType HeapTop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
return php->a[0];
}
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
int HeapSize(HP* php)
{
assert(php);
return php->size;
}
測(cè)試文件（test.c）編寫：
#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void HeapTest1()
{
HP h;
HeapInit(&h);
HeapPush(&h, 15);
HeapPush(&h, 18);
HeapPush(&h, 19);
HeapPush(&h, 25);
HeapPush(&h, 28);
HeapPush(&h, 34);
HeapPush(&h, 65);
HeapPush(&h, 49);
HeapPush(&h, 27);
HeapPush(&h, 37);
HeapPush(&h, 10);
printf("%d\n", HeapSize(&h));
HeapPrint(&h);
for (int i = 0; i < 8; i++)
{
printf("%d ", HeapTop(&h));
HeapPop(&h);
}
printf("\n");
HeapDestroy(&h);
printf("%d ", HeapTop(&h));
HeapPop(&h);
}
int main()
{
HeapTest1();
return 0;
}
運(yùn)行結(jié)果測(cè)試截圖：
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-416574.html
總結(jié)撒花??
? ?本篇文章旨在分享詳解小白如何使用C語(yǔ)言實(shí)現(xiàn)堆數(shù)據(jù)結(jié)構(gòu)。希望大家通過(guò)閱讀此文有所收獲！
? ???如果我寫的有什么不好之處，請(qǐng)?jiān)谖恼孪路浇o出你寶貴的意見(jiàn)??。如果覺(jué)得我寫的好的話請(qǐng)點(diǎn)個(gè)贊贊和關(guān)注哦~??????文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-416574.html
到了這里，關(guān)于追夢(mèng)之旅【數(shù)據(jù)結(jié)構(gòu)篇】——詳解小白如何使用C語(yǔ)言實(shí)現(xiàn)堆數(shù)據(jù)結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
