文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >【数据结构】顺序结构二叉树详解

【数据结构】顺序结构二叉树详解

作者头像
小年糕是糕手
发布于 2026-01-14 17:20:04
发布于 2026-01-14 17:20:04
240
举报
文章被收录于专栏：C++学习C++学习

一般堆使用顺序结构的数组来存储数据，堆是一种特殊的二叉树，具有二叉树的特性的同时，还具备其他的特性。

一、堆的概念与结构

如果有一个关键码的集合 K={k0​,k1​,k2​,…,kn−1​}，把它的所有元素按完全二叉树的顺序存储方式存储，在一个一维数组中，并满足：Ki​ <= K(2∗i + 1)​（Ki ​>= K(2 ∗ i + 1)​且Ki​ <= K(2 ∗ i + 2)​，i = 0、1、2...，则称为小堆 (或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆

堆具有以下性质

  • 堆中某个结点的值总是不大于或不小于其父结点的值；
  • 堆总是一棵完全二叉树。
  • 堆顶是最值（最大值 / 最小值）

二叉树性质

  • 对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从 0 开始编号，则对于序号为 i 的结点有：
    1. 若 i>0，i 位置结点的双亲序号：(i−1)/2；i=0，i 为根结点编号，无双亲结点
    2. 若 2i+1<n，左孩子序号：2i+1，2i+1>=n 否则无左孩子
    3. 若 2i+2<n，右孩子序号：2i+2，2i+2>=n 否则无右孩子

这里我们给出手绘的示意图来加强理解

二、堆的实现
2.1、Heap.h
代码语言：javascript
复制
#pragma once
#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//定义堆结构
typedef int HPDataType;

typedef struct Heap {
	HPDataType* arr;
	int size;//有效数据个数
	int capacity;//空间大小
}HP;

//堆的初始化
void HPInit(HP* php);

//堆的销毁
void HPDesTroy(HP* php);

//交换数据
void Swap(int* x, int* y);

//向上调整算法
void AdjustUp(HPDataType* arr, int child);

//向下调整算法
//n是堆里面的结点个数，如果越界了就不需要调整了
void AdjustDown(HPDataType* arr, int parent, int n);

//打印堆
void HPPrint(HP* php);

//往堆里插入数据
void HPPush(HP* php, HPDataType x);

//删除数据
void HPPop(HP* php);

//判断堆是否为空
bool HPEmpty(HP* php);

//取堆顶
HPDataType HPTop(HP* php);
2.2、Heap.c
代码语言：javascript
复制
#include"Heap.h"

//堆的初始化
void HPInit(HP* php)
{
	assert(php);
	php->arr = NULL;
	php->size = php->capacity = 0;
}

//堆的销毁
void HPDesTroy(HP* php)
{
	assert(php);
	if (php->arr)
		free(php->arr);
	php->arr = NULL;
	php->size = php->capacity = 0;
}

//打印堆
void HPPrint(HP* php)
{
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->arr[i]);
	}
	printf("\n");
}

//交换数据
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//向上调整算法
void AdjustUp(HPDataType* arr, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		//建大堆: >
		//建小堆: <
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			//不用调整符合情况
			break;
		}
	}
}

//向下调整算法
//n是堆里面的结点个数，如果越界了就不需要调整了
void AdjustDown(HPDataType* arr, int parent, int n)
{
	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 HPPush(HP* php, HPDataType x)
{
	assert(php);
	//空间不够要增容
	if (php->size == php->capacity)
	{
		//增容
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->arr, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		php->arr = tmp;
		php->capacity = newcapacity;
	}
	//空间足够
	php->arr[php->size] = x;
	php->size++;
	//向上调整
	//数组下标是从0开始的,所以要size - 1
	AdjustUp(php->arr, php->size - 1);
}

//判断堆是否为空
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

//出堆顶
//先让堆顶与最后一个数据交换，然后size--
//找child中较大的一个与parent交换，以此类推
void HPPop(HP* php)
{
	assert(!HPEmpty(php));
	Swap(&php->arr[0], &php->arr[php->size - 1]);
	--php->size;
	//堆顶数据需要向下调整
	AdjustDown(php->arr, 0, php->size);
}

//取堆顶
HPDataType HPTop(HP* php)
{
	assert(!HPEmpty(php));
	return php->arr[0];
}
2.3、test.c
代码语言：javascript
复制
#include"Heap.h"

void test01()
{
	HP hp;
	HPInit(&hp);

	HPPush(&hp, 25);
	HPPush(&hp, 15);
	HPPush(&hp, 10);
	HPPush(&hp, 80);
	HPPrint(&hp);

	while (!(HPEmpty(&hp)))
	{
		int top = HPTop(&hp);
		printf("%d ", top);
		HPPop(&hp);
	}


	HPPop(&hp);
	HPPrint(&hp);


	HPDesTroy(&hp);
}

//冒泡排序
void BubbleSort(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				Swap(&arr[j], &arr[j + 1]);
			}
		}
	}
}


//堆排序 -- 这不是真的堆排序
//这直接使用了数据结构中的堆
void HeapSort01(int* arr, int n)
{
	HP hp;//-------使用了数据结构 -- 堆
	HPInit(&hp);

	//调用push将数组中的数据放入到堆中
	for (int i = 0; i < n; i++)
	{
		HPPush(&hp, arr[i]);
	}
	//得到了一个堆结构
	int i = 0;
	while (!HPEmpty(&hp))
	{
		int top = HPTop(&hp);
		arr[i++] = top;
		HPPop(&hp);
	}
	HPDesTroy(&hp);
}

