手搓堆（C语言）

Heap.h

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;//初始化
void HeapInit(Heap* php);
//堆的构建
void HeapCreate(Heap* php, HPDataType* a, int size);
//销毁
void HeapDestroy(Heap* php);
//向上调整
void AdjustUp(HPDataType* a, int child);
//插入
void HeapPush(Heap* php, HPDataType data);
//向下调整
void AdjustDown(HPDataType* a, int parent, int size);
//删除
void HeapPop(Heap* php);
//取堆顶数据
HPDataType HeapTop(Heap* php);
//堆的大小
int HeapSize(Heap* php);
//是否为空
bool HeapEmpty(Heap* php);
//打印函数
void Print(Heap* php);

Heap.c

#include "Heap.h"//初始化
void HeapInit(Heap* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}//堆的构建
void HeapCreate(Heap* php, HPDataType* a, int size)
{assert(php);php->a = (HPDataType*)malloc(sizeof(HPDataType) * size);if (php->a == NULL){perror("HeapCreate");exit(-1);}php->size = size;php->capacity = size;//插入memcpy(php->a, a, sizeof(HPDataType) * size);//向下调整建堆int i;for (i = (size - 2) / 2; i >= 0; i--){AdjustDown(php->a, i, size);}
}
//销毁
void HeapDestroy(Heap* php)
{assert(php);free(php->a);php->a = NULL;php->size = 0;php->capacity = 0;
}void Swap(HPDataType* x, HPDataType* y)
{assert(x && y);HPDataType tmp = *x;*x = *y;*y = tmp;
}//向上调整
void AdjustUp(HPDataType* a, int child)
{assert(a);while (child > 0){int parent = (child - 1) / 2;//小堆if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;}else{break;}}
}//插入
void HeapPush(Heap* php, HPDataType data)
{assert(php);//扩容if (php->size == php->capacity){int NewCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * NewCapacity);if (tmp == NULL){perror("HeapPush");exit(-1);}php->a = tmp;php->capacity = NewCapacity;}//插入php->a[php->size++] = data;//建堆AdjustUp(php->a, php->size - 1);}//向下调整
void AdjustDown(HPDataType* a, int parent, int size)
{assert(a);int SChild = parent * 2 + 1;while (SChild < size){//小堆if (SChild + 1 < size && a[SChild + 1] < a[SChild]){++SChild;}if (a[SChild] < a[parent]){Swap(&a[SChild], &a[parent]);parent = SChild;SChild = parent * 2 + 1;}else{break;}}
}//删除堆顶数据
void HeapPop(Heap* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;//建堆AdjustDown(php->a, 0, php->size);}//取堆顶数据
HPDataType HeapTop(Heap* php)
{assert(php);assert(php->size > 0);return php->a[0];
}//堆的大小
int HeapSize(Heap* php)
{assert(php);return php->size;
}//是否为空
bool HeapEmpty(Heap* php)
{return php->size == 0;
}//打印函数
void Print(Heap* php)
{assert(php);int i;for (i = 0; i < php->size; ++i){printf("%d ", php->a[i]);}printf("\n");}

test.c

#include "Heap.h"void test1()
{Heap hp;//初始化HeapInit(&hp);Print(&hp);//插入数据HeapPush(&hp, 9);Print(&hp);HeapPush(&hp, 2);Print(&hp);HeapPush(&hp, 7);Print(&hp);HeapPush(&hp, 8);Print(&hp);HeapPush(&hp, 3);Print(&hp);HeapPush(&hp, 1);Print(&hp);HeapPush(&hp, 0);Print(&hp);HeapPush(&hp, 5);Print(&hp);//堆的大小printf("HeapSize = %d\n", HeapSize(&hp));//堆排序while (!HeapEmpty(&hp)){//打印堆顶数据printf("%d ", HeapTop(&hp));//删除堆顶数据HeapPop(&hp);}printf("\n");//销毁HeapDestroy(&hp);
}void test2()
{Heap hp;int arr[] = { 5,11,7,2,3,17 };int sz = sizeof(arr) / sizeof(arr[0]);//用数据初始化HeapCreate(&hp, arr, sz);Print(&hp);//插入数据HeapPush(&hp, 6);Print(&hp);HeapPush(&hp, 9);Print(&hp);//堆的大小printf("HeapSize = %d\n", HeapSize(&hp));//堆排序while (!HeapEmpty(&hp)){//打印堆顶数据printf("%d ", HeapTop(&hp));//删除堆顶数据HeapPop(&hp);}//销毁HeapDestroy(&hp);
}
int main()
{test1();//test2();return 0;
}

测试示例

普通初始化：

用数据初始化：