当前位置: 首页> 文旅> 旅游 > 手搓堆(C语言)

手搓堆(C语言)

时间:2025/7/10 20:37:34来源:https://blog.csdn.net/m0_62646213/article/details/138414492 浏览次数:0次

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;
}

测试示例

普通初始化:

用数据初始化:

关键字:手搓堆(C语言)

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: