二叉树顺序结构——堆的结构与实现

二叉树顺序结构——堆的结构与实现

  • 一、二叉树的顺序结构
  • 二、堆的概念及结构
  • 三、堆的实现
    • 堆向下调整算法
    • 堆的创建
    • 建堆时间复杂度
    • 堆的插入(堆向上调整算法)
    • 堆的删除
    • 堆的代码实现(使用VS2022的C语言)
      • 初始化、销毁
      • 构建、插入、删除
      • 返回堆顶元素、判空、返回有效元素个数
  • 四、完整 Heap.c 源代码

一、二叉树的顺序结构

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

二、堆的概念及结构

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

  1. 堆中某个结点的值总是不大于或不小于其父结点的值；
  2. 堆总是一棵完全二叉树。
    在这里插入图片描述
    在这里插入图片描述

三、堆的实现

注意：

  1. 对于堆中父亲节点下标 i ，它的左孩子总是 i * 2 + 1，右孩子总是 i * 2 + 2;
  2. 对于左右孩子节点 i ，由于整数相除会取整，则它们共同的父亲节点为：(i - 1) / 2;
/*
* leftChild = parent * 2 + 1;
* rightChild = parent * 2 + 2;
* parent = (leftChild - 1) / 2 = (rightChild - 1) / 2;
*/

堆向下调整算法

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

void swap(HPDataType* a, HPDataType* b)
{
	HPDataType temp = *a;
	*a = *b;
	*b = temp;
}

// 向下调整代码
void AdjustDown(HPDataType* arr, int n, int parent)
{
	assert(arr);
	
	// 先找到左孩子
	int child = parent * 2 + 1;
	while (child < n)						// 当child 超过范围退出
	{
		// 假设法
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			++child;
		}
		
		// 若不符合堆的性质，则调整，反之退出
		if (arr[parent] > arr[child])
		{
			swap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;							// 满足堆的性质，直接退出
		}
	}
}

堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根结点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子结点的子树开始调整，一直调整到根结点的树，就可以调整成堆。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

// 堆的创建
void HeapCreate(pHeap ph, HPDataType* arr, int sz)
{
	assert(ph);
	assert(HeapEmpty(ph));		// 堆不为空则不能创建

	HPDataType* temp = (HPDataType*)realloc(ph->arr, sizeof(HPDataType) * sz);
	if (temp == NULL)
	{
		perror("realloc failed");
		return;
	}
	ph->arr = temp;
	ph->size = sz;
	ph->capacity = sz;

	memcpy(ph->arr, arr, sizeof(HPDataType) * sz);
	
	// 倒数的第一个非叶子结点的子树下标为: 
	// (总长 - 2) / 2 == 总长 / 2 - 1
	// 因为对于最后一个叶子节点，它的下标为：
	// 总长 - 1
	// 而我们知道非根节点无论是左右孩子，因为整数用除会取整，
	// 则它的父亲节点均为：
	// (child - 1) / 2
	// 即：
	// lastChild = 总长 - 1;
	// 倒数的第一个非叶子结点的子树下标 = (lastChild - 1) / 2;
	// 得 (总长 - 1 - 1) / 2 == 总长 / 2 - 1
	for (int i = sz / 2 - 1; i >= 0; --i)
	{
		AdjustDown(ph->arr, sz, i);
	}
}

建堆时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个结点不影响最终结果)：
在这里插入图片描述
因此：建堆的时间复杂度为O(N)。

堆的插入(堆向上调整算法)

先插入一个 10 到数组的尾上，再进行向上调整算法，直到满足堆。
在这里插入图片描述

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

	int parent = (child - 1) / 2;
	while (child > 0)				// 当 child 为根节点时退出
	{
		if (arr[child] < arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;					// 当数据满足堆的性质时退出
		}
	}
}

堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
在这里插入图片描述

堆的代码实现(使用VS2022的C语言)

堆常用的接口包括：

  1. 初始化、销毁

  2. 构建、插入、删除

  3. 返回堆顶元素、判空、返回有效元素个数

在 Heap.h 中：

#pragma once

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

// 初始化容量
#define INIT_CAPACITY 4

// 增容倍率
#define EXPANSION_MULTIPLE 2

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* arr;
	int size;
	int capacity;
} Heap, * pHeap;