//堆排序 -- 使用堆结构的思想来进行堆排序
void HeapSort02(int* arr, int n)
{
	//乱序数组 -- 建堆
	//先从最后一个结点开始开始调整，假设有6个数据，数组第一个元素下标是0
	//最后一个数据的下标便是5,即n-1,我们要根据孩子求父亲便是(k - 1)/2,这里的k是n - 1
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, n);
	}

	////向上调整算法
	//for (int i = 0; i < n; i++)
	//{
	//	AdjustUp(arr, i);
	//}

	//拿堆顶和最后一个数据进行交换,然后向下调整
	//这里的例子是排降序,建的小堆
	//如果要排升序,我们要去建大堆
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		end--;
	}
}

int main()
{
	//test01();

	int arr[6] = { 25,15,10,56,70,30 };
	printf("排序之前: \n");
	for (int i = 0; i < 6; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	HeapSort02(arr, 6);
	printf("排序之后: \n");
	for (int i = 0; i < 6; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");

	return 0;
}

这里我们重点关注Heap.c文件，我们来详解一下向上调整算法和向下调整算法：

2.4、向上调整算法

这个我们是在"堆的插入"里使用到的：

将新数据插入到数组的尾上，再进行向上调整算法，直到满足堆。

向上调整算法

  • 先将元素插入到堆的末尾，即最后一个孩子之后
  • 插入之后如果堆的性质遭到破坏，将新插入结点顺着其双亲往上调整到合适位置即可
代码语言：javascript
复制
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;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void HPPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size - 1);
}

计算向上调整算法建堆时间复杂度：

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

由此可得：

向上调整算法建堆时间复杂度为：O(n ∗ log ​n)（log是以2为底）

2.5、向下调整算法

这个我们是在"堆的删除"里使用到的：

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

向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

向下调整算法

  • 将堆顶元素与堆中最后一个元素进行交换
  • 删除堆中最后一个元素
  • 将堆顶元素向下调整到满足堆特性为止
代码语言：javascript
复制
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;
		}
		if (a[child] > a[parent])
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size, 0);
}

计算向下调整算法建堆时间复杂度：

向下调整算法建堆时间复杂度为：O(n)

三、堆的应用
3.1、堆的排序
版本一：基于已有数组建堆、取堆顶元素完成排序版本
代码语言：javascript
复制
// 1、需要堆的数据结构
// 2、空间复杂度 O(N)
void HeapSort(int* a, int n)
{
	HP hp;
	for (int i = 0; i < n; i++)
	{
		HPPush(&hp, a[i]);
	}
	int i = 0;
	while (!HPEmpty(&hp))
	{
		a[i++] = HPTop(&hp);
		HPPop(&hp);
	}
	HPDestroy(&hp);
}

该版本有一个前提，必须提供有现成的数据结构堆

版本二：数组建堆，首位交换，交换后的堆尾数据从堆中删掉，将堆顶数据向下调整选出次大的数据
代码语言：javascript
复制
// 升序，建⼤堆
// 降序，建⼩堆
// O(N*logN)
void HeapSort(int* a, int n)
{
	// a数组直接建堆 O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}
	// O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

堆排序时间复杂度计算：

堆排序时间复杂度为：O(n * logn)

3.2、TOP-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 

假设现在有10亿个整数，需要申请多大内存？ 1G = 1024 MB = 1024 * 1024 KB = 1024 * 1024 *1024 byte，10亿 * 4 = 4G 假设只有1G内存怎么办？ 这时候我们可能会想到采用循环的方式来利用那1G内存，那假设现在只有1KB内存怎么办？

图解：创建一个堆，堆中只有k个数据，我们建小堆，遍历剩下的n - k个数据，比堆顶要大就和堆顶交换。 要是找最小的前k个数据，建大堆，遍历剩下的数据和堆顶比，比堆顶要大就和堆顶交换。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了 (可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1）用数据集合中前 K 个元素来建堆前 k 个最大的元素，则建小堆前 k 个最小的元素，则建大堆 2）用剩余的 N-K 个元素依次与堆顶元素来比较，不满足则替换堆顶元素将剩余 N-K 个元素依次与堆顶元素比完之后，堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素

代码语言：javascript
复制
#include<stdio.h>
void CreateNDate()
{
	// 造数据
	int n = 100000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	for (int i = 0; i < n; ++i)
	{
		int x = (rand() + i) % 1000000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}
void topk()
{
	printf("请输⼊k：>");
	int k = 0;
	scanf("%d", &k);
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}
	int val = 0;
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc error");
		return;
	}
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
	}
	// 建k个数据的⼩堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(minheap, k, i);
	}
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		// 读取剩余数据，⽐堆顶的值⼤，就替换他进堆
		if (x > minheap[0])
		{
			minheap[0] = x;
			AdjustDown(minheap, k, 0);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	fclose(fout);
}

时间复杂度：O(N)= k + (n − k)log k（log以2为底） 

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2026-01-13，如有侵权请联系 cloudcommunity@tencent.com 删除
算法
二叉树
数据结构
数据
数组

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

算法
二叉树
数据结构
数据
数组
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 一、堆的概念与结构
  • 二、堆的实现
    • 2.1、Heap.h
    • 2.2、Heap.c
    • 2.3、test.c
    • 2.4、向上调整算法
    • 2.5、向下调整算法
  • 三、堆的应用
    • 3.1、堆的排序
      • 版本一：基于已有数组建堆、取堆顶元素完成排序版本
      • 版本二：数组建堆，首位交换，交换后的堆尾数据从堆中删掉，将堆顶数据向下调整选出次大的数据
    • 3.2、TOP-K问题
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2026 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论