当前位置： 首页 > article >正文

堆排序（C语言版本）

article 2025/2/23 0:27:18

目录

1. 树的介绍

1.1 特殊的二叉树

1.2 二叉树的性质

1.3 二叉树的存储结构

2. 堆的介绍和使用

2.1 堆的概念及结构

2.2 堆的实现

2.2.1 堆向下调整算法

2.2.2 堆的删除

3. 堆排序

4. TOP-K问题

我这边会有目录，所以想看堆排序的可以直接跳转过去，我这边首先介绍下树

1. 树的介绍

1.1 特殊的二叉树

  • 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是 说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
  • 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

1.2 二叉树的性质

  • 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(h-1)个结点。
  • 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1。
  • 对任何一棵二叉树, 如果度为0其叶结点个数为n0, 度为2的分支结点个数为n2 ,则有n0＝n2＋1
  • 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log(n + 1)。 (ps：log(n+1)是log以2为底，n+1为对数)。

做一道练习题：

解析：

1.3 二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

1. 顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

结论：数组存储只适合完全二叉树和满二叉树

物理结构：数组（因为ABCDEFG都是存放到数组中）

逻辑结构：二叉树（现象成是一颗二叉树）

我们根据数组可以发现父子存储的下标位置规律

leftchild = parent * 2 + 1

rightchild = parent * 2 + 2

partent = (child-1)/2

2. 链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所 在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程学到高阶数据结构如红黑树等会用到三叉链。

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
	struct BinTreeNode* _pLeft; // 指向当前节点左孩子
	struct BinTreeNode* _pRight; // 指向当前节点右孩子
	BTDataType _data; // 当前节点值域
};

// 三叉链
struct BinaryTreeNode
{
	struct BinTreeNode* _pParent; // 指向当前节点的双亲
	struct BinTreeNode* _pLeft; // 指向当前节点左孩子
	struct BinTreeNode* _pRight; // 指向当前节点右孩子
	BTDataType _data; // 当前节点值域
};

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

2. 堆的介绍和使用

2.1 堆的概念及结构

把要存储的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

  1. 完全二叉树
  2. 小堆（任何一个父亲<=孩子）
  3. 大堆（任何一个父亲>=孩子）

2.2 堆的实现

2.2.1 堆向下调整算法

堆的调整优先使用向下调整

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

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

向下调整代码实现

//交换元素
void Swap(HPDataTyped* child, HPDataTyped* parent)
{
	HPDataTyped tmp = *parent;
	*parent = *child;
	*child = tmp;
}

//判断是否需要向下调制元素位置
//因为把最后一个叶子节点与跟节点数据进行交换
//会导致堆的结构被破坏，所以这里就进行向下调整
void AdjustDown(HPDataTyped* a, int n, int parent)
{
	int child = 2 * parent + 1;
	//函数退出条件
	//当父亲节点走到叶子部分的时候就要退出了
	//而孩子节点是父亲节点乘2+1,所以孩子的下标就会超过数组的长度
	//从而用其判断函数结束标志
	while (child < n)
	{
		//child+1是防止右子树没数据，如果还让左孩子与右还是相比就会越界
		//a[child+1] < a[child] 是为了找到其中最小的元素
		//我们一开始假设的是左孩子是最小的，所以如果右孩子更小，我们就要让child++
		//思路：把最小的元素放入根部，使得下一次取根元素，从而实现从小到大排序
		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;
		}
	}

2.2.2 堆的删除

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

3. 堆排序

1. 建堆

  • 升序：建大堆
  • 降序：建小堆

2. 用堆删除思想来进行排序（但并不是把交换后的数据删掉，而是不把交换后的数据看做是堆内的元素）

