实现二叉树_堆

一. 堆的实现

在上一节中我们知道了堆的数据结构，其实就是一种特殊的完全二叉树，堆的底层数据结构就是数组，所以我们就可以定义堆的结构：

//定义堆的结构--数组
typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;int size;//有效的数据个数int capacity;//空间大小
}HP;void HPinit(HP* php);//堆的初始化
void HPdistroy(HP* php);//堆的销毁
void HPPush(HP* php, HPDataType x);//向堆中插入数据
void AdjustUP(HPDataType* arr, int child);//堆的向上调整法
void Swap(HPDataType* x, HPDataType* y);//数据交换
void HPpop(HP* php);//删除数据
void AdjustDown(HPDataType* arr, int parent, int n);//堆的向下调整算法
HPDataType HPTop(HP* php);//取堆顶数据

下面是具体的算法实现：

void HPinit(HP* php)//堆的初始化
{assert(php);php->arr = NULL;php->size = php->capacity = 0;
}void HPdistroy(HP* php)//堆的销毁
{if (php->arr)free(php->arr);php->arr = NULL;php->size = php->capacity = 0;
}void Swap(HPDataType* x, HPDataType* y)//数据交换
{HPDataType tmp = *x;*x = *y;*y = tmp;
}void AdjustUP(HPDataType* arr, int child)//堆的向上调整法
{int parent = (child - 1) / 2;while (child >= 0){if (arr[child] < arr[parent]){Swap(&arr[parent], &arr[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void HPPush(HP* php, HPDataType x) //堆的插入
{assert(php);//判断空间是否足够if (php->size == php->capacity){//扩容{int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = realloc(php->arr, newCapacity * sizeof(HPDataType));if (tmp == NULL){printf("realloc fail!");exit(1);}php->arr = tmp;php->capacity = newCapacity;}}php->arr[php->size] = x;//进行堆的调整 （完成我们的大堆或者小堆）AdjustUP(php->arr, php->size);++php->size;
}//堆的向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;//左孩子while (child<n){//找到左右孩子中的最小值if (child + 1 < n && arr[child] > arr[child + 1]){child++;}if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//在堆中删除数据是删除堆顶的数据，所以在我们删除完一个数据之后还要保持这个堆的结构是原本的小堆或者大堆，还要进行数据调整
void HPpop(HP* php)//删除数据
{assert(php && php->size);//arr[0]   arr[size-1]Swap(&php->arr[0], &php->arr[php->size - 1]);//向下调整算法AdjustDown(php->arr, 0, php->size);--php->size;
}
//判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}HPDataType HPTop(HP* php)//取堆顶数据
{assert(php && php->size);return php->arr[0];
}

上面就是对于堆这样一个数据结构中数据的插入、删除、以及如何完成我们想要的大堆还是小堆等，通过算法一一实现。

二. 向上调整算法

我们在上面的算法中可能会看到一个向上调整算法，这是一个比较重要的算法，用于完成我们想要的数据结构。如何来理解呢?首先我们就拿小堆来举例子，假如我们现在要完成一个小堆的数据结构，我们首先要往一个数组中插入数据：

所以第一步，我们来插入数据，先判断空间是否足够，如果不够的话就扩容，最后再往数组中插入数据，这是比较最基础的步骤，然后再来实现我们要的小堆，这里就需要我们的AdjustUP向上调整算法：

根据上面的图片我们来做对代码的解释，如图所示，我们就拿17 20 10 13 19 15 这几个数字来完成我们的小堆，我们在AdjustUP函数中传入（php->arr, php->size），其实就是指数组，以及传入的最后一个数据，所以当我们传入了两个数据之后，我们就要开始比较了，20是孩子结点，通过计算找到父亲结点，然后比较二者的大小，因为我们这次要完成的是小堆，所以此时两者不用交换，但是当在传入数据10的时候，通过计算发现10<17，要交换。但是如果还继续传入数据的话，我们就要一步步继续向上比较，所以此时我们要让child等于来的parent，parent继续等于（child-1）/2，继续向上比较，直到child小于0，所以我们的while循环条件是（child>=0)，我们来调试一下判断我们的代码是否正确：

由此看出来我们确实实现了小堆的操作，大家可以自己操作实现一下。

三. 向下调整算法

堆的删除的删除堆顶的数据，但是如果直接删除堆顶的数据之后，我们原本的大堆或者小堆的顺序就会改变，可能发生顺序的紊乱，所以如果我们要删除堆中的一个数据的话，也就是出堆，出的是堆顶的数据，我们一般采用的是交换堆顶数据和最末尾的数据：

像上图中的代码一样，先交换堆顶的数据和最末尾的数据，然后删除末尾的数据，也就是把堆顶数据出堆，但是出堆之后的堆并不一定是小堆了，所以我们现在要进行向下调整算法，

void AdjustDown(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;//左孩子while (child<n){//找到左右孩子中的最小值if (child + 1 < n && arr[child] > arr[child + 1]){child++;}if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

取堆顶数据 ：

//判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}HPDataType HPTop(HP* php)//取堆顶数据
{assert(php && php->size);return php->arr[0];
}

四. 堆的应用

那么堆有哪些应用呢？可以用来排序，堆排序。在前面我们学习过对于数据的一些排序方法，比如冒泡排序等，那么如何使用堆来进行排序，并且使空间复杂度为O(1)呢？

//堆排序   不额外开辟空间
void HeapSort(int* arr, int n)
{//建堆//升序----大堆//降序----小堆for (int i = 0; i < n; i++){AdjustUP(arr,i);}//循环的将堆顶数据与最后位置数据进行交换int end = n - 1;while (end>0){Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}
}
int main()
{//test01();//给定一个数据，随数组中的数据进行排序int arr[] = { 17,20,10,13,19,15 };HeapSort(arr, 6);for (int i = 0; i < 6; i++){printf("%d ", arr[i]);}printf("\n");return 0;
}