【数据结构】二叉树-堆

堆分为：

• 小根堆
• 大根堆

小根堆： 父节点的元素小于或等于左右子结点的元素。
大根堆： 父节点的元素大于或等于左右子节点的元素。

这里我们一大根堆为例。

//.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<time.h>typedef int HPDataType;typedef struct Heap
{HPDataType* arr;int size;int capacity;
}HP;void HPInit(HP*php);//堆初始化
void HPDestory(HP*php);//堆的销毁void HPPush(HP*php,HPDataType x);//堆插入数据
void HPPop(HP*php);//出堆
bool HPEmpty(HP*php);//判断堆是否为空
HPDataType HPTop(HP*php);//获取堆顶元素
HPDataType HPSize(HP*php);//堆中数据个数void AdjustDown(HPDataType* arr, int parent, int n);
void AdjustUp(HPDataType* arr, int child);
void Swap(int* x, int* y);

//.c
#include"Heap.h"void HPInit(HP* php)//堆初始化
{assert(php);php->arr = NULL;php->capacity = php->size = 0;
}void HPDestory(HP* php)//堆的销毁
{assert(php);if (php->arr){free(php->arr);}php->arr = NULL;php->capacity = php->size = 0;
}void Swap(int*x,int*y)
{int tmp = *x;*x = *y;*y = tmp;
}void AdjustUp(HPDataType*arr,int child) 
{assert(arr);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->capacity==php->size){int newnode = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->arr,newnode*sizeof(HPDataType));assert(tmp);php->arr = tmp;php->capacity = newnode;}php->arr[php->size] = x;AdjustUp(php->arr,php->size);php->size++;
}void AdjustDown(HPDataType*arr,int parent,int n)
{assert(arr);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);Swap(&php->arr[0],&php->arr[php->size-1]);--php->size;AdjustDown(php->arr,0,php->size);
}bool HPEmpty(HP* php)//判断堆是否为空
{assert(php);return php->size == 0;
}HPDataType HPTop(HP* php)//获取堆顶元素
{assert(php);return php->arr[0];
}HPDataType HPSize(HP* php)//堆中数据个数
{assert(php);return php->size;
}