6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)

本文主要是介绍6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

一.堆(Heap)的基本介绍

二.堆的常用操作(以小根堆为例)

三.实现代码

3.1 堆结构定义

3.2 向下调整算法*

3.3 初始化堆*

3.4 销毁堆

3.4 向上调整算法*

 3.5 插入数据

3.6 删除数据

3.7 返回堆顶数据

四.下篇内容

1.堆排序

2.TopK问题


一.堆(Heap)的基本介绍

        了解堆之前我们要简单了解完全二叉树:        

        在二叉树中,我们使用指针来连接每一个结点,最后构成一颗二叉树。而堆是一种使用数组来表示完全二叉树。其满足以下两条规则。

        1.堆中结点值总是大于或者小于其父结点的值。

        2.堆总是一颗完全二叉树。

由此可以推出有两种堆:大根堆和小根堆。

大根堆:根节点的值最大。

小根堆:根节点的值最小。

在堆(二叉树)中,如果一个结点的下标为i

其父亲的结点的下标为 (i-1)/ 2

其左孩子结点的下标为 (i+1)*2 -1  即  i*2 +1

其右孩子结点的下标为 (i+1)*2      即  i*2 + 2

数组的下标由0开始,读者可根据下图进行理解

二.堆的常用操作(以小根堆为例)

//初始化堆
void HeapInit(Heap* php, DataType* arr, int n);//数组建堆主要依赖的算法(这个算法要求数组的左右子树都是小堆)
//小堆,使用向下调整算法
void Adjustdown(DataType* arr, int n, int root);//向上调整算法
void Adjustup(DataType* arr, int n, int root);//销毁堆
void HeapDestory(Heap* php);//插入数据
void HeapPush(Heap* php, DataType x);//删除数据
void HeapPop(Heap* php, DataType x);//求堆顶(根)数据
DataType HeadTop(Heap* php);//交换两个数据
void swap(DataType* p1, DataType* p2);

三.实现代码

3.1 堆结构定义

//以小根堆为例
typedef int DataType;
typedef struct Heap
{DataType* arr;    //数组int capacity;     //容量int size;         //元素大小
}Heap;

3.2 向下调整算法*

        小根堆使用该算法的前提是左右子树都为小根堆,大根堆的前提是左右子树都为大根堆

该算法是从根结点依次向下找到比自己小(或者大)的结点,然后进行交换。

最后就能将新插入的根节点放到相应的位置

调整规则:

小根堆:根节点每一次与孩子结点中较小的一个交换

大根堆:根节点每一次与孩子结点中较大的一个交换

如下图

代码如下(以小根堆为例)

//向下调整算法
void AdjustDwon(DataType* arr, int n, int root)
{//1.小根堆,找出左右孩子中较小的结点int parent = root;int child = root * 2 + 1;	//表示左孩子while (child < n){//找到右孩子,如果右孩子比左孩子小,让child++。注意必须存在右孩子才能这么做if (child + 1 < n && arr[child + 1] < arr[child]){child++;}//如果该孩子比父亲小,就要交换if (arr[child] < arr[parent]){swap(arr[child], arr[parent]);//向下继续调整parent = child;child = parent * 2 + 1;}else{//如果孩子比父亲大,交换结束break;}}
}

3.3 初始化堆*

        初始化堆:将一个随机的数组(数组大小随机,元素大小也随机)转换为堆。

思路:

1.将一个数组拷贝到一个堆结构中

2.利用向下调整算法对整个数组进行调整,由于整个数组不能直接进行向下调整(左右子树不符合堆结构),所以我们使用向下调整算法堆 最后一个结点的父亲结点开始调整,然后依次对这个结点之前的结点开始调整。

3.最后得出完整的堆结构

流程图:

代码

//初始化堆
void HeapInit(Heap* hp, DataType* arr, int n)
{//开辟空间,大小为 DataType*nhp->arr = (DataType*)malloc(sizeof(DataType) * n);assert(hp->arr != nullptr);memcpy(hp->arr, arr, sizeof(DataType) * n);hp->size = n;hp->capacity = n;//拷贝好数据后,由于数据是随机的,所以我们使用调整算法建堆//我们从最后一个度为2的结点开始向前依次对每一个结点都进行向下调整//最后一个结点下标为 n-1 则其父亲结点为(n-1-1)/2for (int i = (n - 1 - 1) / 2; i > 0; i--){Adjustdown(hp->arr, hp->size, i);}
}

3.4 销毁堆

//销毁堆
void HeapDestory(Heap* php)
{assert(php);free(php->arr);php->arr = NULL;php->size = 0;php->capacity = 0;
}

3.4 向上调整算法*

当我们插入新数据时,这个数据会破坏堆结构(如插入到数组末尾),所以我们需要向上调整

