C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)二叉樹堆
“竹杖芒鞋輕勝馬，誰怕？一蓑煙雨任平生”
C語言朱武大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)專欄
C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)快速排序圖文示例
C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)希爾排序算法
C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)堆排序圖文示例
C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)二叉樹遞歸
前言
此篇詳細實現(xiàn)二叉樹中的一個順序結(jié)構(gòu)的實現(xiàn)——堆。并實現(xiàn)堆排序重點是堆的規(guī)律和堆的實現(xiàn)
堆的概念
堆：將一些元素按完全二叉樹的順序存儲方式存儲在一個一維數(shù)組中。這就是堆。完全二叉樹：通俗講就是只有最后一層的節(jié)點可以滿，也可以不滿。但是最后一層之前的節(jié)點要滿，這就叫做完全二叉樹。
小堆大堆：將根節(jié)點最大的堆叫做最大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆。（必須滿足堆的性質(zhì)）
堆的性質(zhì)：
1.堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值
2.堆總是一棵完全二叉樹。
注意：
1.普通的二叉樹是不適合用數(shù)組來存儲的，因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結(jié)構(gòu)存儲。
2.現(xiàn)實中我們通常把堆(一種特殊的二叉樹)使用順序結(jié)構(gòu)的數(shù)組來存儲。
3.需要注意的是這里的堆和操作系統(tǒng)虛擬進程地址空間中的堆是兩回事，一個是數(shù)據(jù)結(jié)構(gòu)，一個是操作系統(tǒng)中管理內(nèi)存的一塊區(qū)域分段。
接下來我們用純C實現(xiàn)小堆
創(chuàng)建結(jié)構(gòu)體
因為完全二叉樹更適合使用順序結(jié)構(gòu)存儲。而堆就是完全二叉樹，所以我們需要創(chuàng)建順序表
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;//a指向只一個堆數(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;
}
銷毀結(jié)構(gòu)體
因為是動態(tài)版的順序表，有動態(tài)開辟就需要動態(tài)內(nèi)存釋放，也就是free掉a所指向的空間。
//銷毀結(jié)構(gòu)體
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é)構(gòu)和邏輯結(jié)構(gòu)
前面的步驟打造了一個堆的輪廓，你說它是堆吧，其實本質(zhì)就是一個物理結(jié)構(gòu)在內(nèi)存中連續(xù)的順序表罷了。也就是數(shù)組。如圖下標從0開始。
但是要用到它的邏輯結(jié)構(gòu)，需要把它想象成一個完全二叉樹，就是下面圖片這個樣子。
好了，現(xiàn)在我們要向堆中插入數(shù)據(jù)了，因為順序表尾插效率高O(1),且尾插不會大幅度改變堆的結(jié)構(gòu)。所以插入數(shù)據(jù)指的是尾插。
2.完全二叉樹下標規(guī)律
注意：
1.尾插注意的是size的大小，size一直指向的是即將插入的那個空間。
2.和順序表唯一不同的是尾插后需要向上調(diào)整數(shù)據(jù)，保持小堆的從上往下依次增大的結(jié)構(gòu)
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>
刪除也是一門藝術(shù)。今天的我是站在巨人的肩膀上學(xué)習(xí)堆的刪除。
大佬們的算法思路是：
1.先讓堆頂?shù)闹岛投盐驳闹到粨QO(1)，然后刪除O(1)交換后堆尾的值。
2.再使用向下調(diào)整O(logN)算法，先比較left和right哪個小，誰小就讓parent和誰交換，然后依次迭代，使堆頂?shù)闹迪蛳抡{(diào)整。直到child大于size結(jié)束循環(huán)。
因為這樣的時間復(fù)雜度是相當(dāng)牛的。
注意：這里有幾個地方代碼技巧非常絕。
1.假設(shè)左子樹就是最小的值。然后比較左右子樹的大小后進行調(diào)整到底誰是最小的就OK了。這是非常的絕。因為你需要關(guān)注到底是左子樹小還是右子樹小！
//非常絕的一個思路
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);
}
判斷堆是否為空
當(dāng)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.當(dāng)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;
}
時間復(fù)雜度分析：
時間復(fù)雜度為O(N*logN)。比冒泡排序上升了一個檔次哦。
但是空間復(fù)雜度有待改進。
但是空間復(fù)雜度因為占用了一個數(shù)組所以是O(N)。
空間復(fù)雜度改進的話需要很多字來詳解。下篇博文繼續(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);
//銷毀結(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);
//按照下標打印堆
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é)構(gòu)體
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = 0;
php->capacity = 0;
}
//銷毀結(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;
}
//求堆中有幾個元素
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é)構(gòu)二叉樹堆的詳細內(nèi)容，更多關(guān)于C語言二叉樹堆的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
在C++11之前,每個數(shù)據(jù)類型都需要在編譯時顯示聲明,在運行時限制表達式的值,但在C++的新版本之后,引入了 auto 和 decltype等關(guān)鍵字,本文就來介紹一下C++中類型推斷(auto和decltype)的使用,感興趣的可以了解一下2023-12-12
今天小編就為大家分享一篇關(guān)于C++標準模板庫vector的常用操作，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
這篇文章主要為大家詳細介紹了C語言鏈表實現(xiàn)歌手評分系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-03-03
這篇文章主要介紹了C++采用openfilename打開文件對話框用法實例,是C++文件操作中非常實用的技巧,需要的朋友可以參考下2014-10-10
C++實現(xiàn)LeetCode(167.兩數(shù)之和之二 - 輸入數(shù)組有序)
這篇文章主要介紹了C++實現(xiàn)LeetCode(167.兩數(shù)之和之二 - 輸入數(shù)組有序),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-08-08
C++左值與右值,右值引用,移動語義與完美轉(zhuǎn)發(fā)詳解
這篇文章主要為大家詳細介紹了Python實現(xiàn)學(xué)生成績管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
這篇文章主要給大家介紹了關(guān)于C++中void*的一些小作用，文中通過示例代碼介紹的非常詳細，對大家學(xué)習(xí)或者使用C++具有一定的參考學(xué)習(xí)價值，需要的朋友可以參考借鑒，下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。2017-08-08
C#將Unicode編碼轉(zhuǎn)換為漢字字符串的簡單方法
下面小編就為大家?guī)硪黄狢#將Unicode編碼轉(zhuǎn)換為漢字字符串的簡單方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-01-01
程序中經(jīng)常需要將一組數(shù)據(jù)元素作為整體管理和使用，需要創(chuàng)建這種元素組，用變量記錄它們，傳進傳出函數(shù)等。一組數(shù)據(jù)中包含的元素個數(shù)可能發(fā)生變化，順序表則是將元素順序地存放在一塊連續(xù)的存儲區(qū)里，元素間的順序關(guān)系由它們的存儲順序自然表示2022-03-03
C++編程中break語句和continue語句的學(xué)習(xí)教程
這篇文章主要介紹了C++編程中break語句和continue語句的學(xué)習(xí)教程,break和continue是C++循環(huán)控制中的基礎(chǔ)語句,需要的朋友可以參考下2016-01-01