// 初始化、销毁
void HeapInit(pHeap ph);

void HeapDestroy(pHeap ph);

// 构建、插入、删除
void HeapCreate(pHeap ph, HPDataType* arr, int sz);

void HeapPush(pHeap ph, HPDataType x);

void HeapPop(pHeap ph);

// 返回堆顶元素、判空、返回有效元素个数
HPDataType HeapTop(pHeap ph);

bool HeapEmpty(pHeap ph);

int HeapSize(pHeap ph);

在 Heap.c 中：

初始化、销毁

void HeapInit(pHeap ph)
{
	assert(ph);

	ph->arr = NULL;
	ph->size = 0;
	ph->capacity = 0;
}

void HeapDestroy(pHeap ph)
{
	assert(ph);

	free(ph->arr);
	ph->size = 0;
	ph->capacity = 0;
}

构建、插入、删除

// 堆的创建
void HeapCreate(pHeap ph, HPDataType* arr, int sz)
{
	assert(ph);
	assert(HeapEmpty(ph));		// 堆不为空则不能创建

	HPDataType* temp = (HPDataType*)realloc(ph->arr, sizeof(HPDataType) * sz);
	if (temp == NULL)
	{
		perror("realloc failed");
		return;
	}
	ph->arr = temp;
	ph->size = sz;
	ph->capacity = sz;

	memcpy(ph->arr, arr, sizeof(HPDataType) * sz);

	// 倒数的第一个非叶子结点的子树下标为: 
	// (总长 - 2) / 2 == 总长 / 2 - 1
	// 因为对于最后一个叶子节点，它的下标为：
	// 总长 - 1
	// 而我们知道非根节点无论是左右孩子，因为整数用除会取整，
	// 则它的父亲节点均为：
	// (child - 1) / 2
	// 即：
	// lastChild = 总长 - 1;
	// 倒数的第一个非叶子结点的子树下标 = (lastChild - 1) / 2;
	// 得 (总长 - 1 - 1) / 2 == 总长 / 2 - 1
	for (int i = sz / 2 - 1; i >= 0; --i)
	{
		AdjustDown(ph->arr, sz, i);
	}
}

void HeapPush(pHeap ph, HPDataType x)
{
	assert(ph);
	
	// 先判断空间是否充足
	if (ph->size == ph->capacity)
	{
		int newCapacity = ph->capacity == 0 ? INIT_CAPACITY : ph->capacity * EXPANSION_MULTIPLE;
		HPDataType* temp = (HPDataType*)realloc(ph->arr, sizeof(HPDataType) * newCapacity);
		if (temp == NULL)
		{
			perror("realloc failed");
			return;
		}

		ph->arr = temp;
		ph->capacity = newCapacity;
	}

	ph->arr[ph->size++] = x;
	AdjustUp(ph->arr, ph->size - 1);
}

void HeapPop(pHeap ph)
{
	assert(ph);
	assert(!HeapEmpty(ph));

	--ph->size;
	swap(&ph->arr[0], &ph->arr[ph->size]);
	AdjustDown(ph->arr, ph->size, 0);
}

返回堆顶元素、判空、返回有效元素个数

HPDataType HeapTop(pHeap ph)
{
	assert(ph);
	assert(!HeapEmpty(ph));

	return ph->arr[0];
}

bool HeapEmpty(pHeap ph)
{
	assert(ph);

	return ph->size == 0;
}

int HeapSize(pHeap ph)
{
	assert(ph);

	return ph->size;
}

四、完整 Heap.c 源代码

#include "Heap.h"

void HeapInit(pHeap ph)
{
	assert(ph);

	ph->arr = NULL;
	ph->size = 0;
	ph->capacity = 0;
}

void HeapDestroy(pHeap ph)
{
	assert(ph);

	free(ph->arr);
	ph->size = 0;
	ph->capacity = 0;
}

void swap(HPDataType* a, HPDataType* b)
{
	HPDataType temp = *a;
	*a = *b;
	*b = temp;
}

