目录
1.堆的概念及结构
普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段
1.1概念
堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。
?将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。堆是非线性数据结构，相当于一维数组，有两个直接后继。
?
拓展规律
1.2性质
?1.堆中某个节点的值总是不大于或不小于其父节点的值；2.堆总是一棵完全二叉树。
?2.堆的实现
2.1定义堆
typedef int HPDataType;
//定义大堆
typedef struct Heap
{
HPDataType* a;
int size;
int capacityl;
}HP;2.2向下调整
int array[] = {27,15,19,18,28,34,65,49,25,37};
?前提：左子树是小堆，右子树也是小堆
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p2 = *p2;
*p2 = tmp;
}
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
//选出左右孩子中小的那一个
if (child+1<n && a[child + 1] < a[child])//childe+1<n用于判断右孩子是否存在，因为完全二叉树可能没有右孩子
{
++child;
}
if (a[child] < a[parent])
{
Swap(&a[child], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
int main()
{
int a[] = { 27,15,19,18,28,34,65,49,25,37 };
int n = sizeof(a) / sizeof(a[0]);
AdjustDown(a, n, 0);
return 0;
}
1.往堆顶插入新元素5
?
2.元素5跟左右孩子中小的那个进行比较，若比他大，就交换
?
?3.继续与左右孩子中小的进行比较，若更大，就交换
?4.继续比较，发现并不会比孩子节点小，跳出循环，新的小堆调整结束。
问题：左右子树不是小堆怎么办
倒数的第一个非子叶结点即为最后一个结点的父亲
主函数代码中加入建堆函数即可
//建堆
for (int i = (n-1-1)/2;i>=0;--i)
{
AdjustDown(a, n, i);
}
问题：排升序，建大堆还是小堆？->建大堆
已知建堆的时间复杂度O(N)
为什么不能建小堆?
为什么建大堆？
//排升序，
void HeapSort(int* a, int n)
{
//建堆
for (int 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;
}
}
2.3向上调整
void AdjustUp(int* a, int child)
{
int parent = (child - 1) / 2;
//while (parent >= 0) 不对的 parent不会小于0
while (child > 0)
{
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}?从叶子节点插入一个元素后，想要继续保持堆的结构不变。从下往上，对二叉树进行调整，确保最后是小堆。
图示过程如下：
1.未进行插入新元素的堆：
2.新元素0
3.新元素0跟此时的父亲节点5比较，比5小，交换
4.然后0继续和新的父亲节点2比较，比2小，交换
5.然后0继续和新的父亲节点0进行比较，比1小，交换
2.4堆的初始化
这里以建立小堆为例，我们需要保证小堆的结构，这里通过自下而上进行调整。
这里提一嘴为什么建堆过程中的for循环内i初始值设置为（n-1-1）/2，首先数组最后一个元素下标是n-1,又有child=2*parent+1,带入后就是这个初始值。
void HeapInit(HP* php, HPDataTpye* a, int n)
{
assert(php);
php->a = (HPDataTpye*)malloc(sizeof(HPDataTpye)*n);
if (php->a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
memcpy(php->a, a, sizeof(HPDataTpye)*n);
// 建堆
for (int i = (n-2)/2; i >= 0; --i)
{
AdjustDown(php->a, n, i);
}
php->size = n;
php->capacity = n;
}2.5堆的销毁
直接free掉a，然后把php->a置空，并把size和capacity置0
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}2.6堆的插入操作
1.先判断下空间是否满了，若满了，realloc开辟一块新的空间，没满就不需要开辟。
2.然后把新插入的元素放在最后一个叶子节点处
3.接下来与其双亲结点进行比较,如果比双亲结点小,就交换其值,一直不断重叠
4.最后如果该数据比双亲结点值大,就结束调整;如果当child等于0,就结束调整
// 插入x，保持他继续是堆
void HeapPush(HP* php, HPDataTpye x)
{
assert(php);
if (php->size == php->capacity)
{
HPDataTpye* tmp = (HPDataTpye*)realloc(php->a, php->capacity * 2 * sizeof(HPDataTpye));
if (php->a == NULL)
{
printf("realloc fail\n");
exit(-1);
}
php->capacity *= 2;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}2.7堆的删除操作
该函数的作用是删除堆顶元素,并且不能毁坏堆结构。借助堆排序的思想,直接把堆顶第一个元素和堆底第一个元素交换，然后php->size减1，再调用一次自上而下的排序，因为size减1了，相当于除了原本堆顶第一个元素以外的元素进行调整。
// 删除堆顶数据，删除后保持他继续是堆
void HeapPop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
Swap(&php->a[0], &php->a[php->size - 1]);
--php->size;
AdjustDown(php->a, php->size, 0);
}2.8获取堆顶元素
// 获取堆顶的数据，也就是最值
HPDataTpye HeapTop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
return php->a[0];
}2.9堆的判空操作
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}2.10堆内元素数量
int HeapSize(HP* php)
{
assert(php);
return php->size;
}2.11打印堆
void HeapPrint(HP* php)
{
for (int i = 0; i < php->size; ++i)
{
printf("%d ", php->a[i]);
}
printf("\n");
}