C語(yǔ)言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)堆
“竹杖芒鞋輕勝馬，誰(shuí)怕？一蓑煙雨任平生”
C語(yǔ)言朱武大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)專(zhuān)欄
C語(yǔ)言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)快速排序圖文示例
C語(yǔ)言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)希爾排序算法
C語(yǔ)言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)堆排序圖文示例
C語(yǔ)言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)遞歸
前言
此篇詳細(xì)實(shí)現(xiàn)二叉樹(shù)中的一個(gè)順序結(jié)構(gòu)的實(shí)現(xiàn)——堆。并實(shí)現(xiàn)堆排序重點(diǎn)是堆的規(guī)律和堆的實(shí)現(xiàn)
堆的概念
堆：將一些元素按完全二叉樹(shù)的順序存儲(chǔ)方式存儲(chǔ)在一個(gè)一維數(shù)組中。這就是堆。完全二叉樹(shù)：通俗講就是只有最后一層的節(jié)點(diǎn)可以滿(mǎn)，也可以不滿(mǎn)。但是最后一層之前的節(jié)點(diǎn)要滿(mǎn)，這就叫做完全二叉樹(shù)。
小堆大堆：將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。（必須滿(mǎn)足堆的性質(zhì)）
堆的性質(zhì)：
1.堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值
2.堆總是一棵完全二叉樹(shù)。
注意：
1.普通的二叉樹(shù)是不適合用數(shù)組來(lái)存儲(chǔ)的，因?yàn)榭赡軙?huì)存在大量的空間浪費(fèi)。而完全二叉樹(shù)更適合使用順序結(jié)構(gòu)存儲(chǔ)。
2.現(xiàn)實(shí)中我們通常把堆(一種特殊的二叉樹(shù))使用順序結(jié)構(gòu)的數(shù)組來(lái)存儲(chǔ)。
3.需要注意的是這里的堆和操作系統(tǒng)虛擬進(jìn)程地址空間中的堆是兩回事，一個(gè)是數(shù)據(jù)結(jié)構(gòu)，一個(gè)是操作系統(tǒng)中管理內(nèi)存的一塊區(qū)域分段。
接下來(lái)我們用純C實(shí)現(xiàn)小堆
創(chuàng)建結(jié)構(gòu)體
因?yàn)橥耆鏄?shù)更適合使用順序結(jié)構(gòu)存儲(chǔ)。而堆就是完全二叉樹(shù)，所以我們需要?jiǎng)?chuàng)建順序表
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;//a指向只一個(gè)堆數(shù)組
size_t size;//記錄堆的大小
size_t capacity;//堆的最大容量
}HP;
初始化結(jié)構(gòu)體
這一步必須要有，相當(dāng)于創(chuàng)建變量了。
//初始化結(jié)構(gòu)體
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = 0;
php->capacity = 0;
}
銷(xiāo)毀結(jié)構(gòu)體
因?yàn)槭莿?dòng)態(tài)版的順序表，有動(dòng)態(tài)開(kāi)辟就需要?jiǎng)討B(tài)內(nèi)存釋放，也就是free掉a所指向的空間。
//銷(xiāo)毀結(jié)構(gòu)體
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
//free掉及時(shí)置空，防止野指針
php->a = NULL;
php->size = 0;
php->capacity = 0;
}
向堆中插入數(shù)據(jù)
在插入數(shù)據(jù)之前，我們需要先知道堆的一個(gè)技巧。
1.堆的物理結(jié)構(gòu)和邏輯結(jié)構(gòu)
前面的步驟打造了一個(gè)堆的輪廓，你說(shuō)它是堆吧，其實(shí)本質(zhì)就是一個(gè)物理結(jié)構(gòu)在內(nèi)存中連續(xù)的順序表罷了。也就是數(shù)組。如圖下標(biāo)從0開(kāi)始。
但是要用到它的邏輯結(jié)構(gòu)，需要把它想象成一個(gè)完全二叉樹(shù)，就是下面圖片這個(gè)樣子。
好了，現(xiàn)在我們要向堆中插入數(shù)據(jù)了，因?yàn)轫樞虮砦膊逍矢逴(1),且尾插不會(huì)大幅度改變堆的結(jié)構(gòu)。所以插入數(shù)據(jù)指的是尾插。
2.完全二叉樹(shù)下標(biāo)規(guī)律
注意：
1.尾插注意的是size的大小，size一直指向的是即將插入的那個(gè)空間。
2.和順序表唯一不同的是尾插后需要向上調(diào)整數(shù)據(jù)，保持小堆的從上往下依次增大的結(jié)構(gòu)
3.堆中的下標(biāo)是有規(guī)律的。規(guī)律公式如下
這里需要強(qiáng)調(diào)的是對(duì)于父親下標(biāo)的計(jì)算。父親的下標(biāo)計(jì)算公式為：parent = (child - 1) / 2;舉個(gè)例子。因?yàn)榧偃缱笞訕?shù)是7，右子樹(shù)是8。7-1初以2是3, 但8-1初以2是3.5。但是計(jì)算機(jī)計(jì)算的結(jié)果也是3。
結(jié)論：所以管他是左子樹(shù)，還是右子樹(shù)，都能計(jì)算出其父親的下標(biāo)。
3.插入數(shù)據(jù)思路
最重要的思路是向上調(diào)整思想
我們以向堆中插入一個(gè)8為例。
因?yàn)閟ize指向的是順序表中即將插入的位置，所以直接插入就好了，但要及時(shí)讓size++。
注意：尾插后size還需要指向下一個(gè)即將插入的位置。如圖
然后開(kāi)始向上調(diào)整8的位置。
思路：
1.讓child依次和其parent比較，假如child小的話(huà)就交換兩者的數(shù)據(jù)，使child的值依次向上走。然后迭代執(zhí)行child = parent;parent = (child - 1) / 2;用來(lái)迭代parent和child的位置，直到child等于0。結(jié)束循環(huán)。
2.我覺(jué)得思路不難，難在把思路轉(zhuǎn)換為代碼然后實(shí)現(xiàn)。
3.注意實(shí)參傳遞的實(shí)參分別是數(shù)組首元素的地址，和新插入元素的下標(biāo)。
//交換
void HeapSwap(HPDataType* pa, HPDataType* pb)
{
HPDataType tmp = *pa;
*pa = *pb;
*pb = tmp;
}
//向上調(diào)整
void AdjustUp(HPDataType* a, size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] < a[parent])
{
//因?yàn)樾枰啻斡玫浇粨Q算法，所以寫(xiě)成一個(gè)函數(shù)，方便調(diào)用。
HeapSwap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//插入堆
void HeapPush(HP* php, HPDataType x)
{
assert(php);
//除了AdjustUp
if (php->size == php->capacity)
{
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
//注意realloc的用法
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)* newcapacity);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
php->a = tmp;
php->capacity = newcapacity;
}
php->a[php->size] = x;
++php->size;
//唯一不同于順序表的地方，向上調(diào)整算法
AdjustUp(php->a, php->size - 1);
}
依次打印堆的值
插入堆后，為了可視化，我們還是打印一下看看效果。
void HeapPrint(HP* php)
{
assert(php);
for (size_t i = 0; i < php->size; ++i)
{
printf("%d ", php->a[i]);
}
printf("\n");
}
刪除堆頂?shù)闹?/h2>
刪除也是一門(mén)藝術(shù)。今天的我是站在巨人的肩膀上學(xué)習(xí)堆的刪除。
大佬們的算法思路是：
1.先讓堆頂?shù)闹岛投盐驳闹到粨QO(1)，然后刪除O(1)交換后堆尾的值。
2.再使用向下調(diào)整O(logN)算法，先比較left和right哪個(gè)小，誰(shuí)小就讓parent和誰(shuí)交換，然后依次迭代，使堆頂?shù)闹迪蛳抡{(diào)整。直到child大于size結(jié)束循環(huán)。
因?yàn)檫@樣的時(shí)間復(fù)雜度是相當(dāng)牛的。
注意：這里有幾個(gè)地方代碼技巧非常絕。
1.假設(shè)左子樹(shù)就是最小的值。然后比較左右子樹(shù)的大小后進(jìn)行調(diào)整到底誰(shuí)是最小的就OK了。這是非常的絕。因?yàn)槟阈枰P(guān)注到底是左子樹(shù)小還是右子樹(shù)??！
//非常絕的一個(gè)思路
if (child+1 < size &&
a[child + 1] < a[child])
{
++child;
}
刪除代碼如下。
//向下調(diào)整
AdjustDown(HPDataType* a,size_t size, size_t root)
{
size_t parent= root;
size_t child= parent * 2 + 1;
while (child < size)
{
//判斷哪個(gè)孩子小。
if (child+1 < size && a[child + 1] < a[child])
{
++child;
}
//交換父親和孩子的值
if (a[child] < a[parent])
{
HeapSwap(&a[parent], &a[child]);
//迭代
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//刪除堆頂?shù)闹?
void HeapPop(HP* php)
{
assert(php);
assert(php->size > 0);
//交換堆頂和堆尾的值。然后刪除堆尾的值
HeapSwap(php->a, &php->a[php->size - 1]);
--php->size;
//向下調(diào)整
AdjustDown(php->a, php->size, 0);
}
判斷堆是否為空
當(dāng)size為0時(shí)，堆即為空。
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
求堆中有幾個(gè)元素
size標(biāo)記的就是有幾個(gè)元素。
//求堆中有幾個(gè)元素
size_t HeapSize(HP* php)
{
assert(php);
return php->size;
}
得到堆頂?shù)闹?/h2>
需要注意的是size最少為1.當(dāng)size為0時(shí)，就意味著堆已經(jīng)為空。所以我們需要assert斷言size不為0.
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
堆排序
堆排序即利用堆的思想來(lái)進(jìn)行排序，總共分為兩個(gè)步驟：
建堆
升序：建大堆
降序：建小堆（我們這里用的是建小堆）利用堆刪除思想來(lái)進(jìn)行排序
void HeapSort(HPDataType* a, int size)
{
HP hp;
HeapInit(&hp);
//先創(chuàng)建一個(gè)小堆
for (int i = 0; i < size; i++)
{
HeapPush(&hp, a[i]);
}
size_t j = 0;
//利用堆刪除思想來(lái)進(jìn)行排序
while (!HeapEmpty(&hp))
{
a[j] = HeapTop(&hp);
j++;
HeapPop(&hp);
}
HeapDestroy(&hp);
}
int main()
{
//對(duì)a數(shù)組進(jìn)行排序
int a[] = { 4,2,7,8,5,1,0,6 };
HeapSort(a, sizeof(a) / sizeof(int));
for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
{
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
時(shí)間復(fù)雜度分析：
時(shí)間復(fù)雜度為O(N*logN)。比冒泡排序上升了一個(gè)檔次哦。
但是空間復(fù)雜度有待改進(jìn)。
但是空間復(fù)雜度因?yàn)檎加昧艘粋€(gè)數(shù)組所以是O(N)。
空間復(fù)雜度改進(jìn)的話(huà)需要很多字來(lái)詳解。下篇博文繼續(xù)敘述。
總體代碼
Heap.h
#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
size_t size;
size_t capacity;
}HP;
//初始化結(jié)構(gòu)體
void HeapInit(HP* php);
//銷(xiāo)毀結(jié)構(gòu)體
void HeapDestroy(HP* php);
//向堆里插入數(shù)據(jù)
void HeapPush(HP* php, HPDataType x);
//交換堆中父子
void HeapSwap(HPDataType* pa, HPDataType* pb);
//刪除堆頂數(shù)據(jù)
void HeapPop(HP* php);
//按照下標(biāo)打印堆
void HeapPrint(HP* php);
//判斷堆是否為空
bool HeapEmpty(HP* php);
//求堆中有幾個(gè)元素
size_t HeapSize(HP* php);
//得到堆頂?shù)闹?
HPDataType HeapTop(HP* php);
Heap.c
#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"
//初始化結(jié)構(gòu)體
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = 0;
php->capacity = 0;
}
//銷(xiāo)毀結(jié)構(gòu)體
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->size = 0;
php->capacity = 0;
}
//交換
void HeapSwap(HPDataType* pa, HPDataType* pb)
{
HPDataType tmp = *pa;
*pa = *pb;
*pb = tmp;
}
//向上調(diào)整
void AdjustUp(HPDataType* a, size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] < a[parent])
{
HeapSwap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//插入堆
void HeapPush(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, sizeof(HPDataType)* newcapacity);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
php->a = tmp;
php->capacity = newcapacity;
}
php->a[php->size] = x;
++php->size;
//向上調(diào)整
AdjustUp(php->a, php->size - 1);
}
//向下調(diào)整
AdjustDown(HPDataType* a,size_t size, size_t root)
{
size_t parent= root;
size_t child= parent * 2 + 1;
while (child < size)
{
if (child+1 < size && a[child + 1] < a[child])
{
++child;
}
if (a[child] < a[parent])
{
HeapSwap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//刪除堆的值
void HeapPop(HP* php)
{
assert(php);
assert(php->size > 0);
//交換堆頂和堆尾的值。然后刪除堆尾的值
HeapSwap(php->a, &php->a[php->size - 1]);
--php->size;
//向下調(diào)整
AdjustDown(php->a, php->size, 0);
}
//打印堆
void HeapPrint(HP* php)
{
assert(php);
for (size_t i = 0; i < php->size; ++i)
{
printf("%d ", php->a[i]);
}
printf("\n");
}
//判斷堆是否為空
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
//求堆中有幾個(gè)元素
size_t HeapSize(HP* php)
{
assert(php);
return php->size;
}
//得到堆頂?shù)闹?
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
Test.c
#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"
void testHeap()
{
HP hp;
HeapInit(&hp);
HeapPush(&hp, 5);
HeapPush(&hp, 4);
HeapPush(&hp, 3);
HeapPush(&hp, 2);
HeapPush(&hp, 1);
HeapPrint(&hp);
/*HeapPop(&hp);
HeapPrint(&hp);*/
HeapDestroy(&hp);
}
void HeapSort(HPDataType* a, int size)
{
HP hp;
HeapInit(&hp);
for (int i = 0; i < size; i++)
{
HeapPush(&hp, a[i]);
}
size_t j = 0;
while (!HeapEmpty(&hp))
{
a[j] = HeapTop(&hp);
j++;
HeapPop(&hp);
}
HeapDestroy(&hp);
}
int main()
{
/*testHeap();*/
int a[] = { 4,2,7,8,5,1,0,6 };
HeapSort(a, sizeof(a) / sizeof(int));
for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
{
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
以上就是C語(yǔ)言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)堆的詳細(xì)內(nèi)容，更多關(guān)于C語(yǔ)言二叉樹(shù)堆的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
- C語(yǔ)言排序之?堆排序
- C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之堆排序的優(yōu)化算法
- C語(yǔ)言詳解如何實(shí)現(xiàn)堆及堆的結(jié)構(gòu)與接口
- C語(yǔ)言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)堆排序圖文示例
- C語(yǔ)言堆與二叉樹(shù)的順序結(jié)構(gòu)與實(shí)現(xiàn)
- C語(yǔ)言函數(shù)調(diào)用堆棧詳情分析
- C語(yǔ)言實(shí)現(xiàn)堆的簡(jiǎn)單操作的示例代碼
- C語(yǔ)言中的二叉樹(shù)和堆詳解
- C語(yǔ)言堆實(shí)現(xiàn)建堆算法和堆排序
相關(guān)文章
在C++?17中引入了一個(gè)標(biāo)記符nodiscard，用于聲明一個(gè)?“非棄值(no-discard)表達(dá)式”。這篇文章就來(lái)和大家來(lái)聊一聊nodiscard標(biāo)記符的使用吧2023-02-02
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言二分查找法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-08-08
這篇文章主要介紹了c語(yǔ)言多進(jìn)程tcp服務(wù)器示例,多進(jìn)程socket，epoll實(shí)現(xiàn)IO復(fù)用,需要的朋友可以參考下2014-03-03
C語(yǔ)言關(guān)鍵字auto與register及static專(zhuān)項(xiàng)詳解
這篇文章主要解釋了c語(yǔ)言中什么是數(shù)據(jù)類(lèi)型，什么是變量，他們的真正含義是什么。分析了屬性關(guān)鍵字auto,register和static的用法2022-07-07
C++ OpenCV學(xué)習(xí)之圖像金字塔與圖像融合詳解
圖像金字塔分為兩種：高斯金字塔和拉普拉斯金字塔。圖像金字塔在保持細(xì)節(jié)的條件下進(jìn)行圖像融合等多尺度編輯操作非常有用。本文將利用圖像金字塔實(shí)現(xiàn)圖像融合，需要的可以參考一下2022-03-03
c語(yǔ)言大小端(數(shù)據(jù)在內(nèi)存中的存儲(chǔ))
大小端是內(nèi)存存儲(chǔ)字節(jié)的兩種方式,一個(gè)是大端存儲(chǔ),一個(gè)是小端存儲(chǔ),本文主要介紹了c語(yǔ)言大小端,具有一定的參考價(jià)值,感興趣的可以了解一下2023-09-09
windows下在vim中搭建c語(yǔ)言開(kāi)發(fā)環(huán)境的詳細(xì)過(guò)程
Qt 數(shù)據(jù)庫(kù)QSqlDatabase使用示例