// 向下调整代码
void AdjustDown(HPDataType* arr, int n, int parent)
{
	assert(arr);

	// 先找到左孩子
	int child = parent * 2 + 1;
	while (child < n)						// 当child 超过范围退出
	{
		// 假设法
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			++child;
		}

		// 若不符合堆的性质，则调整，反之退出
		if (arr[parent] > arr[child])
		{
			swap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;							// 满足堆的性质，直接退出
		}
	}
}

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

	int parent = (child - 1) / 2;
	while (child > 0)				// 当 child 为根节点时退出
	{
		if (arr[child] < arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;					// 当数据满足堆的性质时退出
		}
	}
}

// 堆的创建
void HeapCreate(pHeap ph, HPDataType* arr, int sz)
{
	assert(ph);
	assert(HeapEmpty(ph));		// 堆不为空则不能创建

	HPDataType* temp = (HPDataType*)realloc(ph->arr, sizeof(HPDataType) * sz);
	if (temp == NULL)
	{
		perror("realloc failed");
		return;
	}
	ph->arr = temp;
	ph->size = sz;
	ph->capacity = sz;

	memcpy(ph->arr, arr, sizeof(HPDataType) * sz);

	// 倒数的第一个非叶子结点的子树下标为: 
	// (总长 - 2) / 2 == 总长 / 2 - 1
	// 因为对于最后一个叶子节点，它的下标为：
	// 总长 - 1
	// 而我们知道非根节点无论是左右孩子，因为整数用除会取整，
	// 则它的父亲节点均为：
	// (child - 1) / 2
	// 即：
	// lastChild = 总长 - 1;
	// 倒数的第一个非叶子结点的子树下标 = (lastChild - 1) / 2;
	// 得 (总长 - 1 - 1) / 2 == 总长 / 2 - 1
	for (int i = sz / 2 - 1; i >= 0; --i)
	{
		AdjustDown(ph->arr, sz, i);
	}
}

void HeapPush(pHeap ph, HPDataType x)
{
	assert(ph);

	// 先判断空间是否充足
	if (ph->size == ph->capacity)
	{
		int newCapacity = ph->capacity == 0 ? INIT_CAPACITY : ph->capacity * EXPANSION_MULTIPLE;
		HPDataType* temp = (HPDataType*)realloc(ph->arr, sizeof(HPDataType) * newCapacity);
		if (temp == NULL)
		{
			perror("realloc failed");
			return;
		}

		ph->arr = temp;
		ph->capacity = newCapacity;
	}

	ph->arr[ph->size++] = x;
	AdjustUp(ph->arr, ph->size - 1);
}

void HeapPop(pHeap ph)
{
	assert(ph);
	assert(!HeapEmpty(ph));

	--ph->size;
	swap(&ph->arr[0], &ph->arr[ph->size]);
	AdjustDown(ph->arr, ph->size, 0);
}

HPDataType HeapTop(pHeap ph)
{
	assert(ph);
	assert(!HeapEmpty(ph));

	return ph->arr[0];
}

bool HeapEmpty(pHeap ph)
{
	assert(ph);

	return ph->size == 0;
}

