c 语言 堆的解析(自我理解)!!!堆排序,建堆

2023-12-09 03:36

本文主要是介绍c 语言 堆的解析(自我理解)!!!堆排序,建堆,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.堆是什么?

首先先看一个图片

小顶堆的意思就是顶 的元素最小,两个子节点的元素要大于父节点。大顶堆同理。

小顶堆就像是一个金字塔。第一层很小,然后后面是依次增大,就像社会人才金字塔图一样。

大顶堆就可以想做,每个人的财富拥有值的金字塔图,上层人的钱很多,而底层的人钱最少。

其次关于堆,其实堆在通常情况下是一个完全二叉树 (只有最底层的节点没有充满的二叉树,全充满的也属于完全二叉树叫做满二叉树)

那堆能干嘛呢,首先堆是可以用来排序的,而且排序的时间也是较快,处于(n*logn)这个层级。 

 还有一个就是在频繁的出队和入队时,用堆是一个不错的选择。如果用数组和链表来完成pop和push时,时间复杂度是O(n)而用 堆就是O(log n)。

在一个堆中通常用parent 和 child 来表示父节点和子节点。堆通常都是用数组来实现的。

通过上图可以看出堆的父节点如果为0的话,子节点就是1 和 2.就可以推导出公式

child = parent * 2 +1 或者 parent * 2 + 2。parent = child  / 2。

2.堆的实现和接口。(小堆)

1.头文件

#define _CRT_SECURE_NO_WARNINGS  1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<time.h>
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;
void Swap(int* C, int* P);
void AdjustUP(int* a, int size);//向上调整
void AdjustDown(HPDataType* a, int size,int parent);//向下调整
void HPInit(HP* hp);//初始化
void HPDestroy(HP* hp);//摧毁
void HeapPush(HP* hp, HPDataType x);//加入数据
void HeapPop(HP* hp);//删除数据
HPDataType HeapTop(HP* hp);//查找头元素
int HeapSize(HP* hp);//有效元素个数
bool HeapEmpty(HP* hp);//判空

堆的底层和顺序表的底层很像,但二者也不是相同。

size 的意思是目前元素的个数

capacity是当前开辟的空间的容量 

2.初始化

void HPInit(HP* hp)
{assert(hp);hp->a = NULL;hp->capacity = 0;hp->size = 0;
}

3.摧毁

void HPDestroy(HP* hp)
{assert(hp);free(hp->a);hp->a = NULL;hp->capacity = 0;hp->size = 0;
}

4.向上调整(重点)

void AdjustUP(int* a,int Child)
{assert(a);int Parent = (Child - 1) / 2;while (Child > 0){if (a[Child] < a[Parent]){Swap(&(a[Child]), &(a[Parent]));}else{break;}Child = (Child - 1) / 2;Parent = (Parent - 1) / 2;}
}

关于向上调整实际上就是,把选定的Child位置元素,以大堆或小堆的方式向上调整。

 因为向上调整是从孩子的位置开始向父亲的位置开始调整的,因为向上嘛,如果是父亲调儿子辈分就乱了。所以传入进来的 child 。然后 child > 0 ,是为了让 最后 孩子走到顶就是 0 的位置以后 这时才将所有的父节点比较结束。

因为实现的是小堆,如果子节点的值小于父节点就交换二者的值。出现 大于父节点的值就break。child = (child - 1)/2 是为了让子节点成为父节点,而 parent = (parent - 1)/2是为了让父节点等与下一个父节点,大致想象为爷爷节点。

5.向下调整(重点)

