堆的實現(xiàn)思路
什么是堆？
- 堆是一種 基于樹結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)，它是一棵二叉樹 ，具有以下兩個特點：
- 堆是一個完全二叉樹，即除了最后一層，其他層都是滿的，最后一層從左到右填滿。
- 堆中每個節(jié)點都滿足堆的特性，即父節(jié)點的值要么等于或者大于（小于）子節(jié)點的值。
1.1 堆的分類
堆一般分為兩類： 大堆和小堆 。
- 大堆中，父節(jié)點的值大于或等于子節(jié)點的值，
- 小堆中，父節(jié)點的值小于或等于子節(jié)點的值。
堆的主要應(yīng)用是在排序和優(yōu)先隊列中。
以下分別為兩個堆（左大堆，右小堆）：
Part2 堆的實現(xiàn)思路
2.1 使用什么實現(xiàn)？
邏輯結(jié)構(gòu)如上， 然而這僅僅是我們想像出來的而已，而實際上的堆的物理結(jié)構(gòu)是一個完全二叉樹 ， 通常是 用數(shù)組實現(xiàn)的 。如下：
對此，這就要引申出一個問題？我們該如何分辨父節(jié)點以及子節(jié)點呢？如下：
2.2 怎么分辨父節(jié)點以及子節(jié)點？
通常我們的數(shù)組下標(biāo)為“0”處即為根節(jié)點，也就是說我們一定知道一個父節(jié)點！并且我們也有“計算公式”來計算父節(jié)點以及子節(jié)點。（先記住，后面實現(xiàn)有用?。。。┮簿褪钦f我們也可以通過公式從每一個位置計算父節(jié)點以及子節(jié)點！如下：
2.3 總體實現(xiàn)思路
先建立一個結(jié)構(gòu)體，由于堆的結(jié)構(gòu)實際上是一顆完全二叉樹，因此我們的 結(jié)構(gòu)跟二叉樹一樣即可！ 接著，想想我們的堆需要實現(xiàn)的功能？ 構(gòu)建、銷毀、插入、刪除、取堆頂?shù)臄?shù)據(jù)、取數(shù)據(jù)個數(shù)、判空 。(⊙o⊙)…基本的就這些吧哈~
接著按照 定義函數(shù)接口->實現(xiàn)各個函數(shù)功能->測試測試->收工(-_^) o( ￣▽￣ )ブ
Part3** 堆的實現(xiàn)**
3.1 結(jié)構(gòu)體以及接口的實現(xiàn)
typedefint HPDataType;
typedefstruct Heap
{
HPDataType* _a;
int _size;
int _capacity;
}Heap;
// 堆的構(gòu)建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的銷毀
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的刪除
void HeapPop(Heap* hp);
// 取堆頂?shù)臄?shù)據(jù)
HPDataType HeapTop(Heap* hp);
// 堆的數(shù)據(jù)個數(shù)
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
3.2 堆的兩種建堆方式
在實現(xiàn)以上的接口之前，我們必須要知道堆的兩種建堆方式?。?！
并且僅僅通過調(diào)整建堆方式的<和>符號，我們就可以輕易控制大小堆，具體看代碼注釋！
建堆有兩種方式，分別是 自底向上建堆以及自頂向下建堆。 具體簡介如下：
- 自底向上建堆：自底向上建堆是指按照原始數(shù)組順序依次插入元素，然后對每個插入的元素執(zhí)行向上調(diào)整的操作，使得堆的性質(zhì)保持不變。這種方法需要對每個元素都進行調(diào)整操作，時間復(fù)雜度為 O(nlogn)。
- 自頂向下建堆：自頂向下建堆是指從堆頂開始，對每個節(jié)點執(zhí)行向下調(diào)整操作，使得堆的性質(zhì)保持不變。這種方法需要從根節(jié)點開始遞歸向下調(diào)整，時間復(fù)雜度為 O(n)。因此，自頂向下建堆的效率比自底向上建堆要高。
以上兩種建堆方式，實際上是基于兩種調(diào)整方法，接下來將詳細(xì)介紹：
向上調(diào)整方法
堆的向上調(diào)整方法將新插入的節(jié)點從下往上逐層比較，如果當(dāng)前節(jié)點比其父節(jié)點大（或小，根據(jù)是大根堆還是小根堆），則交換這兩個節(jié)點。一直向上比較，直到不需要交換為止。這樣可以保證堆的性質(zhì)不變。
具體步驟如下：
- 將新插入的節(jié)點插入到堆的最后一位。
- 獲取該節(jié)點的父節(jié)點的位置，比較該節(jié)點與其父節(jié)點的大小關(guān)系。
- 如果該節(jié)點比其父節(jié)點大（或小，根據(jù)是大根堆還是小根堆），則交換這兩個節(jié)點。
- 重復(fù)步驟2-3，直到不需要交換為止，堆的向上調(diào)整完成。
- 堆的向上調(diào)整的時間復(fù)雜度為O(logn)，其中n為堆的大小。
一圖讓你了解~：
實現(xiàn)如下：
void swap(HPDataType* s1, HPDataType* s2)
{
HPDataType temp = *s1;
*s1 = *s2;
*s2 = temp;
}
void Adjustup(HPDataType* a, int child)//向上調(diào)整
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])//建大堆，小堆則<
{
swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
向下調(diào)整方法
堆的向下調(diào)整方法是指將某個節(jié)點的值下放至其子節(jié)點中，以維護堆的性質(zhì)的過程。
假設(shè)當(dāng)前節(jié)點為 i，其左子節(jié)點為 2i+1，右子節(jié)點為 2i+2，堆的大小為 n
則向下調(diào)整的步驟如下：
- 從當(dāng)前節(jié)點 i 開始，將其與其左右子節(jié)點中較小或較大的節(jié)點比較，找出其中最小或最大的節(jié)點 j。
- 如果節(jié)點 i 小于等于（或大于等于，取決于是最小堆還是最大堆）節(jié)點 j，則說明它已經(jīng)滿足堆的性質(zhì)，調(diào)整結(jié)束；否則，將節(jié)點 i 與節(jié)點 j 交換位置，并將當(dāng)前節(jié)點 i 更新為 j。
- 重復(fù)執(zhí)行步驟 1 和步驟 2，直到節(jié)點 i 沒有子節(jié)點或已經(jīng)滿足堆的性質(zhì)。
一圖讓你了解~：
實現(xiàn)如下：
void swap(HPDataType* s1, HPDataType* s2)
{
HPDataType temp = *s1;
*s1 = *s2;
*s2 = temp;
}
void Adjustdown(HPDataType* a, int n, int parent)//向下調(diào)整
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child + 1] > a[child])//找出兩個孩子中較大的那個，此為大堆，如果要實現(xiàn)小堆則 改 >
{
++child;
}
if (a[child] > a[parent])//此為大堆，如果要實現(xiàn)小堆則 改 >
{
swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
3.3 堆的構(gòu)建
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
assert(hp);
assert(a);
hp- >_a = (HPDataType*)malloc(sizeof(HPDataType) * n);
if (!hp- >_a)
{
perror("malloc fail");
exit(-1);
}
hp- >_capacity = hp- >_size = n;
//將a中的元素全部轉(zhuǎn)移到堆中
memcpy(hp- >_a, a, sizeof(HPDataType) * n);
//建堆
for (int i = 1; i < n; i++)
{
Adjustup(hp- >_a, i);//按向上調(diào)整，此建立大堆
}
}
本文的構(gòu)建方法是 通過傳遞一個數(shù)組以及傳遞一個數(shù)組大小來構(gòu)建的 ，里面包括了堆結(jié)構(gòu)體的初始化操作，基本的建堆方式則是通過向上調(diào)整方法建堆。
3.4 堆的銷毀
void HeapDestory(Heap* hp)
{
assert(hp);
free(hp- >_a);
hp- >_a = NULL;
hp- >_capacity = hp- >_size = 0;
}
就正常的銷毀操作？大家應(yīng)該都懂（確信） (o°ω°o)
3.5 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
if (hp- >_capacity == hp- >_size)//擴容
{
int newcapacity = hp- >_capacity == 0 ? 4 : hp- >_capacity * 2;
HPDataType* new = (HPDataType*)realloc(hp- >_a, sizeof(HPDataType) * newcapacity);
if (!new)
{
perror("realloc fail");
exit(-1);
}
hp- >_a = new;
hp- >_capacity = newcapacity;
}
hp- >_a[hp- >_size++] = x;
Adjustup(hp- >_a, hp- >_size - 1);
}
實現(xiàn)是對于堆的空間進行判斷，不夠則是擴容操作，當(dāng)然也有初始化的意思，接著是通過向上調(diào)整的方式插入操作。
3.6 堆的刪除（較重要）
void HeapPop(Heap* hp)//先將最后一個數(shù)與堆頂交換，然后再讓size--，再進行向下調(diào)整
{
assert(hp);
swap(&hp- >_a[0], &hp- >_a[hp- >_size - 1]);
hp- >_size--;
Adjustdown(hp- >_a, hp- >_size, 0);
}
進行刪除操作，我們當(dāng)然是刪除堆頂啦，這個刪除操作先將最后一個數(shù)與堆頂交換，然后再讓size--，再進行向下調(diào)整。
一圖讓你了解~：
3.7 取堆頂?shù)臄?shù)據(jù)
HPDataType HeapTop(Heap* hp)//取堆頂
{
assert(hp);
assert(hp- >_size > 0);
return hp- >_a[0];
}
3.8 堆的數(shù)據(jù)個數(shù)
int HeapSize(Heap* hp)//堆大小
{
assert(hp);
return hp- >_size;
}
3.9 堆的判空
int HeapEmpty(Heap* hp)//判堆空
{
assert(hp);
return hp- >_size==0;
}
Part4 總體代碼
4.1pile.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS 01
#include< stdio.h >
#include< stdlib.h >
#include< string.h >
#include< assert.h >
typedefint HPDataType;
typedefstruct Heap
{
HPDataType* _a;
int _size;
int _capacity;
}Heap;
// 堆的構(gòu)建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的銷毀
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的刪除
void HeapPop(Heap* hp);
// 取堆頂?shù)臄?shù)據(jù)
HPDataType HeapTop(Heap* hp);
// 堆的數(shù)據(jù)個數(shù)
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
4.2pile.c
#include"pile.h"
void swap(HPDataType* s1, HPDataType* s2)
{
HPDataType temp = *s1;
*s1 = *s2;
*s2 = temp;
}
void Adjustup(HPDataType* a, int child)//向上調(diào)整
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])//建大堆，小堆則<
{
swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void Adjustdown(HPDataType* a, int n, int parent)//向下調(diào)整
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child + 1] > a[child])//找出兩個孩子中較大的那個，此為大堆，如果要實現(xiàn)小堆則 改 >
{
++child;
}
if (a[child] > a[parent])//此為大堆，如果要實現(xiàn)小堆則 改 >
{
swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
assert(hp);
assert(a);
hp- >_a = (HPDataType*)malloc(sizeof(HPDataType) * n);
if (!hp- >_a)
{
perror("malloc fail");
exit(-1);
}
hp- >_capacity = hp- >_size = n;
//將a中的元素全部轉(zhuǎn)移到堆中
memcpy(hp- >_a, a, sizeof(HPDataType) * n);
//建堆
for (int i = 1; i < n; i++)
{
Adjustup(hp- >_a, i);//按向上調(diào)整，此建立大堆
}
}
void HeapDestory(Heap* hp)
{
assert(hp);
free(hp- >_a);
hp- >_a = NULL;
hp- >_capacity = hp- >_size = 0;
}
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
if (hp- >_capacity == hp- >_size)//擴容
{
int newcapacity = hp- >_capacity == 0 ? 4 : hp- >_capacity * 2;
HPDataType* new = (HPDataType*)realloc(hp- >_a, sizeof(HPDataType) * newcapacity);
if (!new)
{
perror("realloc fail");
exit(-1);
}
hp- >_a = new;
hp- >_capacity = newcapacity;
}
hp- >_a[hp- >_size++] = x;
Adjustup(hp- >_a, hp- >_size - 1);
}
void HeapPop(Heap* hp)//先將最后一個數(shù)與堆頂交換，然后再讓size--，再進行向下調(diào)整
{
assert(hp);
swap(&hp- >_a[0], &hp- >_a[hp- >_size - 1]);
hp- >_size--;
Adjustdown(hp- >_a, hp- >_size, 0);
}
HPDataType HeapTop(Heap* hp)//取堆頂
{
assert(hp);
assert(hp- >_size > 0);
return hp- >_a[0];
}
int HeapSize(Heap* hp)//堆大小
{
assert(hp);
return hp- >_size;
}
int HeapEmpty(Heap* hp)//判堆空
{
assert(hp);
return hp- >_size==0;
}
4.3test.c
#include"pile.h"
void test()
{
Heap hp;
int arr[] = { 1,6,2,3,4,7,5 };
HeapCreate(&hp, arr, sizeof(arr) / sizeof(arr[0]));
//HeapPush(&hp, 10);
printf("%dn", HeapSize(&hp));
while (!HeapEmpty(&hp))
{
printf("%d %d n", HeapTop(&hp), HeapSize(&hp));
HeapPop(&hp);
}
printf("%dn", HeapSize(&hp));
HeapDestory(&hp);
HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
printf("n");
}
int main()
{
test();
return0;
}
4.4 測試結(jié)果
聲明：本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點僅代表作者本人，不代表電子發(fā)燒友網(wǎng)立場。文章及其配圖僅供工程師學(xué)習(xí)之用，如有內(nèi)容侵權(quán)或者其他違規(guī)問題，請聯(lián)系本站處理。
舉報投訴
-
接口
+關(guān)注
關(guān)注
33文章
8447瀏覽量
150720 -
數(shù)據(jù)結(jié)構(gòu)
+關(guān)注
關(guān)注
3文章
569瀏覽量
40072 -
元素
+關(guān)注
關(guān)注
0文章
47瀏覽量
8410 -
二叉樹
+關(guān)注
關(guān)注
0文章
74瀏覽量
12302
發(fā)布評論請先 登錄
相關(guān)推薦
堆煤傳感器的工作原理是什么？
堆煤傳感器正常時煤位傳感器輸出端“堆煤”輸出高電平，當(dāng)煤位增高推移傳感器偏轉(zhuǎn)一定角度時，其內(nèi)萬向接點導(dǎo)通， “堆煤”輸出低電平，“滿煤”指示燈亮，經(jīng)短暫延時，主機執(zhí)行繼電器釋放，實現(xiàn)
發(fā)表于 03-31 09:00
如何使用鏈接腳本刪除堆分配？
的 heap_symbol），這對我來說會更好，因為否則這個符號會得到它的地址，并且可以使用它的地址覆蓋內(nèi)存。我的問題是，當(dāng)我只是丟棄它時，我得到了期望此引用的 gcc 文件 (_cr_sbrk.c) 的引用錯誤。我想尋求幫助來實現(xiàn)我的目標(biāo)，即安全地從鏈接器中刪除堆分配
發(fā)表于 03-23 07:05
整流堆,什么是整流堆
整流堆,什么是整流堆
橋堆的檢測
1. 全橋的檢測 大多數(shù)的整流全橋上，均標(biāo)注有“+”、“-”、“~”符號（其中“+”為整流后輸出電壓
發(fā)表于 02-27 10:46
?2116次閱讀
常用橋堆及半橋堆電路結(jié)構(gòu)分析
橋堆及半橋堆都是整流二極管的組合器件，這一點可以從它們的結(jié)構(gòu)中看出。在許多電源電路中使用橋堆或半橋堆構(gòu)成整流電路。
發(fā)表于 08-26 10:34
?8484次閱讀
堆和堆的應(yīng)用：堆排序和優(yōu)先隊列
堆(Heap))是一種重要的數(shù)據(jù)結(jié)構(gòu)，是實現(xiàn)優(yōu)先隊列(Priority Queues)首選的數(shù)據(jù)結(jié)構(gòu)。
串口WiFi模塊實現(xiàn)遠(yuǎn)程控制電飯煲的設(shè)計思路分享.pdf
分享一個串口WiFi模塊實現(xiàn)遠(yuǎn)程控制電飯煲的設(shè)計思路，通過串口wifi模塊可以在手機app上遠(yuǎn)程操控電飯煲，相比定時的效果更好！
發(fā)表于 04-26 16:57
?76次下載
什么是堆內(nèi)存？堆內(nèi)存是如何分配的？
在一般的編譯系統(tǒng)中，堆內(nèi)存的分配方向和棧內(nèi)存是相反的。當(dāng)棧內(nèi)存從高地址向低地址增長的時候，堆內(nèi)存從低地址向高地址分配。
實現(xiàn)完全 MCU 分區(qū)隔離：堆
曾幾何時，嵌入式系統(tǒng)非常簡單以至于很少使用堆。然而，從那時起，復(fù)雜性增長得如此之快，以至于大多數(shù)嵌入式系統(tǒng)，甚至是實時操作系統(tǒng)，現(xiàn)在都使用堆。如果只有一個堆在使用，堆效率就不是什么大問
發(fā)表于 11-26 15:21
?20次下載
STL中的堆算法該如何使用呢？
了解過數(shù)據(jù)結(jié)構(gòu)的人，應(yīng)該對堆結(jié)構(gòu)不陌生，堆的底層是使用數(shù)組來實現(xiàn)的，但卻保持了二叉樹的特性。
橋堆的作用是什么？橋堆整流后電壓是多少?
橋堆的作用及工作原理解讀 橋堆的作用是什么？橋堆整流后電壓是多少?? 橋堆是一種常用的電路，廣泛應(yīng)用于電力電子系統(tǒng)中。橋堆是一種全波整流電路
UVC bulk傳輸實現(xiàn)思路
前段時間有個讀者咨詢UVC bulk 傳輸實現(xiàn)，接著這個機會重新梳理一遍UVC bulk 傳輸實現(xiàn)思路,同時對比ISO 與 Bulk 實現(xiàn)不同。
智慧礦山&礦山安全生產(chǎn):AI智能堆料檢測-打造高效井下堆料管理系統(tǒng)
通過AI算法實現(xiàn)井下堆料檢測，并打造智能堆料管理系統(tǒng)，提高堆料效率。
如何使用SystemView的堆監(jiān)控功能
SystemView能夠監(jiān)視應(yīng)用程序如何使用動態(tài)存儲。這意味著，如果應(yīng)用程序中使用了C或C++堆、自定義堆或RTOS提供的內(nèi)存池對象，我們可以跟蹤這些對象的使用情況。SystemView可以在一個
工商網(wǎng)監(jiān)
評論