main.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Heap.h" //堆的测试 void HeapTest() { Heap hp = {0}; HeapCreat(&hp); HeapPush(&hp, 10); HeapPush(&hp, 18); HeapPush(&hp, 19); HeapPush(&hp, 25); HeapPush(&hp, 28); HeapPush(&hp, 43); HeapPush(&hp, 65); HeapPush(&hp, 49); HeapPush(&hp, 27); HeapPush(&hp, 37); HeapPop(&hp); HeapPrint(&hp); HeapDestory(&hp); } //堆排序 void HeapSort(int* a, int size) { Heap hp; HeapCreat(&hp); for (int i = 0; i < size; ++i) { HeapPush(&hp, a[i]); } size_t j = 0; while (!HeapEmpty(&hp)) { a[j] = HeapTop(&hp); j++; HeapPop(&hp); } HeapDestory(&hp); } int main() { //TestHeap(); int a[] = { 4, 2, 7, 8, 5, 1, 0, 6 }; HeapSort(a, sizeof(a) / sizeof(int)); for (int i = 0; i < sizeof(a) / sizeof(int); ++i) { printf("%d ", a[i]); } printf("\n"); return 0; }
咱主要讲Heap.c所需要讲解的部分
主要讲解部分
下方是结构题的内容
typedef struct Heap { HPDataType* data;//用于储存数据 size_t size; //大小 size_t capacity;//容量 }Heap;
实话实说需要重点讲解的主要是两个函数.
其中
void AdJustUp(Heap* obj) { size_t child = obj->size-1; size_t parent = (child - 1) / 2; while (child) { if (obj->data[parent] > obj -> data[child]) { HPDataType tmp = obj->data[child]; obj->data[child] = obj->data[parent]; obj->data[parent] = tmp; child = parent; parent = (child - 1) / 2; } else { break; } } }
这个函数是嵌套在HeapPush中的一个用于调整数据位置的函数,我们在HeapPush的时候是将数据直接放在我们顺序表的末尾处,然后通过AdJustUp函数对数据进行调整.将本来插入后可能不是堆情况调整成堆的格式.
我们通过图来了解这种情况: 比如我们的数值原来有着: 2 3 5 6 7 8
这时我们插入一个1来看看我们的AdJustUp函数是如何将顺序表的储存情况重新换成堆形势.
其实很简单我们通过while循环和if语句来判断末尾部的父亲是否大于我们要改变位置的节点如果大于就交换他们的位置如果小于就直接进行break语句跳出循环即可.
然后使我们的向下调整函数.
void AdJustDown(Heap* obj) { size_t father = 0; size_t child = father*2+1;//得到的是左孩子 while (child < obj->size) { //选出最小的孩子 if (child+1<obj->size&&obj->data[child] > obj->data[child + 1]) { child++; } if (obj->data[child] < obj->data[father]) { HPDataType tmp = obj->data[child]; obj->data[child] = obj->data[father]; obj->data[father] = tmp; father = child; child = father * 2 + 1; } else { break; } } } void HeapPop(Heap* obj) { assert(obj); assert(obj->size > 0); obj->data[0] = obj->data[obj->size - 1]; obj->size--; AdJustDown(obj); }
我们的向下调整函数也是在HeapPop函数内作为内嵌(至于为啥要把向下调整专门分装成一个函数,我个人认为是为了代码的整洁性吧).
HeapPop 的功能是删除顺序表的定元素也就是下标为0的元素,但是我们如果先将下标为0的元素换成我们在尾的元素然后进行对size进行--即可.
然后我们即可进行向下调整的操作.
老样子我们使用图文调整的形式给大家展示.
我们先比较左右还在的大小选一个最小的与父亲节点交换在只有一个孩子的情况至于左孩子比较即可👍.
结尾
这部分的代码实现其实也挺简单的,我们想用堆排序也只需要从得到头元素然后删头只要堆为空即可👍.
