今天我們來學(xué)習(xí)堆，它也是二叉樹的一種（我滴神樹！）

堆的介紹：

如果有一個關(guān)鍵碼的集合K = { ， ， ，…， }，把它的所有元素按完全二叉樹的順序存儲方式存儲 在一個一維數(shù)組中，并滿足： <= 且
<= ( >= 且 >= ) i = 0，1，
2…，則稱為小堆(或大堆)。將根節(jié)點最大的堆叫做最大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆。

堆的性質(zhì)：

• 堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值；
• 堆總是一棵完全二叉樹。

堆的代碼實現(xiàn)：

堆的結(jié)構(gòu)體創(chuàng)建：

typedef int HpDataType;typedef struct Heap
{int size;int capacity;HpDataType* a;
}Hp;

堆的初始化：

這里我們選擇先不給賦值，等push時再給賦值

void HpInit(Hp* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}

堆的銷毀：

雖然與初始化相似，但是不能混用

void HpDestory(Hp* php)
{assert(php);free(php->a);php->a = NULL;php->size = 0;php->capacity = 0;
}

堆的push：

我們需要一個向上調(diào)整算法：

這里我們選擇創(chuàng)建小堆

因為我們只有push需要創(chuàng)建newnode，故不需要重新封裝一個CreatNewnode函數(shù)調(diào)整算法時需要傳的參數(shù)是

void HpPush(Hp* php, HpDataType x)
{assert(php);if (php->capacity == php->size){int newcapacity = (php->capacity == 0 ? 4 : php->capacity * 2);HpDataType* tmp = (HpDataType*)realloc(php->a, sizeof(HpDataType)* newcapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

向上調(diào)整算法：

注意：
我們在進(jìn)行向上傳參時，要傳入動態(tài)數(shù)組的地址和最后一個葉子節(jié)點的下標(biāo)，為什么不是傳入結(jié)構(gòu)體的地址原因會在后來講解

Swap(HpDataType* e1, HpDataType* e2)
{HpDataType tmp = *e1;*e1 = *e2;*e2 = tmp;
}void AdjustUp(HpDataType* a, int child)
{int parent = (child - 1) / 2;//假設(shè)進(jìn)入循環(huán)時child > 0//這里選擇child = 0作為結(jié)束標(biāo)志是因為當(dāng)child = 0時//a[child] 與 a[parent]已經(jīng)交換過一次了,//他們兩現(xiàn)在同時指向下標(biāo)位0，不需要在交換了while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);}else{break;}child = (child - 1) / 2;parent = (parent - 1) / 2;}
}

堆的pop：

注意：
我們在進(jìn)行pop時，并不是pop最后的葉子節(jié)點，這樣沒有實際意義，我們要pop的是根節(jié)點，這樣是有實際意義的，比如Top k問題，堆排序等

pop主體部分：

void HpPop(Hp* php)
{assert(php);Swap(&php->a[php->size - 1], &php->a[0]);php->size--;AdjustDown(php->a, php->size, 0);
}

同理我們也需要一個向下調(diào)整算法

注意：

傳參時仍然是傳動態(tài)數(shù)組a的地址，另外還需要size與根節(jié)點0的下標(biāo)，
size用于判斷是否超出堆的范圍，0作為parent的初始值

向下調(diào)整時我們需要找出孩子節(jié)點中較大或較小的那個，在這種情況下我們可以使用假設(shè)法，假設(shè)后在進(jìn)行判斷是否正確，將兩段邏輯變成一段邏輯

AdjustDown(HpDataType* a, int size, int parent)
{//假設(shè)法int child = parent * 2 + 1;while (child < size){if (child + 1 < size && a[child] > a[child + 1]){child++;}if (a[parent] > a[child]){Swap(&a[parent], &a[child]);}else{break;}child = child * 2 + 1;parent = parent * 2 + 1;}
}

判空 && 求Top元素 && 求size：

bool HpEmpty(Hp* php)
{assert(php);return php->size == 0;
}int HpTop(Hp* php)
{assert(php);//注意為空assert(php->size);return php->a[0];
}int HpSize(Hp* php)
{assert(php);return php->size;
}

完整源碼：

heap.c

#define _CRT_SECURE_NO_WARNINGS 1#include"heap.h"void HpInit(Hp* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}void HpDestory(Hp* php)
{assert(php);free(php->a);php->a = NULL;php->size = 0;
}Swap(HpDataType* e1, HpDataType* e2)
{HpDataType tmp = *e1;*e1 = *e2;*e2 = tmp;
}void AdjustUp(HpDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);}else{break;}child = (child - 1) / 2;parent = (parent - 1) / 2;}
}
//小堆
void HpPush(Hp* php, HpDataType x)
{assert(php);if (php->capacity == php->size){int newcapacity = (php->capacity == 0 ? 4 : php->capacity * 2);HpDataType* tmp = (HpDataType*)realloc(php->a, sizeof(HpDataType)* newcapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}AdjustDown(HpDataType* a, int size, int parent)
{//假設(shè)法int child = parent * 2 + 1;while (child < size){if (child + 1 < size && a[child] > a[child + 1]){child++;}if (a[parent] > a[child]){Swap(&a[parent], &a[child]);}else{break;}child = child * 2 + 1;parent = parent * 2 + 1;}
}void HpPop(Hp* php)
{assert(php);Swap(&php->a[php->size - 1], &php->a[0]);php->size--;AdjustDown(php->a, php->size, 0);
}bool HpEmpty(Hp* php)
{assert(php);return php->size == 0;
}int HpTop(Hp* php)
{assert(php);assert(php->size);return php->a[0];
}int HpSize(Hp* php)
{assert(php);return php->size;
}

heap.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int HpDataType;typedef struct Heap
{int size;int capacity;HpDataType* a;
}Hp;void HpInit(Hp* php);void HpDestory(Hp* php);void HpPush(Hp* php, HpDataType x);void HpPop(Hp* php);bool HpEmpty(Hp* php);int HpSize(Hp* php);int HpTop(Hp* php);

有疑問可以及時找博主交流