Hello，我们又见面了，今天讲的是堆，是数据结构里的堆，可不是我们C语言的堆区那个，今天这篇文章我们写一个数组堆，然后实现堆排序的功能，废话不多说，开始我们今天的学习吧！！
堆的概念与性质
堆是计算机中的一类特殊的数据结构的统称。堆通常是可以被看做一颗完全二叉树的数组对象.
堆的性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树。
堆又分为大小堆，大堆的特点就是父亲是最大的，后面我会补文章来讲解数的一些概念，小堆就是父亲是最小的
举列子给大家看可能更好的理解。
上面的是小堆，因为我们的父亲最小，下面的是大堆，父亲是最大的数
那我们有没有想过堆的作用是什么
第一个作用就是解决堆排序的问题，我们可以用它来排序数组，因为数组是我们的物理结构，但是不是任何数组都可以用来排序的，我们还得满足它的逻辑结构，那就是左右必须得是子数，满足大小堆的结构.
那我们先来实现一个数组堆，和之前的顺序表和链表一样，我们有我们的结构。
typedef int HeapDataType; typedef struct Heap { HeapDataType* arry; int size; int capacity; }Heap;
这么一看我们定义的结构体就是我们顺序表定义过的结构体！！！
那我们的接口函数实现
typedef int HeapDataType; typedef struct Heap { HeapDataType* arry; int size; int capacity; }Heap; void HeapInit(Heap* php); void HeapDestory(Heap* php); void HeapPrint(Heap* php); bool HeapEmpty(Heap* php); void HeapPush(Heap* php, HeapDataType x); void HeapPop(Heap* php); HeapDataType HeapTop(Heap* php); int HeapSize(Heap* php);
那我们一个一个来实现吧，首先就是我们的初始化堆，这个很简单，和顺序表一摸一样的操作就可以实现，我们来看一下吧
void HeapInit(Heap* php) { assert(php); php->arry = NULL; php->capacity = php->size = 0; }
这个应该很简单来了，对于我们来说，不懂可以看前面的文章去看看
有了初始化就有销毁，销毁的时我们动态开辟的空间。我们也来实现一下吧
void HeapDestory(Heap* php) { assert(php); free(php->arry); }
现在我们继续实现堆打印的函数
void HeapPrint(Heap* php) { assert(php); int i = 0; for (i = 0; i < php->size; i++) { printf("%d ", php->arry[i]); } printf("\n"); }
遍历一遍数组其实就能实现，因为我们的物理结构就是数组，所以这里很简单，接下来就是怎么放入数组，这个有点难里面有好几个接口函数需要我们手动实现，这里我们拿小堆升序来讲
首先我们插入，应该是从他的尾巴插入，就是数组最后一个，插入的话，我们是不是需要实现一个接口函数检查受否要扩容，检查这个扩容我们已经实现过好几次了，这里我就不讲解了，然后我们需要把要插入的数放进去，size++就行了，但是插入一个数之后，二叉数堆就不是我们之前的小堆，需要进行调整，这里我们就用一个巧妙的方法，向上调整，调整我们的数到合适位置，调整比较的是它的祖先，而不是随意的进行比较，因为我们的堆是小堆，所以这个数如果比他的祖先小，就需要进行调整，最坏的就是这个数是最小的，这时候我们要给定一个条件来结束调整。那我们先来看一下完整的代码吧
void swap(HeapDataType* p1, HeapDataType* p2) { HeapDataType tmp = *p1; *p1 = *p2; *p2 = tmp; } void Adjustup(HeapDataType* arry, int child) { int parent = (child - 1) / 2; while (child > 0) { if (arry[child] < arry[parent]) { swap(&arry[child], &arry[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } void HeapPush(Heap* php, HeapDataType x) { assert(php); if (php->capacity == php->size) { int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2; HeapDataType* tmp = (HeapDataType*)realloc(php->arry, sizeof(HeapDataType) * newcapacity); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } php->arry = tmp; php->capacity = newcapacity; } php->arry[php->size] = x; php->size++; Adjustup(php->arry, php->size - 1); }
这就是我们的调整，我们走读代码来到调整的部分，我们比较的是父亲和孩子，如果孩子比父亲小就进行交换，反之退出循环，还可以用递归的方法来写，但是一般情况下堆不会使用。
有了数据的插入就有数据的删除，来看看删除的向下调整，也是同样的思路。
void AdjustDown(HeapDataType* arry, int size, int parent) { int child = 2 * parent + 1; if (child+1<size && arry[child + 1] < arry[child]) { child++; } while (child < size) { if (arry[parent] > arry[child]) { swap(&arry[parent], &arry[child]); parent = child; child = 2 * parent + 1; } else { break; } } } void HeapPop(Heap* php) { assert(php); assert(php->size > 0); swap(&(php->arry[0]), &(php->arry[php->size - 1])); php->size--; AdjustDown(php->arry, php->size, 0); }
这个内容主要就是讲pop和push这两个，其他结构函数这里小编一并实现了，不是特别难，我们来看看吧
HeapDataType HeapTop(Heap* php) { assert(php); return php->arry[0]; } int HeapSize(Heap* php) { assert(php); return php->size; }
这两个一个是取出堆顶的数，就是我们的根，第二个是个数。
还有与一个判断堆是否是空的函数，让我们一起来看看吧
bool HeapEmpty(Heap* php) { assert(php); return php->size == 0; }
完整代码
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int HeapDataType; typedef struct Heap { HeapDataType* arry; int size; int capacity; }Heap; void HeapInit(Heap* php); void HeapDestory(Heap* php); void HeapPrint(Heap* php); bool HeapEmpty(Heap* php); void HeapPush(Heap* php, HeapDataType x); void HeapPop(Heap* php); HeapDataType HeapTop(Heap* php); int HeapSize(Heap* php);
#include"Heap.h" void HeapInit(Heap* php) { assert(php); php->arry = NULL; php->capacity = php->size = 0; } void HeapDestory(Heap* php) { assert(php); free(php->arry); } void HeapPrint(Heap* php) { assert(php); int i = 0; for (i = 0; i < php->size; i++) { printf("%d ", php->arry[i]); } printf("\n"); } bool HeapEmpty(Heap* php) { assert(php); return php->size == 0; } void swap(HeapDataType* p1, HeapDataType* p2) { HeapDataType tmp = *p1; *p1 = *p2; *p2 = tmp; } void Adjustup(HeapDataType* arry, int child) { int parent = (child - 1) / 2; while (child > 0) { if (arry[child] < arry[parent]) { swap(&arry[child], &arry[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } void HeapPush(Heap* php, HeapDataType x) { assert(php); if (php->capacity == php->size) { int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2; HeapDataType* tmp = (HeapDataType*)realloc(php->arry, sizeof(HeapDataType) * newcapacity); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } php->arry = tmp; php->capacity = newcapacity; } php->arry[php->size] = x; php->size++; Adjustup(php->arry, php->size - 1); } void AdjustDown(HeapDataType* arry, int size, int parent) { int child = 2 * parent + 1; if (child+1<size && arry[child + 1] < arry[child]) { child++; } while (child < size) { if (arry[parent] > arry[child]) { swap(&arry[parent], &arry[child]); parent = child; child = 2 * parent + 1; } else { break; } } } void HeapPop(Heap* php) { assert(php); assert(php->size > 0); swap(&(php->arry[0]), &(php->arry[php->size - 1])); php->size--; AdjustDown(php->arry, php->size, 0); } HeapDataType HeapTop(Heap* php) { assert(php); return php->arry[0]; } int HeapSize(Heap* php) { assert(php); return php->size; }
懒得去测试了，大家就这样看看吧，那今天的分享就到这里，我们后面讲讲怎么用堆来实现堆排序吧
