初阶数据结构（C语言实现）——5.2 二叉树的顺序结构及堆的实现

1.二叉树的顺序结构及实现

1.1 二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段

左图就是完全二叉树的数组存储
右图是非完全二叉树的数组顺序存储，会造成浪费
数组存储不适合，因为会浪费很多空间。数组存储表示二叉树只适合完全二叉树

• 逻辑结构：想像出来的
• 物理结构：实实在在的在内存中是如何存储

表示二叉树的值在数组位置中父子下标关系:

• parent =(child-1)/2
• leftchild = parent*2+1
• rightchild = parent*2+2

1.2 堆的概念及结构

如果有一个关键码的集合K = { k₀，k₁ ，k₂ ，…，k_n-1 }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： k_i<=k_2*i+1 且 k_i <=k_2*i+2 ( k_i>= k_2*i+1且 k_i>=k_2*i+2 ) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树。

小根堆：树中所有父亲都小于或等于孩子
大根堆：树中所有父亲都大于或等于孩子

1.2.1 堆的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

因此：堆的时间复杂度为O(N)。

1.3 堆的实现思路（均以大顶堆为例后面实现也是）

• 难点：你实际操作的是数组，但是你要会画图，清晰的知道你实现的是二叉树。

typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;
//堆的初始化
void HeapInit(HP* php);
// 堆的插入
void HeapPush(HP* php, HPDataType x);
// 堆的删除
void HeapPop(HP* php);
// 取堆顶的数据
HPDataType HeapTop(HP* php);
// 堆的数据个数
bool HeapEmpty(HP* php);
// 堆的判空
int HeapSize(HP* php);

1.3.0 堆的初始化

初始化，先断言，然后malloc开辟空间，初始化大小和容量

void HeapInit(HP* php)
{assert(php);//断言php->a = (HPDataType*)malloc(sizeof(HPDataType)*4);//开辟初始空间if (php->a == NULL){perror("HeapInit::malloc fail!");return;}php->size = 0;//目前堆内没有数据，所以size = 0php->capacity = 4;//默认初始容量是4
}

1.3.1 堆向上调整算法

• 在数组上看起来是毫无章法的交换数据，但是把二叉树画出来，就清晰的知道为什么这么换。

从孩子向上调整，从刚刚插入的数据位置进行调整
结束条件，是我们的最后交换到堆顶，堆顶结点也就是父亲结点>=0，

• 向上调整算法代码实现

void swap(HPDataType* p1, HPDataType* p2)
{HPDataType x = *p1;*p1 = *p2;*p2 = x;
}void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;//根据孩子位置，计算父亲位置while (child > 0)//child = 0,说明parent不存在了,已经到堆顶了{if (a[child] > a[parent]) //当孩子大小大于父亲大小的时候就交换{swap(&a[child], &a[parent]);//因为其他地方也要用到交换，封装了一个交换函数child = parent; //现在把父亲的值给孩子。parent = (child - 1) / 2;//继续计算现在节点的父亲结点，}else//孩子<=父亲 没必要往上走，直接break就行。		{break;}}
}

1.2.1 堆向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

int array[] = {27,15,19,18,28,34,65,49,25,37};

