终于又到了学习二叉树的时间了，今天来讲的是二叉树的堆。
普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。
所以我们就可以有我们堆的存储方式。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。这里的堆又刚好应用于完成二叉树（包括满二叉树）。
引出堆的概念
那堆又分成大堆和小堆。
可以发现小堆就是所有的父亲是小于孩子的，而且我们小堆的根节点是最小的，大堆是所有的父亲节点都是比孩子节点是大的，那我们后面来实现一下，首先我们就拿小堆的方式来实现。
我们这里考虑的是用顺序表的方式来实现，我们可以用顺序表的那一套来用，先定义堆这个结构体。
我们来看看我们是怎么来定义的吧，首先我们都知道我们顺序表定义的时候都是给定一个动态数组，然后加上size是来计数的，也可以来表示这个数的下标，只不过我们要进行减1，因为数组是下标是从0开始的，那我们还要有一个capacity来表示空间是不是够的。
下一个步骤就是我们先要来初始化，这个过程是很重要的，如果不初始化就是随机数，而且我们的数组指向的是个随机地址，这个就是对我们空间内存的非法访问了，所以我们需要对其进行初始化，初始化的函数就是下面这个。
void HeapInit(Heap* php)
{
assert(php);
php->a = NULL;
php->capacity = php->size = 0;
}
因为我们需要动态开辟空间，所以我们肯定要进行对空间进行销毁，首先就是我们的动态数组，然后再给size和capacity进行置0.
void HeapDestory(Heap* php)
{
assert(php);
free(php->a);
php->capacity = php->size = 0;
}
下面就是我们如果对堆进行插入的时候该怎么控制和写，首先我们插入因为是数组，我们为什么用数组就是因为他在尾插的时候是最快的，所以我们就可以用时间复杂度为O（1）的方式进行插入，但是在末尾插入一个随机数，他可能就不是堆，我们需要对这个堆进行调整才行，比如下面的这个图。
比如我们进行插入的是1，那我们这个时候就不是小堆了，因为我们对小堆的定义就是父亲节点是是小于孩子节点的，但是现在这个情况，我们1是最小的，所以需要将他调整到根节点的位置，因为我们很可以看到1是这里面最小的，而我们小堆的根节点就是最小，那我们1是我们的孩子节点，他应该是去和父亲节点进行比较，父亲节点的计算公式就是（child -1） / 2，我们第一次比较就是和56进行比较。
他们需要进行交换。
进行交换之后我们又可以发现的问题就是1和父亲节点比较的时候孩子节点还是最小的，这也提示我们后面要写的是一个循环。我们再次进行交换。
这样我们的小堆就是调整好了，当然这个是最坏的情况，我们也可能不用进行调整的，所以判断条件其实就是我们的孩子节点和父亲节点进行比较就行了。
这次插入就不要进行插入，所以最坏情况就是调整我们的高度此，我们也知道其实高度次该怎么计算，我们的节点是2的h（高度）次方-1，所以我们也可以算出我们这个向上调整方式的时间复杂度就是O（logN），那我们现在来实现一下吧，
void Swap(HeapDateType* p1, HeapDateType* p2)
{
HeapDateType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void AdjustUp(HeapDateType* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[parent] > a[child])
{
Swap(&a[parent], &a[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void HeapPush(Heap* php, HeapDateType x)
{
assert(php);
if (php->capacity == php->size)
{
HeapDateType newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HeapDateType* tmp = (HeapDateType*)realloc(php->a, sizeof(HeapDateType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail\n");
exit(-1);
}
php->a = tmp;
php->capacity = newcapacity;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}
看代码不难发现前面扩容的操作其实就是我们顺序表的方法，那这里就不详解了，我们扩容好就是要进行我们的调整，调整的方式就是上面的代码了，还有就是我们需要注意这里的判断方式，首先就是child>0的时候就得结束了，因为堆这里的本质还是数组，所以我们child==0的时候已经是最坏的情况了。只要我们中途的时候父亲已经小于孩子的时候，我们就可以退出循环了。
有push就有Pop，Pop可不是直接末尾–，而是我们需要删掉小堆的最小值，大堆的最大值，就是根节点，还要保持我们还是一个小堆。
我们可以先进行头和尾的交换，在size–这样就可以把根节点上的位置进行删除了，但是我们这样就不是小堆了，那这个时候我们要进行的操作就是向下调整，就是从根节点开始孩子和父亲进行比较，因为我们是小堆，所以父亲如果比孩子大，我们就进行交换，这样的话到最后的时候我们就又调整成堆，但是还会出现一个问题，父亲有两个节点，我们和那个孩子进行比较才是最合理的呢，答案是和小的，如果和大的比较进行交换之后，父亲还是大于孩子，那我们这样不仅没有用，还会改变原来堆的顺序，所以我们选小的就行，那我们的代码就是下面的这段。
void AdjustDown(HeapDateType* a, int size, int parent)
{
int child = 2 * parent + 1;
while (child < size)
{
if (a[child] > a[child + 1] && child + 1 < size)
{
child++;
}
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
void HeapPop(Heap* php)
{
assert(php);
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a, php->size , 0);
}
这里要注意的第一个小问题就是孩子节点不能越界，因为我们下标最大的是到size-1，传过去的事有几个数，所以我们孩子最多只能到size-1的位置，我们不能访问后面的范围，要不然就是越界了。
写完这个剩下的几个接口函数就是比较好实现的，比如判空，统计个数，还有取出堆顶的元素。
int HeapTop(Heap* php)
{
assert(php);
return php->a[0];
}
int HeapSize(Heap* php)
{
assert(php);
return php->size;
}
bool HeapEmpty(Heap* php)
{
assert(php);
return php->size == 0;
}
完整的代码就是下面的。
Heap.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
typedef int HeapDateType;
typedef struct Heap
{
HeapDateType* a;
int size;
int capacity;
}Heap;
void HeapInit(Heap* php);
void HeapDestory(Heap* php);
void HeapPush(Heap* php, HeapDateType x);
void HeapPop(Heap* php);
int HeapTop(Heap* php);
int HeapSize(Heap* php);
bool HeapEmpty(Heap* php);
Heap.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void HeapInit(Heap* php)
{
assert(php);
php->a = NULL;
php->capacity = php->size = 0;
}
void HeapDestory(Heap* php)
{
assert(php);
free(php->a);
php->capacity = php->size = 0;
}
void Swap(HeapDateType* p1, HeapDateType* p2)
{
HeapDateType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void AdjustUp(HeapDateType* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[parent] > a[child])
{
Swap(&a[parent], &a[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void HeapPush(Heap* php, HeapDateType x)
{
assert(php);
if (php->capacity == php->size)
{
HeapDateType newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HeapDateType* tmp = (HeapDateType*)realloc(php->a, sizeof(HeapDateType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail\n");
exit(-1);
}
php->a = tmp;
php->capacity = newcapacity;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}
void AdjustDown(HeapDateType* a, int size, int parent)
{
int child = 2 * parent + 1;
while (child < size)
{
if (a[child] > a[child + 1] && child + 1 < size)
{
child++;
}
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
void HeapPop(Heap* php)
{
assert(php);
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a, php->size , 0);
}
int HeapTop(Heap* php)
{
assert(php);
return php->a[0];
}
int HeapSize(Heap* php)
{
assert(php);
return php->size;
}
bool HeapEmpty(Heap* php)
{
assert(php);
return php->size == 0;
}
测试代码
Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
int main()
{
Heap hp;
HeapInit(&hp);
int arr[] = { 1,2,13,36,24,12,15,14,11 };
int i = 0;
for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
HeapPush(&hp, arr[i]);
}
while (!HeapEmpty(&hp))
{
printf("%d ", HeapTop(&hp));
HeapPop(&hp);
}
}
虽然我们这是小堆但是要改成大堆其实是很简单的。
我们就直接在原有的基础上改，只需要改的是push和pop就可以了。
改的就是AdjustUp和AdjuestDown，我们来看看
void AdjustDown(HeapDateType* a, int size, int parent)
{
int child = 2 * parent + 1;
while (child < size)
{
if (a[child] < a[child + 1] && child + 1 < size)
{
child++;
}
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
void AdjustUp(HeapDateType* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
就改了三个符号就能解决大堆还是小堆，那讲完堆之后我们再来想想这个到底有什么用，首先就是堆排序，时间复杂度就是O（N*logN），这个我们后面会继续讲，其次就是我们可以用来进行TopK的问题，啥是TopK呢？
我们可以给出这样的一个场景，就是全国不是有很多的美食店，假设我们是一亿家，我们要在这些店内找到最好吃的K家美食点，选的依据是根据他的好评，k是个远小于一亿的一个数字，我们就假设他可以是10，面对这个问题就是我们的topk问题，那这里我们可以用一些数据来代替，我们的问题就是假设我们有一个亿的数字，我们要找出最大十个数，我们该怎么写。
面对上面的问题，大家第一个想法就是我们可以把这一亿个数字插入大堆里面，等全部插入之后，我们是不是就可以找出来了，前十个数就是最大的数，但是这个方法十有缺陷的，我们假设没有这么大的空间，这个方法就是不行的，所以我们的想用另一种方法。
我们可以建设一个小堆，找最大的k个数，这里必须是小堆，然后我们这个堆的大小就只能放k个数，我们放进去的规定就是比这个堆顶的数字大，我们就进行插入，这里再解释一下为什么一定得是小堆，因为小堆的堆顶这个数是最小的，如果是大堆的话，第一个插入的数字是最大的，那我们后面怎么进行插入，同时我们的小堆进行向下调整。
我们前k个数其是就是可以直接插入的，就是按照我们平常的插入，但是只是插满，先构建成小堆的样子。
我们这里只是给大家提供一下思路，因为差生一亿个数字其实挺麻烦的，虽然写个循环就行，但是不好观察，我们就用下面这个例子，给一个数组，找出最大的三个数。
那这样就是k再是3，我们建一个小堆，然后找出前3个最大的数。
#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void AdjustUp(int* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void AdjustDown(int* a, int size, int parent)
{
int child = 2 * parent + 1;
while (child < size)
{
if (a[child + 1] < a[child] && child+1 < size)
{
child++;
}
if (a[parent] > a[child])
{
Swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
int main()
{
int arr[] = { 2,7,4,11,23,9,12,18,14,16,33 };
int k = 3;
int* maxk = (int*)malloc(sizeof(int) * k);
int i = 0;
while (k--)
{
int size = 2 - k;
maxk[size] = arr[i];
i++;
AdjustUp(maxk, size);
}
while (i < sizeof(arr) / sizeof(arr[0]))
{
if (arr[i] > maxk[0])
{
maxk[0] = arr[i];
AdjustDown(maxk, 3, 0);
i++;
}
else
{
i++;
}
}
return 0;
}
我们就可以写这样的一个代码，最后我们通过调试窗口可以发现结果是对的，所以我们可以用这样的思路。
那我们今天的讲解就结束了，后面也会持续更新二叉树等内容，我们下次再见。
文章出处登录后可见！