使用堆的向下调整算法，最坏的情况下（即一直需要交换结点），需要循环的次数为：h - 1次（h为树的高度）。而h = log2(N+1)（N为树的总结点数）。所以堆的向下调整算法的时间复杂度为：O(logN）

上面说到，使用堆的向下调整算法需要满足其根结点的左右子树均为大堆或是小堆才行，那么如何才能将一个任意树调整为堆呢？
答案很简单，我们只需要从倒数第一个非叶子结点开始，从后往前，按下标，依次作为根去向下调整即可。

建堆代码

//通过向下调整来建堆，这样消耗会小
for (int i = (sz - 1 - 1) / 2; i >= 0; i--)
{
	adjustDown(arr, sz, i);
}

那么建堆的时间复杂度又是多少呢？
 当结点数无穷大时，完全二叉树与其层数相同的满二叉树相比较来说，它们相差的结点数可以忽略不计，所以计算时间复杂度的时候我们可以将完全二叉树看作与其层数相同的满二叉树来进行计算。

 向下调整建堆的时间复杂度

1. 首先我们要看满二叉树的节点个数和层数的关系

向下调整建堆时间复杂如下

那么堆建好后，如何进行堆排序呢？
步骤如下：
 1、将堆顶数据与堆的最后一个数据交换，然后对根位置进行一次堆的向下调整，但是调整时被交换到最后的那个最大的数不参与向下调整。
 2、完成步骤1后，这棵树除最后一个数之外，其余数又成一个大堆，然后又将堆顶数据与堆的最后一个数据交换，这样一来，第二大的数就被放到了倒数第二个位置上，然后该数又不参与堆的向下调整…反复执行下去，直到堆中只有一个数据时便结束。此时该序列就是一个升序。堆排序代码：

Test.c

#include "Heap.h"

int main()
{
	int arr[] = { 31,315,52,12,100,17,81,498 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int end = sz;
	//通过向下调整来建堆，这样消耗会小
	for (int i = (sz - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, sz, i);
	}
	//排序（降序建小堆）
	while (sz > 1)
	{
		Swap(&arr[0], &arr[sz - 1]);
		sz--;
		AdjustDown(arr, sz, 0);
	}
	for (int i = 0; i < end; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

 Head.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"

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

//销毁堆
void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->sz = 0;
}

//交换元素
void Swap(HPDataType* child, HPDataType* parent)
{
	HPDataType tmp = *parent;
	*parent = *child;
	*child = tmp;
}

//因为我们插入的时候是尾差，有可能插入的数据是比祖先节点还小
//所以我们需要判断是否需要向上调制元素位置
void AdjustUp(HPDataType* a, int sz)
{
	int child = sz;
	int parent = (child - 1) / 2;
	//循环结束条件：
	//因为如果最后插入的节点是整颗树最小的节点的话
	//那最后这个节点（child）就会一直往上交换直到变成了整个树的根
	//那此时child值就为0（指向的是数组下标为0的元素）
	//而父亲节点parent = (parent-1) / 2就为0
	//因为当child = 0的时候就已经在无法相比了，所以就退出循环
	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->capacity == php->sz)
	{
		int Newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* cur = (HPDataType*)realloc(php->a, sizeof(HPDataType) * Newcapacity);
		if (cur == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = cur;
		php->capacity = Newcapacity;
	}
	php->a[php->sz] = x;
	php->sz++;
	//因为我们插入的时候是尾差，有可能插入的数据是比祖先节点还小，所以我们需要向上判断
	AdjustUp(php->a, php->sz - 1);
}
//返回根节点元素
HPDataType HPTop(HP* php)
{
	assert(php);
	assert(!HPEmpty(php));
	return php->a[0];
}

//判断是否需要向下调制元素位置
//因为把最后一个叶子节点与跟节点数据进行交换
//会导致堆的结构被破坏，所以这里就进行向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = 2 * parent + 1;
	//函数退出条件
	//当父亲节点走到叶子部分的时候就要退出了
	//而孩子节点是父亲节点乘2+1,所以孩子的下标就会超过数组的长度
	//从而用其判断函数结束标志
	while (child < n)
	{
		//child+1是防止右子树没数据，如果还让左孩子与右还是相比就会越界
		//a[child+1] < a[child] 是为了找到其中最小的元素
		//我们一开始假设的是左孩子是最小的，所以如果右孩子更小，我们就要让child++
		//思路：把最小的元素放入根部，使得下一次取跟元素，从而实现从小到大排序
		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(!HPEmpty(php));
	int chlid = php->sz - 1;
	int parent = 0;
	Swap(&(php->a[chlid]), &(php->a[parent]));
	php->sz--;
	AdjustDown(php->a, php->sz, 0);
}

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

Head.h

#pragma once
#include<stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	int sz;
	int capacity;
}HP;

//初始化堆
void HPInit(HP* php);
//初始化堆
void HPInitArray(HP* php, HPDataType* a, int n);
//销毁栈
void HPDestroy(HP* php);
//堆插入元素
void HPPush(HP* php, HPDataType x);
//返回堆顶元素
HPDataType HPTop(HP* php);
//删除堆顶元素
void HPPop(HP* php);
//判断堆是否为空
bool HPEmpty(HP* php);
//向下调整
void AdjustDown(HPDataType* a, int n, int parent);
//交换元素
void Swap(HPDataType* a1, HPDataType* a2);

时间复杂度：0(NlogN) 空间复杂度：O(1)

4. TOP-K问题


http://www.kler.cn/a/550079.html

相关文章：

  • IMX6ULL的ALT0、ALT1、ALT2、ALT3、ALT4等是啥意思？
  • Golang学习笔记_31——原型模式
  • 【Java线程中断】线程中断后为什么要调用interrupt()?
  • XSS攻击（跨站脚本攻击）详解与实战
  • 智能选路+NAT实验
  • 分享一个解梦 Chrome 扩展 —— 周公 AI 解梦
  • 天翼云910B部署DeepSeek蒸馏70B LLaMA模型实践总结
  • Game Maker 0.11：《The Sandbox》创作愿景的全新篇章
  • 【学习】软件测试中的分类树法介绍
  • 设计模式3：代理、适配器、装饰器模式
  • 工厂设计模式一篇全部概括
  • 使用 Docker 部署 Elasticsearch：详细步骤与原创指南
  • 2025年人工智能十大趋势：AI如何塑造未来？
  • 有关表单autocomplete = “off“ 失效问题解决方案
  • Android MVC、MVP、MVVM、MVI的架构的区别
  • 武汉火影数字|VR大空间内容制作：开启沉浸式体验新时代
  • Python基础-使用dict和set
  • 走出养生误区，拥抱健康生活
  • 亿发解析2025年新零售趋势：全场景融合与深度数字化
  • nlp|微调大语言模型初探索(2)，训练自己的聊天机器人