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