int HeapSize(pHeap ph)
{
	assert(ph);

	return ph->size;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/697581.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【Python教程】4-字符串、列表、字典、元组与集合操作

【Python教程】4-字符串、列表、字典、元组与集合操作

在整理自己的笔记的时候发现了当年学习python时候整理的笔记&#xff0c;稍微整理一下&#xff0c;分享出来&#xff0c;方便记录和查看吧。个人觉得如果想简单了解一名语言或者技术&#xff0c;最简单的方式就是通过菜鸟教程去学习一下。今后会从python开始重新更新&#xff0…
阅读更多...
7.高级纹理

7.高级纹理

前面的基础纹理包括法线纹理、渐变纹理和遮罩纹理等。这些纹理都属于低纬&#xff08;一维或二维&#xff09;纹理。 立方体纹理&#xff08;Cubemap&#xff09;实现环境映射 渲染纹理&#xff08;Render Texture&#xff09; 程序纹理&#xff08;Procedure Texture&#…
阅读更多...
java线程生命周期介绍

java线程生命周期介绍

Java线程的生命周期包含以下几个状态&#xff1a; 1.新建(New)&#xff1a;线程对象被创建&#xff0c;但是还没有调用start()方法。 1.运行(Runnable)&#xff1a;线程正在运行或者是就绪状态&#xff0c;等待CPU时间片。 1.阻塞(Blocked)&#xff1a;线程暂时停止执行&…
阅读更多...
每日5题Day21 - LeetCode 101 - 105

每日5题Day21 - LeetCode 101 - 105

每一步向前都是向自己的梦想更近一步&#xff0c;坚持不懈&#xff0c;勇往直前&#xff01; 第一题&#xff1a;101. 对称二叉树 - 力扣&#xff08;LeetCode&#xff09; class Solution {public boolean isSymmetric(TreeNode root) {if(root null){return true;}Stack<…
阅读更多...
已解决Error || KeyError: ‘The truth value of a Series is ambiguous‘

已解决Error || KeyError: ‘The truth value of a Series is ambiguous‘

已解决Error || KeyError: ‘The truth value of a Series is ambiguous’ &#x1f680; 原创作者&#xff1a; 猫头虎 作者微信号&#xff1a; Libin9iOak 作者公众号&#xff1a; 猫头虎技术团队 更新日期&#xff1a; 2024年6月6日 博主猫头虎的技术世界 &#x1f3…
阅读更多...
第十篇——等价性：信息是如何压缩的？

第十篇——等价性：信息是如何压缩的？

目录 一、背景介绍二、思路&方案三、过程1.思维导图2.文章中经典的句子理解3.学习之后对于投资市场的理解4.通过这篇文章结合我知道的东西我能想到什么&#xff1f; 四、总结五、升华 一、背景介绍 基于信息是如何进行压缩的&#xff0c;引出来等价信息的概念&#xff1b;…
阅读更多...
如何制定工程战略

如何制定工程战略

本文介绍了领导者如何有效制定工程战略&#xff0c;包括理解战略核心、如何收集信息并制定可行的策略&#xff0c;以及如何利用行业最佳实践和技术债务管理来提升团队效能和产品质量。原文: How to Build Engineering Strategy 如果你了解过目标框架&#xff08;如 OKR&#xf…
阅读更多...
某药监局后缀(第一部分)

某药监局后缀(第一部分)

声明 本文章中所有内容仅供学习交流使用&#xff0c;不用于其他任何目的&#xff0c;抓包内容、敏感网址、数据接口等均已做脱敏处理&#xff0c;严禁用于商业用途和非法用途&#xff0c;否则由此产生的一切后果均与作者无关&#xff01; 本文章未经许可禁止转载&#xff…
阅读更多...
Unity编辑器扩展，快捷键的使用

Unity编辑器扩展，快捷键的使用

代码部分 编辑器界面 使用方法&#xff1a; 使用方法和如图1一样&#xff0c;只需要在Menuitem的路径后面加上标识符号就行。 "#"对应的是shift "&"对应的是Alt "%"对应的是ctrl 比如我图中的是&#xff0c;%#s对应的是CtrlShifts&…
阅读更多...
ReentrantLock底层原理

ReentrantLock底层原理

ReentrantLock public ReentrantLock() {sync new NonfairSync(); }public ReentrantLock(boolean fair) {sync fair ? new FairSync() : new NonfairSync(); }ReentrantLock 的默认实现是非公平锁&#xff0c;实际上 ReentrantLock 中的方法&#xff0c;几乎都让 sync 实现…
阅读更多...
【C语言】11.字符函数和字符串函数

【C语言】11.字符函数和字符串函数

文章目录 1.字符分类函数2.字符转换函数3.strlen的使用和模拟实现4.strcpy的使用和模拟实现5.strcat的使用和模拟实现6.strcmp的使用和模拟实现7.strncpy函数的使用8.strncat函数的使用9.strncmp函数的使用10.strstr的使用和模拟实现11.strtok函数的使用12.strerror函数的使用 …
阅读更多...
买CPU怕买到假货？这担忧属实有点……

买CPU怕买到假货？这担忧属实有点……

这担忧属实有点多了 前段时间有朋友问小白&#xff1a;买CPU会买到假的吗&#xff1f; 啥&#xff1f;CPU还有假的&#xff1f; 这个问题让这几天闷闷不乐的小白笑得根本停不下来。 如果有哪个小伙伴能手搓个CPU出来&#xff0c;那这位小伙伴估计就不愁财富不到家了。 正文…
阅读更多...
爬虫工具yt-dlp

爬虫工具yt-dlp

yt-dlp是youtube-dlp的一个fork&#xff0c;youtube-dlp曾经也较为活跃&#xff0c;但后来被众多网站屏蔽&#xff0c;于是大家转而在其基础上开发yt-dlp。yt-dlp的github项目地址为&#xff1a;GitHub - yt-dlp/yt-dlp: A feature-rich command-line audio/video downloaderA …
阅读更多...
入侵报警系统的智慧核心——ARMxy工控机深度应用

入侵报警系统的智慧核心——ARMxy工控机深度应用

智能安防领域高清视频监控、人脸识别门禁系统以及入侵报警系统的智能化升级&#xff0c;正以前所未有的速度推动着行业的变革。在这场变革中&#xff0c;ARMxy工业计算机以其卓越的性能、高度的灵活性及强大的集成能力&#xff0c;成为了众多安防解决方案中的核心组件。 高清视…
阅读更多...
IIR滤波器的结构比较（Direct I and Direct II Form）

IIR滤波器的结构比较（Direct I and Direct II Form）

在 IIR 滤波器的设计和实现中&#xff0c;直接 I 型和直接 II 型结构的主要区别在于计算顺序和存储延迟项的方式。 直接I型结构 特点&#xff1a; 级联形式&#xff1a;直接I型结构的传递函数可以表示为两个级联部分&#xff1a;一个由分子系数组成的部分和一个由分母系数组…
阅读更多...
MySQL高性能（MySQL锁）

MySQL高性能（MySQL锁）

MySQL性能系列 MySQL锁 前言1. 死锁机制2. 思维导图与锁划分介绍3. 粒度划分锁3.1. 全局锁3.2. 页级锁&#xff08;Page-level locking&#xff09;3.3. 表级锁&#xff08;Tables-level lock&#xff09;○ 共享锁&#xff08;表级&#xff09;○ 排他锁&#xff08;表级&…
阅读更多...
字节面试：CPU100% 如何处理？

字节面试：CPU100% 如何处理？

尼恩说在前面 在40岁老架构师 尼恩的读者交流群(50)中&#xff0c;最近有小伙伴拿到了一线互联网企业如得物、阿里、滴滴、极兔、有赞、希音、百度、网易、美团的面试资格&#xff0c;遇到很多很重要的线上问题的场景题&#xff1a; 1.CPU100%&#xff0c;你是怎么处理的&…
阅读更多...
HTML做成一个粒子漩涡特效页面

HTML做成一个粒子漩涡特效页面

大家好&#xff0c;今天制作制作一个粒子漩涡特效的页面&#xff01; 先看具体效果&#xff1a; 要在一个单一的 index.html 页面中实现粒子漩涡特效&#xff0c;我们可以使用HTML、CSS和JavaScript&#xff08;不需要外部库&#xff09;。下面是一个简单的例子&#xff0c;展…
阅读更多...
OBS 录屏软件 for Mac 视频录制和视频实时交流软件 安装

OBS 录屏软件 for Mac 视频录制和视频实时交流软件 安装

Mac分享吧 文章目录 效果一、准备工作二、开始安装注意事项&#xff1a;包内有两个版本及圆形图片&#xff0c;请根据自身需要版本进行安装演示为&#xff1a;MacBook Pro M3芯片1、双击运行软件&#xff0c;将其从左侧拖入右侧文件夹中&#xff08;最终目的&#xff1a;安装进…
阅读更多...
【全网最简单的解决办法】vscode中点击运行出现仅当从 VS 开发人员命令提示符处运行 VS Code 时，cl.exe 生成和调试才可用

【全网最简单的解决办法】vscode中点击运行出现仅当从 VS 开发人员命令提示符处运行 VS Code 时，cl.exe 生成和调试才可用

首先确保你是否下载好了gcc编译器&#xff01;&#xff01;&#xff01; 检测方法&#xff1a; winR 打开cmd命令窗 输入where gcc(如果出现路径则说明gcc配置好啦&#xff01;) where gcc 然后打开我们的vscode 把这个文件删除掉 再次点击运行代码&#xff0c;第一个出现…
阅读更多...
最新文章

Copyright @ 2022~2023