和向下调整算法类似

思路:

        让新增节点依次和自己的父亲比较,然后交换即可

        小根堆:比父亲小,交换。直到比父亲大就结束

        大根堆:比父亲大,交换。直到比父亲小就结束

流程图:

代码

//向上调整算法,以小根堆为例
void AdjustUp(DataType* arr, int n, 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;}}
}

 3.5 插入数据

//插入数据
void HeapPush(Heap* hp, DataType x)
{assert(hp);//1.增容if (hp->size == hp->capacity){hp->capacity *= 2;DataType* tmp = (DataType*)realloc(hp->arr, sizeof(DataType) * hp->capacity);assert(tmp != NULL);hp->arr = tmp;}//2.在数组的插入数据hp->arr[hp->size] = x;hp->size++;//对数组进行向上调整,将小的数据向上调整Adjustup(hp->arr, hp->size, hp->size - 1);
}

3.6 删除数据

删除堆顶的数据

我们交换第一个数据和最后一个数据,然后删除最后一个数据。再对堆顶进行向下调整

这样就能满足删除后,整个堆还是满足规则的

//删除数据(删掉堆顶的数据)
//类似于堆排序,交换第一个和最后一个数据。保证根节点的左右子树都是小根堆
void HeapPop(Heap* hp)
{assert(hp);assert(hp->arr);swap(hp->arr[0], hp->arr[hp->size - 1]);hp->size--;Adjustdown(hp->arr, hp->size, 0);
}

3.7 返回堆顶数据

直接返回0下标处的数据即可

//求堆顶(根)数据
DataType HeadTop(Heap* hp)
{assert(hp);assert(hp->size > 0);return hp->arr[0];
}

四.下篇内容

1.堆排序

2.TopK问题

这篇关于6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

大模型研发全揭秘:客服工单数据标注的完整攻略

在人工智能(AI)领域,数据标注是模型训练过程中至关重要的一步。无论你是新手还是有经验的从业者,掌握数据标注的技术细节和常见问题的解决方案都能为你的AI项目增添不少价值。在电信运营商的客服系统中,工单数据是客户问题和解决方案的重要记录。通过对这些工单数据进行有效标注,不仅能够帮助提升客服自动化系统的智能化水平,还能优化客户服务流程,提高客户满意度。本文将详细介绍如何在电信运营商客服工单的背景下进行

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

基于MySQL Binlog的Elasticsearch数据同步实践

一、为什么要做 随着马蜂窝的逐渐发展,我们的业务数据越来越多,单纯使用 MySQL 已经不能满足我们的数据查询需求,例如对于商品、订单等数据的多维度检索。 使用 Elasticsearch 存储业务数据可以很好的解决我们业务中的搜索需求。而数据进行异构存储后,随之而来的就是数据同步的问题。 二、现有方法及问题 对于数据同步,我们目前的解决方案是建立数据中间表。把需要检索的业务数据,统一放到一张M

关于数据埋点,你需要了解这些基本知识

产品汪每天都在和数据打交道,你知道数据来自哪里吗? 移动app端内的用户行为数据大多来自埋点,了解一些埋点知识,能和数据分析师、技术侃大山,参与到前期的数据采集,更重要是让最终的埋点数据能为我所用,否则可怜巴巴等上几个月是常有的事。   埋点类型 根据埋点方式,可以区分为: 手动埋点半自动埋点全自动埋点 秉承“任何事物都有两面性”的道理:自动程度高的,能解决通用统计,便于统一化管理,但个性化定

使用SecondaryNameNode恢复NameNode的数据

1)需求: NameNode进程挂了并且存储的数据也丢失了,如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2)故障模拟 (1)kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 (2)删除NameNode存储的数据(/opt/module/hadoop-3.1.4/data/tmp/dfs/na

异构存储(冷热数据分离)

异构存储主要解决不同的数据,存储在不同类型的硬盘中,达到最佳性能的问题。 异构存储Shell操作 (1)查看当前有哪些存储策略可以用 [lytfly@hadoop102 hadoop-3.1.4]$ hdfs storagepolicies -listPolicies (2)为指定路径(数据存储目录)设置指定的存储策略 hdfs storagepolicies -setStoragePo

Hadoop集群数据均衡之磁盘间数据均衡

生产环境,由于硬盘空间不足,往往需要增加一块硬盘。刚加载的硬盘没有数据时,可以执行磁盘数据均衡命令。(Hadoop3.x新特性) plan后面带的节点的名字必须是已经存在的,并且是需要均衡的节点。 如果节点不存在,会报如下错误: 如果节点只有一个硬盘的话,不会创建均衡计划: (1)生成均衡计划 hdfs diskbalancer -plan hadoop102 (2)执行均衡计划 hd

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<