C語言 深入解讀數(shù)據(jù)結(jié)構(gòu)之堆的實(shí)現(xiàn)
更新時(shí)間：2021年11月09日 15:47:11 作者：loveandsharef
堆就是用數(shù)組實(shí)現(xiàn)的二叉樹，所以它沒有使用父指針或者子指針。堆根據(jù)“堆屬性”來排序，“堆屬性”決定了樹中節(jié)點(diǎn)的位置
堆的概念與結(jié)構(gòu)
概念：如果有一個(gè)關(guān)鍵碼的集合K={ k0，k1 ，k2 ，…，kn-1 },把它的所有元素按完全二叉樹的順序存儲方式存儲 在一個(gè)一維數(shù)組中，并滿足K i<=K 2*i+1且Ki<=K 2*i+2(K i>=K 2*i+1且Ki>=K 2*i+2) i = 0，1，2...，則稱為小堆(或大堆)。將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。
性質(zhì)：
- 堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
- 堆總是一棵完全二叉樹。
結(jié)構(gòu)：
1.大堆
2.小堆
堆(大根堆)的實(shí)現(xiàn)：
堆的接口：
#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;
//堆的創(chuàng)建
void HeapInit(HP*hp);
//堆的銷毀
void HeapDestroy(HP*hp);
//交換數(shù)值
void Swap(HPDataType *px, HPDataType *py);
//向上調(diào)整
void AdjustUp(int *a,int child);
//向下調(diào)整
void AdjustDown(int *a, int n, int parent);
//堆的插入
void HeapPush(HP*hp,HPDataType x);
//堆的刪除
void HeapPop(HP*hp);
//取堆頂?shù)臄?shù)據(jù)
HPDataType HeapTop(HP*hp);
//打印堆
void HeapPrint(HP*hp);
//堆的判空
bool HeapEmpty(HP*hp);
//堆的數(shù)據(jù)個(gè)數(shù)
int HeapSize(HP*hp);
堆的創(chuàng)建：
void HeapInit(HP*hp)
{
assert(hp);
hp->a=NULL;
hp->capacity=hp->size=0;
}
堆的銷毀：
void HeapDestroy(HP*hp)
{
assert(hp);
free(hp->a);
hp->capacity=hp->size=0;
}
交換數(shù)值：
void Swap(HPDataType*px, HPDataType*py)
{
HPDataType tmp = *px;
*px=*py;
*py=tmp;
}
向上調(diào)整：
void AdjustUp(int*a, int child)
{
assert(a);
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])
{
//交換數(shù)值
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
堆得插入：
void HeapPush(HP*hp,HPDataType x)
{
assert(hp);
if(hp->capacity==hp->size)
{
size_t newCapacity=hp->capacity==0?4:hp->capacity*2;
HPDataType * tmp=(HPDataType*)realloc(hp->a,newCapacity*sizeof(HPDataType));
if(tmp==NULL)
{
printf("realloc is fail\n");
}
hp->a=tmp;
hp->capacity=newCapacity;
}
hp->a[hp->size-1]=x;
hp->size++;
//向上調(diào)整
AdjusiUp(hp->a,hp->size-1);
}
向下調(diào)整：
void AdjustDown(int *a,int n,int parent)
{
int child=parent*2+1;
while(child<n)
{
//比較左孩子還是右孩子大
if(child+1<n && a[child+1]>a[child])
{
child++;
}
if(a[child]>a[parent])
{
Swap(&a[child],&a[parent]);
parent=child;
child=parent*2+1;
}
else
{
break;
}
}
}
堆的判空：
bool HeapEmpty(HP*hp)
{
assert(hp);
return hp->size==0;
}
堆的刪除：
void HeapPop(HP*hp)
{
assert(hp);
//堆的判空
assert(!HeapEmpty(hp));
//交換數(shù)值
Swap(&hp->a[0], &hp->a[hp->size - 1]);
hp->size--;
//向下調(diào)整
AdjustDown(hp->a, hp->size, 0);
}
取堆頂?shù)臄?shù)據(jù)：
HPDataType HeapTop(HP*hp)
{
assert(hp);
assert(!HeapEmpty(hp));
return hp->a[0];
}
打印堆：
void HeapPrint(HP*hp)
{
assert(hp);
assert(!HeapEmpty(hp));
for(int i=0; i<hp->size;i++)
{
printf("%d",hp->a[i]);
}
printf("\n");
}
堆的數(shù)據(jù)個(gè)數(shù)：
int HeapSize(HP*hp)
{
assert(hp);
return hp->size;
}
以上就是對堆的講解與操作實(shí)現(xiàn)。
感謝老鐵看到這里，如果文章對你有用的話請給我一個(gè)贊支持一下，感激不盡！
在下才疏學(xué)淺,一點(diǎn)淺薄之見，歡迎各位大佬指點(diǎn)。
以上就是C語言 深入解讀數(shù)據(jù)結(jié)構(gòu)之堆的實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于C語言 數(shù)據(jù)結(jié)構(gòu)的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
C語言用函數(shù)指針實(shí)現(xiàn)一個(gè)特別的計(jì)算器
函數(shù)指針是一個(gè)指針變量,它可以存儲函數(shù)的地址,然后使用函數(shù)指針,下面這篇文章主要給大家介紹了關(guān)于C語言用函數(shù)指針實(shí)現(xiàn)計(jì)算器的方法,需要的朋友可以參考下2022-07-07
單例模式（Singleton Pattern）是最簡單的設(shè)計(jì)模式之一。這種類型的設(shè)計(jì)模式屬于創(chuàng)建型模式，它提供了一種創(chuàng)建對象的最佳方式，這種模式涉及到一個(gè)單一的類，該類負(fù)責(zé)創(chuàng)建自己的對象，同時(shí)確保只有單個(gè)對象被創(chuàng)建2022-06-06
這篇文章主要為大家詳細(xì)介紹了如何利用C語言制作一個(gè)簡單的表白神器，文中的示例代碼講解詳細(xì)，具有一定的借鑒價(jià)值，感興趣的小伙伴可以了解一下2023-03-03
淺談C++ Explicit Constructors(顯式構(gòu)造函數(shù))
下面小編就為大家?guī)硪黄獪\談C++ Explicit Constructors(顯式構(gòu)造函數(shù))。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-12-12
這篇文章主要為大家詳細(xì)介紹了利用C語言實(shí)現(xiàn)五子棋游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-08-08
七夕節(jié)還不知道送啥，教你用MATLAB制作一款刮刮樂抽獎(jiǎng)特效，讓她的手氣決定她的禮物。文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以了解一下2022-03-03
C++實(shí)現(xiàn)圖片jpg格式變成16位565bmp格式
這篇文章主要為大家詳細(xì)介紹了C++如何實(shí)現(xiàn)圖片jpg格式變成16位565bmp格式,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以了解一下2025-03-03
一篇文章教你用C語言模擬實(shí)現(xiàn)字符串函數(shù)
這篇文章主要介紹了C語言模擬實(shí)現(xiàn)字符串函數(shù),開發(fā)程序的時(shí)候經(jīng)常使用到一些字符串函數(shù)，例如求字符串長度，拷貝字符串……，需要的朋友可以參考下2021-09-09
這篇文章主要介紹了C語言冒泡排序，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-11-11
當(dāng)我們在寫一段代碼時(shí)，如果要頻繁的在一塊區(qū)域進(jìn)行插入或者刪除操作時(shí)，會發(fā)現(xiàn)用數(shù)組實(shí)現(xiàn)會比較復(fù)雜，這時(shí)候我們就要用另一種數(shù)據(jù)結(jié)構(gòu)，鏈表來實(shí)現(xiàn)2022-05-05