void swap(HPDataType* p1, HPDataType* p2)
{HPDataType x = *p1;*p1 = *p2;*p2 = x;
}
void AdjustDown(HPDataType* a, int n ,int parent)
{int child = parent*2+1;//根据父亲位置，计算孩子位置while (child <n)//走到没有孩子的时候，结束，{// 选出左右孩子中大的那一个if (child + 1 < n && a[child + 1] > a[child])//必须把child+1<n放前面，否则后面a[child+1]就越界了！{++child;}//交换if (a[child] > a[parent]){swap(&a[child],&a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

1.2.4 堆的插入

先判断是否要扩容
然后进行数据插入
判断是否满足大根堆条件，不满足就要进行交换

• 先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

• 堆的插入代码实现

void HeapPush(HP* php, HPDataType x)
{assert(php);//扩容判断if (php->size == php->capacity){HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);if (tmp == NULL){perror("HeapPush::realloc fail!");return;}php->a = tmp;php->capacity *= 2;}php->a[php->size] = x;	//在数组尾巴插入数据php->size++;//给size++//封装一个调整函数，在函数内判断是否进行交换，交换就直接换。AdjustUp(php->a,php->size-1);
}

• 代码验证，打开调试窗口，在监视1中输入ph.a，5，就能看到我们插入的堆的值。看着数组值自己手动画图，就能看到我们的大顶堆成功实现了。

1.2.5 堆的删除

• 删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

• 堆的删除代码实现

void HeapPop(HP * php)
{assert(php);assert(!HeapEmpty(php));//删除数据//（1）交换堆顶和最后一个数据 直接删掉。swap(&php->a[0], &php->a[php->size-1]);php->size--;//新的堆顶元素向下调整AdjustDown(php->a, php->size,0);
}

1.2.6 其他

HPDataType HeapTop(HP* php)
{assert(php);return php->a[0];
}bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}int HeapSize(HP* php)
{assert(php);return php->size;
}

• 验证。调试，在监控窗口输入：hp.a，3

2 附录：堆的代码实现

2.1 20250312_heap.h

#pragma once
#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 HeapInit(HP* php);
// 堆的插入
void HeapPush(HP* php, HPDataType x);
// 堆的删除
void HeapPop(HP* php);
// 取堆顶的数据
HPDataType HeapTop(HP* php);
// 堆的数据个数
bool HeapEmpty(HP* php);
// 堆的判空
int HeapSize(HP* php);

2.2 20250312_heap.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"20250312_heap.h"void HeapInit(HP* php)
{assert(php);php->a = (HPDataType*)malloc(sizeof(HPDataType)*4);if (php->a == NULL){perror("HeapInit::malloc fail!");return;}php->size = 0;php->capacity = 4;
}void swap(HPDataType* p1, HPDataType* p2)
{HPDataType x = *p1;*p1 = *p2;*p2 = x;
}void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;//根据孩子位置，计算父亲位置while (child > 0)//child = 0,说明parent不存在了,已经到堆顶了{if (a[child] > a[parent]) //当孩子大小大于父亲大小的时候就交换{swap(&a[child], &a[parent]);//因为其他地方也要用到交换，封装了一个交换函数child = parent; //现在把父亲的值给孩子。parent = (child - 1) / 2;//继续计算现在节点的父亲结点，}else//孩子<=父亲 没必要往上走，直接break就行。		{break;}}
}void HeapPush(HP* php, HPDataType x)
{assert(php);//扩容判断if (php->size == php->capacity){HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);if (tmp == NULL){perror("HeapPush::realloc fail!");return;}php->a = tmp;php->capacity *= 2;}php->a[php->size] = x;	//在数组尾巴插入数据php->size++;//给size++//封装一个调整函数，在函数内判断是否进行交换，交换就直接换。AdjustUp(php->a,php->size-1);
}void AdjustDown(HPDataType* a, int n ,int parent)
{int child = parent*2+1;//根据父亲位置，计算孩子位置while (child <n)//走到没有孩子的时候，结束，{// 选出左右孩子中大的那一个if (child + 1 < n && a[child + 1] > a[child])//必须把child+1<n放前面，否则后面a[child+1]就越界了！{++child;}//交换if (a[child] > a[parent]){swap(&a[child],&a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapPop(HP * php)
{assert(php);assert(!HeapEmpty(php));//删除数据//（1）交换堆顶和最后一个数据 直接删掉。swap(&php->a[0], &php->a[php->size-1]);php->size--;//新的堆顶元素向下调整AdjustDown(php->a, php->size,0);
}HPDataType HeapTop(HP* php)
{assert(php);return php->a[0];
}bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}int HeapSize(HP* php)
{assert(php);return php->size;
}

2.3 test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"20250312_heap.h"int main()
{HP hp;HeapInit(&hp);HeapPush(&hp, 1);HeapPush(&hp, 24);HeapPush(&hp, 7);HeapPush(&hp, 9);HeapPush(&hp, 4);HeapPop(&hp);HeapPop(&hp);return 0;
}