文章目錄
- 堆
- 堆的概念及結構
- 堆的性質
- 堆的結構（這里實作大堆）
- 堆的結構體
- 堆初始化函式HeapInit
- 堆銷毀函式HeapDestroy
- 堆列印函式HeapPrint
- 向上調整函式AdjustUp
- 堆插入函式HeapPush
- 判斷堆是否為空函式HeapErmpy
- 回傳堆大小函式HeapSize
- 交換函式Swap
- 向下調整函式AdjustDown
- 堆洗掉函式HeapPop
- 代碼
- Heap.h
- Heap.c
- test.c
堆
資料結構中的堆不同于作業系統中的堆（作業系統中的堆是用來存盤動態記憶體的），資料結構中的堆是資料的存盤方式，資料結構中的堆是完全二叉樹
既然堆是完全二叉樹的形式存盤的那么就非常適合用陣列的方式來表示
堆的概念及結構
如果有一個關鍵碼的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉樹的順序存盤方式存盤在一個一維陣列中，并滿足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，則稱為小堆(或大堆)，將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆，
大堆：樹中一個樹及子樹中，任何一個父親都大于等于孩子
小堆：樹中一個樹及子樹中，任何一個父親都小于等于孩子
堆的性質
堆中某個節點的值總是不大于或不小于其父節點的值；
堆總是一棵完全二叉樹，**
堆的結構（這里實作大堆）
既然還是陣列的結構的話就還是順序表的處理方式，陣列指標，size，capacity，雖然物理上我們是用順序表的方式來表示，但是他實際上表示的資料是完全二叉樹，
堆的結構體
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
堆初始化函式HeapInit
就是一個指向NULL的陣列，size 和 capacity都為零
//堆初始化函式
void HeapInit(HP* hp)
{
assert(hp);
hp->a = NULL;
hp->size = hp->capacity = 0;
}
堆銷毀函式HeapDestroy
由于陣列是動態開辟的，所以用完后需要銷毀的，不然會記憶體泄漏
//堆銷毀函式
void HeapDestroy(HP* hp)
{
assert(hp);
free(hp->a);
hp->size = hp->capacity = 0;
}
堆列印函式HeapPrint
可以想象成一種快速除錯，類似于單片機中的串口列印看資料收發情況
//堆列印函式
void HeapPrint(HP* hp)
{
int i = 0;
for (i = 0; i < hp->size; i++)
{
printf("%d ", hp->a[i]);
}
printf("\n");
}
向上調整函式AdjustUp
為了不影響資料的存盤形式（大堆還得是大堆），插入資料就不能破壞大堆的形式，我們需要把堆插入函式中的資料調整給剝離出來
我們可以看到插入的這個資料對其他的節點并沒有什么影響，有影響的只是這個節點到根這條路徑上的節點，如何解決對這條路徑的影響呢，我們可以形象的看到僅僅是在這條路徑上進行向上調整
通過parent = （child-1）/2 找到父親節點，與之進行比較，然后父親小就交換位置（大堆），然后交換后就在找上面的父親節點，直到找到父親大于孩子，就不交換了
//向上調整函式
void AdjustUp(HPDataType* a, int child)
{
assert(a);
int parent = (child - 1) / 2;
while (child>0)
{
if (a[parent] < a[child])//父親小于孩子就交換（大堆）
{
a[parent] = a[parent] ^ a[child];
a[child] = a[parent] ^ a[child];
a[parent] = a[parent] ^ a[child];
//交換好后重新稱呼一下孩子與父親
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
堆插入函式HeapPush
//堆插入函式（要保持原來形式，大堆還是大堆，小堆就還是小堆）
void HeapPush(HP* hp, HPDataType x)
{
assert(hp);
//判斷擴容
if (hp->size == hp->capacity)
{
//容量給新的容量
int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
//擴容
HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
//增容失敗
if (!tmp)
{
printf("realloc fail\n");
exit(-1);
}
//增容成功
hp->a = tmp;
hp->capacity = newcapacity;
}
//放資料
hp->a[hp->size] = x;
hp->size++;
//實作大堆
//這個部分的向上調整其他地方也用的到就把他剝離出來
AdjustUp(hp->a, hp->size - 1);//child下標
}
判斷堆是否為空函式HeapErmpy
//判斷堆是否為空函式
bool HeapErmpy(HP* hp)
{
assert(hp);
return hp->size == 0;
}
回傳堆大小函式HeapSize
//回傳堆大小函式
int HeapSize(HP* hp)
{
assert(hp);
return hp->size;
}
下面還會用到交換函式，上面也有那么我們不妨把他剝離出來封裝一下，就不需要重復寫了
交換函式Swap
//交換函式
void Swap(HPDataType* px, HPDataType* py)
{
*px = *px ^ *py;
*py = *px ^ *py;
*px = *px ^ *py;
}
向下調整函式AdjustDown
//向下調整函式
void AdjustDown(HPDataType* a, int size, int parent)
{
assert(a);
//創建一個孩子變數，有兩個孩子就在這個上加1就行
int child = parent * 2 + 1;
while (child< size)
{
//選大孩子
if (child + 1 < size && a[child] < a[child + 1])
{
child++;
}
//大的孩子還大于父親就交換
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
}
}
堆洗掉函式HeapPop
我們可以認為假想根和堆的最后一個元素交換后，把最后一個洗掉，然后再對堆進行操作，你會發現，我們沒有破壞原來的整體結構
//堆洗掉函式（洗掉的是堆頂資料也就是取最值）
//還有不可能一直刪的所以我們需要一個判空函式
void HeapPop(HP* hp)
{
assert(hp);
assert(!HeapErmpy(hp));
//根和堆最后一個元素交換
Swap(&hp->a[0],&hp->a[hp->size-1]);
//把最后一個洗掉，就是我們想要洗掉的元素
hp->size--;
//向下調整
AdjustDown(hp->a,hp->size,0);
}
代碼
Heap.h
#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;
//堆初始化函式
extern void HeapInit(HP* hp);
//堆銷毀函式
extern void HeapDestroy(HP* hp);
//向上調整函式
extern void AdjustUp(HPDataType* a,int child);
//堆插入函式
extern void HeapPush(HP* hp,HPDataType x);
//堆列印函式
extern void HeapPrint(HP* hp);
//向下調整函式
extern void AdjustDown(HPDataType* a, int size, int parent);
//堆洗掉函式
extern void HeapPop(HP* hp);
//判斷堆是否為空函式
extern bool HeapErmpy(HP* hp);
//交換函式
extern void Swap(HPDataType* px, HPDataType* py);
//回傳堆大小函式
extern int HeapSize(HP* hp);
Heap.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
//堆初始化函式
void HeapInit(HP* hp)
{
assert(hp);
hp->a = NULL;
hp->size = hp->capacity = 0;
}
//堆銷毀函式
void HeapDestroy(HP* hp)
{
assert(hp);
free(hp->a);
hp->size = hp->capacity = 0;
}
//向上調整函式
void AdjustUp(HPDataType* a, int size, int child)
{
assert(a);
int parent = (child - 1) / 2;
while (child>0)
{
if (a[parent] < a[child])//父親小于孩子就交換（大堆）
{
Swap(&a[parent], &a[child]);
//交換好后重新稱呼一下孩子與父親
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//堆插入函式（要保持原來形式，大堆還是大堆，小堆就還是小堆）
void HeapPush(HP* hp, HPDataType x)
{
assert(hp);
//判斷擴容
if (hp->size == hp->capacity)
{
//容量給新的容量
int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
//擴容
HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
//增容失敗
if (!tmp)
{
printf("realloc fail\n");
exit(-1);
}
//增容成功
hp->a = tmp;
hp->capacity = newcapacity;
}
//放資料
hp->a[hp->size] = x;
hp->size++;
//實作大堆
//這個部分的向上調整其他地方也用的到就把他剝離出來
//向上調整一下堆的資料形式，使他還是大堆的形式
AdjustUp(hp->a, hp->size, hp->size - 1);
}
//堆列印函式
void HeapPrint(HP* hp)
{
assert(hp);
int i = 0;
for (i = 0; i < hp->size; i++)
{
printf("%d ", hp->a[i]);
}
printf("\n");
}
//判斷堆是否為空函式
bool HeapErmpy(HP* hp)
{
assert(hp);
return hp->size == 0;
}
//回傳堆大小函式
int HeapSize(HP* hp)
{
assert(hp);
return hp->size;
}
//交換函式
void Swap(HPDataType* px, HPDataType* py)
{
*px = *px ^ *py;
*py = *px ^ *py;
*px = *px ^ *py;
}
//向下調整函式
void AdjustDown(HPDataType* a, int size, int parent)
{
assert(a);
//創建一個孩子變數，有兩個孩子就在這個上加1就行
int child = parent * 2 + 1;
while (child< size)
{
//選大孩子
if (child + 1 < size && a[child] < a[child + 1])
{
child++;
}
//大的孩子還大于父親就交換
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//堆洗掉函式（洗掉的是堆頂資料也就是取最值）
//還有不可能一直刪的所以我們需要一個判空函式
void HeapPop(HP* hp)
{
assert(hp);
assert(!HeapErmpy(hp));
//根和堆最后一個元素交換
Swap(&hp->a[0],&hp->a[hp->size-1]);
//把最后一個洗掉，就是我們想要洗掉的元素
hp->size--;
//向下調整
AdjustDown(hp->a,hp->size,0);
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void test()
{
int a[] = { 70,56,30,25,15,75 };
HP hp;
HeapInit(&hp);
int i = 0;
for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
HeapPush(&hp, a[i]);
}
HeapPrint(&hp);
HeapPop(&hp);
HeapPrint(&hp);
HeapDestroy(&hp);
}
int main()
{
test();
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/354694.html
標籤：其他