系列文章目录
提示：写完文章后，目录可以自动生成，如何生成可参考右边的帮助文档
文章目录
- 一、什么是树？
- 一、什么是堆？
- 三、堆的实现
- 总结
一、什么是树？
树是一种数据结构，它是由n(n≥0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
1.每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。
2.孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
3.节点的度：一个节点含有的子节点的个数称为该节点的度；
4.叶节点或终端节点：度为0的节点称为叶节点；
5.非终端节点或分支节点：度不为0的节点；
6.双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
7.兄弟节点：具有相同父节点的节点互称为兄弟节点；
8.树的度：一棵树中，最大的节点的度称为树的度；
9.节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
10.树的高度或深度：树中节点的最大层次；
二、什么是堆？
1.堆(Heap)是计算机科学中一类特殊的数据结构，是最高效的优先级队列。堆通常是一个可以被看做一棵完全二叉树的数组对象。
2.它有以下性质：
1）堆总是一棵完全二叉树。
2）堆中某个结点的值总是不大于（大根堆）或不小于（小根堆）其父结点的值。（具体
2）将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。（如图所示）
接下来我们用数组实现堆：
三、堆的实现
头文件
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>构建堆
typedef int HPDatatype;
typedef struct Heap
{
HPDatatype* a;//类型的指针-指针构建数组
int size;//数量
int capacity;//容量
}HP;各类功能
void HeapPrint(HP* php);//打印
void HeapInit(HP* php);//初始化
void HeapDestory(HP* php);//销毁
void HeapPush(HP* php, HPDatatype x);//插入
void HeapPop(HP* php);//删除
int HeapTop(HP* php);//取头
bool HeapEmpty(HP* php);//验满
int HeapSize(HP* php);//个数
void Adjustup(HPDatatype* a, int child);//向上调整-插入数据时用
void Adjustdown(HPDatatype* a, int n, int parent);//向下调整-删除
void swap(HPDatatype* x, HPDatatype* y);//交换函数打印
void HeapPrint(HP* php)//打印
{
for (int i = 0; i < php->size; ++i)
{
printf("%d ", php->a[i]);
printf("\n");
}
}初始化
void HeapInit(HP* php)//初始化
{
assert(php);
php->size = php->capacity = 0;
php->a = NULL;
}销毁
void HeapDestory(HP* php)//销毁
{
assert(php);
free(php->a);
php->a = NULL;
php->capacity = php->size = 0;
}插入
void HeapPush(HP* php, HPDatatype x)//插入
{
assert(php);
if (php->size == php->capacity)
{
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDatatype* tmp = (HPDatatype*)realloc(php->a,sizeof(HPDatatype) * newcapacity);
if (tmp==NULL)
{
perror("realloc failed");
exit(-1);
}
php->capacity = newcapacity;
php->a = tmp;
}
php->a[php->size] = x;
php->size++;
Adjustup(php->a, php->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);
}取头
int HeapTop(HP* php)//取头
{
assert(php);
assert(!HeapEmpty(php));
return php->a[0];
}验满
bool HeapEmpty(HP* php)
{
return php->size==0;
}个数
int HeapSize(HP* php)//个数
{
return php->size;
}向上调整(一般插入时使用）
void Adjustup(HPDatatype* a, int child)//向上调整
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])//大根堆用>，小根堆用<
{
swap(&a[child], &a[parent]);
child = parent;
int parent = (child - 1) / 2;
}
else
{
break;
}
}
}向下调整（一般删除时使用）
void Adjustdown(HPDatatype* a, int n,int parent)//向下调整
{
int minchild = 2 * parent + 1;
while (minchild < n)
{
if (minchild+1<n &&a[minchild + 1] > a[minchild])//第二个大于号：大根堆用>，小根堆用<
{
minchild++;
}
if (a[minchild] > a[parent])//大根堆用>，小根堆用<
{
swap(&a[minchild], &a[parent]);
parent = minchild;
int minchild = 2 * parent + 1;
}
else
{
break;
}
}
}交换函数
void swap(HPDatatype* x, HPDatatype* y)//交换
{
HPDatatype tmp = *x;
*x = *y;
*y = tmp;
}总结
学习二叉树-堆这部分的时间是我学c以来最困难时期，可见这部分难度跨越不小，我花费了不少时间理解，希望你也能克服困难，共勉加油！！！