void AdjustDown(HPDataType *a,int size,int parent)
{assert(a);int child = parent*2+1;while (child < size){if (child + 1 < size && a[child] > a[child + 1]){++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

顾名思义 向下调整就是以开头第一个元素为始,开始依次向子节点比较,当child 大于或等于size时循环停止,child + 1小于size 和 a【child】 大于 a【child + 1】条件的原因是,因为向下调整要对比的是两个子节点,通过比较 选出较小的节点(小堆),如果 【child+1】较小就++child。如果父节点比最小的子节点大,那就交换二者的位置,然后向下以这个逻辑,循环到如果出现 最小的孩子 比父亲节点还大的话,那就break循环,如果没有就循环到child大于等于size为止。 

6.插入(重点)

void HeapPush(HP* hp, HPDataType x)
{assert(hp);if (hp->capacity == hp->size){int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;HPDataType* tmp = (HPDataType*)realloc(hp->a,sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc failed");exit(-1);}hp->a = tmp;hp->capacity = newcapacity;}hp->a[hp->size] = x;hp->size++;AdjustUP(hp->a,hp->size);
}

 对于堆的插入呢,当然首先也是尾插,因为这是一个小堆,如果你插入一个特别小的数,那么这个堆就得重新开始调整了。当然调整就用一个向上调整即可,从最下面往上面调整。

因为是插入,所以要先判断整个数列的空间和现在的元素个数,如果 相等了那就得扩容了。

扩容好以后,把要插入的数字尾插在数列的尾端,同时size++,然后对这个数字进行向上调整。

7.删除(重点)

void HeapPop(HP* hp)
{assert(hp);Swap(&(hp->a[hp->size]), &(hp->a[0]));hp->size--;AdjustDown(hp->a,hp->size,0);
}

堆的删除,不是尾删 。而是把头元素删除。 

所以一般的堆删除就是把头尾交换,在把size-- 和顺序的删除很像,就是删除的头结点。、

删除之后对堆在进行一次向下调整即可。因为传上来的数字本来就是在最下面的,所以要把它在沉到最下面。

8.头元素

HPDataType HeapTop(HP* hp)
{assert(hp);return hp->a[0];
}

9.元素个数

int HeapSize(HP* hp)
{assert(hp);return hp->size;
}

10.判空

bool HeapEmpty(HP* hp)
{assert(hp);return hp->size == 0;
}

3.堆的排序。

所谓排序,相信大家都已经学过冒泡排序了把,排序就是把一串数字排成升序或者降序。

那我们为什么要学习排序呢?最重要的一点就是   面试   sdad 

在笔试的时候,最主要的就是靠算法题。像拼多多、头条这种大公司,上来就来几道算法题,如果你没AC出来,面试机会都没有。

在面试(现场面或者视频面)的时候也会问算法题,难度肯定是没有笔试的时候那么难的。我们可以想象一个场景,一面面试面到一半,面试官让你反转二叉树,问问现在的自己,你还会吗。

 所以这些排序我们都还得学,当然以后如果有这方面的工作也会用得到,技多不压身。

堆排序的源代码和实现

#include"Heap.h"
void HeapSort(int* a, size_t size)
{for (int i = (size-1-1)/2; i >=0; i--){AdjustDown(a, size,i);}for (int i = size-1; i > 0; i--){Swap(&a[i], &a[0]);AdjustDown(a, i,0);}
}
int main()
{int arr[] = { 4,10,22,3,6,9,25,11,715 };HeapSort(arr, sizeof(arr) / sizeof(arr[0]));return 0;
}

首先堆排序咱有两步,第一步是先把一组数组先把它先建立成堆。

第二步就是用调整的方法把这个数组变成有序的

关于建堆有两种方法,第一种是用向上调整直接从数组第一个开始,每一个都进行一次向上调整,如果这样调整的话,建堆这个过程的时间复杂度就是n * logn。

而向下调整建堆的时间复杂度则到达了 n ,快了很多,这是向下调整的图片

 

 而我们用向下调整建堆呢,是从这个图元素大小为28的最后一个元素的父节点来进行调整的,这种建堆的关键就是从倒数第一个非叶子节点开始调(也就是树中最后一个父节点),然后逐渐+1,就可以调整从最后一个父节点开始的每一棵树.公式里的第一个size - 1呢是因为本来size是计算元素个数的,数组又是从0开始排序的,所以size - 1是要得到最后一个叶子结点。

而第二个 - 1呢是因为,parent = (child - 1)/ 2.因为adjustdown中传入的第三个变量是parent 所以 需要第二次 - 1.(所以一般建堆都是用向下调整建堆,时间效率高)

 

 

这篇关于c 语言 堆的解析(自我理解)!!!堆排序,建堆的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/472323

相关文章

PostgreSQL的扩展dict_int应用案例解析

《PostgreSQL的扩展dict_int应用案例解析》dict_int扩展为PostgreSQL提供了专业的整数文本处理能力,特别适合需要精确处理数字内容的搜索场景,本文给大家介绍PostgreS... 目录PostgreSQL的扩展dict_int一、扩展概述二、核心功能三、安装与启用四、字典配置方法

Go语言中make和new的区别及说明

《Go语言中make和new的区别及说明》:本文主要介绍Go语言中make和new的区别及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1 概述2 new 函数2.1 功能2.2 语法2.3 初始化案例3 make 函数3.1 功能3.2 语法3.3 初始化

深度解析Java DTO(最新推荐)

《深度解析JavaDTO(最新推荐)》DTO(DataTransferObject)是一种用于在不同层(如Controller层、Service层)之间传输数据的对象设计模式,其核心目的是封装数据,... 目录一、什么是DTO?DTO的核心特点:二、为什么需要DTO?(对比Entity)三、实际应用场景解析

从原理到实战深入理解Java 断言assert

《从原理到实战深入理解Java断言assert》本文深入解析Java断言机制,涵盖语法、工作原理、启用方式及与异常的区别,推荐用于开发阶段的条件检查与状态验证,并强调生产环境应使用参数验证工具类替代... 目录深入理解 Java 断言(assert):从原理到实战引言:为什么需要断言?一、断言基础1.1 语

深度解析Java项目中包和包之间的联系

《深度解析Java项目中包和包之间的联系》文章浏览阅读850次,点赞13次,收藏8次。本文详细介绍了Java分层架构中的几个关键包:DTO、Controller、Service和Mapper。_jav... 目录前言一、各大包1.DTO1.1、DTO的核心用途1.2. DTO与实体类(Entity)的区别1

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Go语言中nil判断的注意事项(最新推荐)

《Go语言中nil判断的注意事项(最新推荐)》本文给大家介绍Go语言中nil判断的注意事项,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1.接口变量的特殊行为2.nil的合法类型3.nil值的实用行为4.自定义类型与nil5.反射判断nil6.函数返回的

Go语言数据库编程GORM 的基本使用详解

《Go语言数据库编程GORM的基本使用详解》GORM是Go语言流行的ORM框架,封装database/sql,支持自动迁移、关联、事务等,提供CRUD、条件查询、钩子函数、日志等功能,简化数据库操作... 目录一、安装与初始化1. 安装 GORM 及数据库驱动2. 建立数据库连接二、定义模型结构体三、自动迁

使用Python绘制3D堆叠条形图全解析

《使用Python绘制3D堆叠条形图全解析》在数据可视化的工具箱里,3D图表总能带来眼前一亮的效果,本文就来和大家聊聊如何使用Python实现绘制3D堆叠条形图,感兴趣的小伙伴可以了解下... 目录为什么选择 3D 堆叠条形图代码实现:从数据到 3D 世界的搭建核心代码逐行解析细节优化应用场景:3D 堆叠图

深度解析Python装饰器常见用法与进阶技巧

《深度解析Python装饰器常见用法与进阶技巧》Python装饰器(Decorator)是提升代码可读性与复用性的强大工具,本文将深入解析Python装饰器的原理,常见用法,进阶技巧与最佳实践,希望可... 目录装饰器的基本原理函数装饰器的常见用法带参数的装饰器类装饰器与方法装饰器装饰器的嵌套与组合进阶技巧