前置知識
堆本質上是一個完全二叉樹，但存盤結構是一個陣列，這個是對堆進行代碼撰寫的核心，要牢牢把握住！
下文代碼以大堆為例！
堆結構定義
堆的物理本質是一個陣列，就可以像動態順序表一樣進行結構定義，
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size; // 有效元素個數
int capacity; // 陣列長度
}HP;
函式介面
// 堆的初始化
void HeapInit(HP* hp);
// 堆的銷毀
void HeapDestroy(HP* hp);
// 堆push資料
void HeapPush(HP* hp, HPDataType x);
// 堆pop堆頂
void HeapPop(HP* hp);
// 獲得堆頂資料
HPDataType HeapTop(HP* hp);
// 空堆
bool HeapEmpty(HP* hp);
// 堆大小
int HeapSize(HP* hp);
堆的初始化
void HeapInit(HP* hp)
{
assert(hp);
hp->a = NULL;
hp->size = hp->capacity = 0;
}
堆的銷毀
順序表空間連續，所以只要free（首地址）就可以，
注意：不能忘記 hp->capacity = hp->size = 0;
void HeapDestroy(HP* hp)
{
assert(hp);
free(hp->a);
hp->a = NULL;
hp->capacity = hp->size = 0;
}
堆入資料
因為堆存盤結構就是一個陣列，所以我們在陣列末入資料，然后再進行向上調整演算法，
void HeapPush(HP* ph, HPDataType x)
{
assert(ph);
// 判斷擴容
if (ph->size == ph->capacity)
{
// 擴容
size_t newcapacity = ph->capacity == 0 ? 4 : 2 * ph->capacity;
HPDataType* tmp = realloc(ph->a, newcapacity * sizeof(HPDataType));
if (tmp == NULL)
{
// 擴容失敗
printf("realloc fail\n");
exit(-1);
}
ph->capacity = newcapacity;
ph->a = tmp;
}
// 陣列尾插資料
ph->a[ph->size++] = x;
// 向上調整
// 引數： 堆陣列，插入位置下標
AdjustUp(ph->a, ph->size - 1);
}
向上調整演算法
對插入資料大小不同，調整的最終條件也不同，
- 插入最小值
堆結構不發生變化
- 插入比堆頂元素小
父親比孩子小，交換元素，
- 插入元素比堆頂大
調整
繼續調整
結束！
代碼：
// 向上調整演算法 此處以大堆為例
void AdjustUp(int* a, int child)
{
assert(a);
int parent = (child - 1) / 2;
// 結束條件如果是parent>=0，會進入到下一個回圈通過break跳出
while (child > 0)
{
if (a[parent] < a[child])
{
// 父親結點值小于孩子結點
Swap(&a[parent], &a[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
洗掉堆頂
堆頂pop分為三個主要步驟：首先堆頂和陣列最后一個元素交換、陣列個數減一、再進行向下調整演算法，
void HeapPop(HP* hp)
{
assert(hp);
assert(hp->size != 0);
// 交換陣列首尾元素
Swap(&hp->a[0], &hp->a[hp->size - 1]);
// 陣列size減一
hp->size--;
// 堆頂元素向下調整
AdjustDown(hp->a, hp->size, 0);
}
向下調整演算法
調整結束的條件：
- 到達葉子節點
- 大堆：當大孩子小于等于父親，退出
- 小堆：小孩子 大于等于父親，退出
以調整為小堆作為講解
小孩子小于父親，調整
右孩子更小，小孩子小于父親，調整
孩子大于父親，結束調整，
// 向下調整演算法，這里默認是調整成小堆
void AdjustDown(int* a, int n, int parent)
{
assert(a);
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;
}
}
}
獲得堆頂資料
進行空堆判斷，
HPDataType HeapTop(HP* hp)
{
assert(hp);
assert(!HeapEmpty(hp));
return hp->a[0];
}
判斷空堆
bool HeapEmpty(HP* hp)
{
assert(hp);
return hp->size == 0;
}
堆大小
int HeapSize(HP* hp)
{
assert(hp);
return hp->size;
}
本文的重點在于堆向下和向上調整，
堆的應用 比如 TopK問題以及堆排序會在后面繼續更新，
碼文不易，歡迎三連，深鞠躬！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/352219.html
標籤：其他