C语言手写堆｜从定义到排序，一篇带你搞定所有接口！

一、定义一个堆

#pragma once typedef int HPDataType; #include<stdio.h> #include<stdlib.h> typedef struct Heap { //堆的本质是树 //要用数组存储 HPDataType* _a; int _size; int _capacity; }Heap;

二、常见接口

void HeapInit(Heap* php, HPDataType* a, int n); void HeapDEstory(Heap* php); void HeapPush(Heap* php, HPDataType x); void HeapPop(Heap* php); HPDataType HeapTop(Heap* php);

三、向下调整算法

//前提：左右子树都是小堆 void AdjustDown(HPDataType* a, int n,int root) { int parent = root; int child = parent * 2 + 1; while(child<n) { //1.找出左右孩子中小的那一个 // 因为不是换一下左右就完了 // 以后还要以这个孩子为根进行交换 //所以默认为左孩子 if (child+1<n && a[child + 1] < a[child]) child++; //2.如果小的那个孩子比父亲还小，就交换 if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else break; } }

四、初始化

void HeapInit(Heap* php, HPDataType* a, int n) { php->_a = (HPDataType*)malloc(sizeof(HPDataType) * n); //malloc很难失败 //此处省略检查，不过严谨起见，最好加上 php->_size = n; php->_capacity = n; //把数组a拷贝进堆中 memcpy(php->_a, a, sizeof(HPDataType) * n); //数组一上来还不是堆，要构建堆 int i = 0; for (i=(n - 1 - 1) / 2;i>=0;i--) AdjustDown(php->_a, php->_size, i); }

五、堆排序

int HeapSort(int* a,int n) { int a[] = { 2,3,4,3,5 }; //1.建堆 //for (int i=n-l;i>= 0;++i) //时间复杂度？ //假设树有N个节点，树高度：1ogN //要注意这里时间复杂度不是N * 1ogN，他的时间复杂度是O（N） int i = 0; for (i = (n - 1 - 1) / 2;i >= 0;i--) AdjustDown(a, n, i); int end = n - 1; while (end>0) { //交换堆顶数据和最后一个数据 Swap(&a[0], &a[end]); //再继续选次小的 AdjustDown(a, end, 0); end--; } }

六、堆的销毁

void HeapDestory(Heap* php) { assert(php); free(php->_a); php->_a = NULL; php->_capacity = php->_size = 0; }

七、插入数据

void HeapPush(Heap* php, HPDataType x) { assert(php); if (php->_size == php->_capacity) { php->_capacity *= 2; HPDataType* tmp = (HPDataType*)realloc\ (php->_a,sizeof(HPDataType) * php->_capacity); php->_a = tmp; } php->_a[php->_size++] = x; AdjustUp(php->_a, php->_size, php->_size - 1); }

如图：向上比较调整