数据结构_ 堆结构与堆排序(c++ 实现 + 完整代码 )

news/2024/4/26 12:51:54/文章来源:https://blog.csdn.net/jj6666djdbbd/article/details/129168604

堆结构与堆排序

文章目录

  • 堆结构与堆排序
    • 引入堆
    • 堆结构所满足的数学特性
    • 准备代码
    • ----------- 往堆中插入元素
    • ----------- 删除堆顶
    • 堆排序构建
    • 完整代码及测试
      • 动态分配版本
      • 非动态版本

引入堆

  • 二叉树
    具有左孩子与右孩子的最普通的二叉树。

  • 满二叉树
    特殊的二叉树:每个节点如果有孩子则一定同时具有左孩子与右孩子。

满二叉树的条件:

  1. 要么有两个孩子,要么没有孩子
  2. 叶子节点在同一层

满二叉树有如下规律:
​如果层数为n
第n层节点数 一定为 2^(n-1)
整颗树节点数 为 2^n - 1


  • 完全二叉树
    能够使得满二叉树 从 下边和右边开始删节点的 二叉树 , 满足从右往左 从下往上删除 (和 阅读顺序 相反)

    1. 满二叉树一定是完全二叉树

    2. 完全二叉树不一定是满二叉树

  • ​ 堆是有序的完全二叉树。

    ​ 父子之间必须有序,父大于子或者子大于父,同层兄弟之间不用管

    1. 父大于子:最大堆(大顶堆)
    2. 子大于父:最小堆(小顶堆)

堆结构所满足的数学特性

在这里插入图片描述

下标关系:

  • 150 的 下标为 0 ,260 的下标为1,290的下标为3,400的下标为7。共同点:都是父节点的左孩子,父节点的下标*2+1=左孩子的下标

  • 150的下标为0,300的下标为2,400的下标为6;260的下标为1,320的下标为4,500的下标为10。共同点:都是父节点的右孩子,父节点的下标*2+2=右孩子的下标

  • 相反,已知400的下标为7,则290的下标为3,260的下标为1。共同点:已知左孩子的下标,(左孩子下标-1)/2得到父节点的下标

  • 已知500的下标为10,320的下标为4,260 的下标为1。共同点:已知右孩子的下标,(右孩子下标-2)/2得到父节点的下标

    总结:

    父亲推孩子:

    已知父节点下标为N
    左孩子下标为:2*N + 1

    右孩子下标为:2*N + 2

    孩子反推父亲:

    已知左孩子下标为M 父节点下标为: (M-1)/2
    已知右孩子下标为M 父节点下标为: (M-2)/2

    已知孩子下标为M 父节点下标为: (M-1)/2

准备代码

template <class T>
class My_Heap
{
private:T* pRoot;	//指向堆的指针,实际上是一个动态数组int len;	//元素个数int MaxLen;	//容量
public:My_Heap(){pRoot = nullptr;len = MaxLen = 0;}~My_Heap(){delete[] pRoot;pRoot = nullptr;len = MaxLen = 0;}//往堆中插入元素void insert(const T& data);//遍历void travel()const;//删除堆顶T pop();
};

----------- 往堆中插入元素

我们采用 小顶堆的方式,即保证孩子节点要比父亲节点大。
采用动态内存分配的方法,插入一个节点到数组中。
堆底开始,根据下标关系找到对应的父节点.

插入步骤:(小顶堆)

  1. 比较插入节点与当前父节点的关系
  2. 如果比父节点小,则当前节点需要上提,交换当前节点与父节点的值
  3. 如果比父节点大,则说明不冲突,则直接退出即可,因为经过以前的处理此情况一定是合法的。
  4. 继续比较,直到不冲突或者到达了根节点为止。

注意:我们使用自底向上的方式,每次比较当前节点与父节点的关系,然后需要将当前节点往上提,继续比较和上一层的关系

图例:
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

要点:从下往上遍历,交换不合适的节点。

template<class T>
inline void My_Heap<T>::insert(const T& data)
{//动态数组//1 像动态数组一样进来if (MaxLen <= len) {//需要申请//计算需要申请的内存大小   //>>1 右移一位 等同于除以2MaxLen = MaxLen + (((MaxLen >> 1) > 1) ? (MaxLen >> 1) : 1);//1 开内存T* pNew = new T[MaxLen];if (pRoot) {//2 pArr指向内存段中数据拷贝到pNew指向内存段memcpy(pNew, pRoot, sizeof(T) * len);//3 释放pArr指向内存段delete[] pRoot;}//4 pArr指向新开内存pRoot = pNew;}pRoot[len++] = data;//循环和父节点比较,如果冲突交换,不冲突,覆盖if (len == 1){return;}int CurrentIdx= len - 1;				//孩子节点int ParentIdx = (CurrentIdx - 1) / 2;	//父节点T temp;while (1){if (CurrentIdx <= 0)break;		//没有父节点,循环结束ParentIdx = (CurrentIdx - 1) / 2;if (pRoot[ParentIdx] < pRoot[CurrentIdx])break;	//不冲突,孩子父亲大,则停止//否则,交换元素temp = pRoot[ParentIdx];pRoot[ParentIdx] = pRoot[CurrentIdx];pRoot[CurrentIdx] = temp;//遍历完一次后,接着往上移动,开始重新一次比较CurrentIdx = ParentIdx;}
}

不使用动态内存分配:

void InsertData(int val){arr[++this->size] = val;if (this->size == 1) return;int curLen = this->size;//当前节点int parentLen = curLen >> 1;//父节点while (true){if (curLen <= 1) break;//到达根节点,退出//比较和父节点的关系,比父节点小则交换parentLen = curLen >> 1;if (arr[curLen] > arr[parentLen]){break;}swap(arr[curLen], arr[parentLen]);curLen = parentLen;}}

----------- 删除堆顶

从堆顶开始,把最后一个元素覆盖堆顶元素,接着根据下标关系,找到堆顶的孩子节点,比较两个孩子谁是最小孩子,如果堆顶比最小孩子节点小,则退出(小顶堆)。否则,交换两个节点,要保证父小于子。然后顶堆往下移动,移动到下一层的父节点,比较父子关系。确保在覆盖了原堆顶(即删除了原堆顶)后,整个堆结构仍然是以小堆顶的结构,因此要进行重排,直到数组下标越界为止。

步骤:

  1. 最后一个元素覆盖堆顶元素
  2. 当前节点寻找两个孩子节点的最小的那个,并且把那个最小的与当前节点的值作交换
  3. 当前节点下移,继续寻找最小的元素并且作交换
  4. 直到超过了下界之后停止。

注意:如果堆顶元素比左右孩子最小的元素都小,则不冲突,因此直接结束循环

图例:

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

要点:从上往下遍历,重排堆结构的父子关系。

template <class T>
//删除堆顶
T MyHeap<T>::pop(){if (0 == len){cout << "堆为空,删除失败!" << endl;return (T)0;}//没法删if (1 == len){//只有一个len--;return pRoot[0];}//1 临时保存堆顶元素T temp = pRoot[0];//2 最后一个覆盖堆顶元素pRoot[0] = pRoot[len - 1];//3 循环  int currentIdx = 0;//从堆顶开始int minChildIdx;while (1){//数组结束 if ((currentIdx * 2 + 1) > (len - 1) ||(currentIdx * 2 + 2) > (len - 1)){break;}// 找到最小的孩子 minChildIdx = currentIdx * 2 + 1;//假定左孩子比较小//如果左孩子比右孩子大,右孩子最小if (pRoot[minChildIdx] > pRoot[minChildIdx + 1]) minChildIdx++;//比最小孩子还小 循环结束if (pRoot[len-1] < pRoot[minChildIdx]) break;//当前位置和最小孩子交换 //子覆盖父//简单交换方式temp1 = pRoot[CurrentIdx];pRoot[CurrentIdx] = pRoot[MinChildIdx];pRoot[MinChildIdx] = temp1;//往下移动currentIdx = minChildIdx;}//4 返回len--;return temp;
}

不使用动态内存分配

int pop(){/*删除堆顶元素*/if (this->size == 1){this->size = 0;return arr[1];}//1. 最后一个元素覆盖堆顶元素int temp = arr[1];arr[1] = arr[this->size];int curLen = 1;//当前节点int childLen = curLen << 1;//孩子节点while (true){//下移超过了边界则退出if (((curLen << 1) > this->size) || (curLen << 1 | 1) > this->size){break;}//找到两个孩子中最小的一个childLen = curLen << 1;//默认最小的是左孩子if (arr[childLen] > arr[childLen + 1]){childLen += 1;//最小的为右孩子}//堆顶比最小的孩子还小,则无需交换if (arr[this->size] < arr[childLen]) break;//交换当前节点与孩子节点的值swap(arr[childLen], arr[curLen]);curLen = childLen;//下移到孩子}this->size--;//最后总的个数要减一个return temp;}

堆排序构建

template <class T>
//直接用数组方式来构建堆
void MyHeap<T>::initHeap(T* pArr, int size){//开内存maxLen = size;len = 0;pRoot = new T[size];//数据进来pRoot[len++] = pArr[0];//第一个int currentIdx;int parentIdx;for (int i = 1; i < size; i++){currentIdx = len;parentIdx = (currentIdx - 1) / 2;//数据先放进来pRoot[currentIdx] = pArr[i];while (1){if (currentIdx <= 0) break;//没有父节点 循环结束parentIdx = (currentIdx - 1) / 2;if (pRoot[parentIdx] < pRoot[currentIdx]) break;//冲突 父节点覆盖子节点pRoot[currentIdx] = pRoot[parentIdx];//往上移currentIdx = parentIdx;}//新数据覆盖回来pRoot[currentIdx] = pArr[i];//个数增加len++;}
}

完整代码及测试

动态分配版本

在这里插入图片描述

#pragma once
#include <iostream>
using namespace std;
template <class T>
class My_Heap
{
private:T* pRoot;	//指向堆的指针,实际上是一个动态数组int len;	//元素个数int MaxLen;	//容量
public:My_Heap(){pRoot = nullptr;len = MaxLen = 0;}~My_Heap(){delete[] pRoot;pRoot = nullptr;len = MaxLen = 0;}//往堆中插入元素void insert(const T& data);//遍历void travel()const;//删除堆顶T pop();void initHeap(T* pArr, int size);
};template<class T>
inline void My_Heap<T>::insert(const T& data)
{//动态数组//1 像动态数组一样进来if (MaxLen <= len) {//需要申请//计算需要申请的内存大小   //>>1 右移一位 等同于除以2MaxLen = MaxLen + (((MaxLen >> 1) > 1) ? (MaxLen >> 1) : 1);//1 开内存T* pNew = new T[MaxLen];if (pRoot) {//2 pArr指向内存段中数据拷贝到pNew指向内存段memcpy(pNew, pRoot, sizeof(T) * len);//3 释放pArr指向内存段delete[] pRoot;}//4 pArr指向新开内存pRoot = pNew;}pRoot[len++] = data;//循环和父节点比较,如果冲突交换,不冲突,覆盖if (len == 1){return;}int CurrentIdx= len - 1;				//孩子节点int ParentIdx = (CurrentIdx - 1) / 2;	//父节点T temp;while (1){if (CurrentIdx <= 0)break;		//没有父节点,循环结束ParentIdx = (CurrentIdx - 1) / 2;if (pRoot[ParentIdx] < pRoot[CurrentIdx])break;	//不冲突,循环继续//效率较低temp = pRoot[ParentIdx];pRoot[ParentIdx] = pRoot[CurrentIdx];pRoot[CurrentIdx] = temp;//往上移动CurrentIdx = ParentIdx;}
}template<class T>
inline void My_Heap<T>::travel() const
{for (int i = 0; i < len; i++){cout << pRoot[i] << " ";}cout << endl;
}template<class T>
inline T My_Heap<T>::pop()
{if (len == 0){cout << "堆为空!\n";return (T)0;}if (len == 1){len--;	//只有一个元素return pRoot[0];}//1. 临时保存堆顶元素T temp = pRoot[0];T temp1;//2. 最后一个元素覆盖堆顶元素pRoot[0] = pRoot[len - 1];//从堆顶开始int CurrentIdx = 0;int MinChildIdx;while (1){//越界if ((CurrentIdx * 2 + 1) > (len - 1) ||(CurrentIdx * 2 + 2) > (len - 1)){break;}//找到最小孩子//先假设左孩子比较小MinChildIdx = CurrentIdx * 2 + 1;if (pRoot[MinChildIdx] > pRoot[MinChildIdx + 1]){MinChildIdx++;	//右孩子比较小}//如果比最小孩子还小if (pRoot[len-1] < pRoot[MinChildIdx])break;//需要交换,采用简单交换, 子覆盖父temp1 = pRoot[CurrentIdx];pRoot[CurrentIdx] = pRoot[MinChildIdx];pRoot[MinChildIdx] = temp1;//父节点往下移动CurrentIdx = MinChildIdx;}len--;return temp;
}template <class T>
//直接用数组方式来构建堆
void My_Heap<T>::initHeap(T* pArr, int size) {//开内存MaxLen = size;len = 0;pRoot = new T[size];//数据进来pRoot[len++] = pArr[0];//第一个int currentIdx;int parentIdx;for (int i = 1; i < size; i++) {currentIdx = len;parentIdx = (currentIdx - 1) / 2;//数据先放进来pRoot[currentIdx] = pArr[i];while (1) {if (currentIdx <= 0) break;//没有父节点 循环结束parentIdx = (currentIdx - 1) / 2;if (pRoot[parentIdx] < pRoot[currentIdx]) break;//冲突 父节点覆盖子节点pRoot[currentIdx] = pRoot[parentIdx];//往上移currentIdx = parentIdx;}//新数据覆盖回来pRoot[currentIdx] = pArr[i];//个数增加len++;}
}
#include "MyHeap.h"#define NUM 11
int main()
{int arr[NUM] = { 150,260,300,290,320,350,500,400,450,490,500 };My_Heap<int> a;/*for (int i = 0; i < NUM; i++){a.insert(arr[i]);a.travel();}*/a.initHeap(arr, NUM);a.travel();return 0;
}

非动态版本

P1177 【模板】快速排序 ----排序测试

Ac code

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
#define int long long
const int N = 1e5 + 10;
const int CurSize = 1e5 + 10;
struct Tree
{int arr[N];int size;Tree() { memset(arr, 0, sizeof(arr)); size = 0; }void InsertData(int val){arr[++this->size] = val;if (this->size == 1) return;int curLen = this->size;//当前节点int parentLen = curLen >> 1;//父节点while (true){if (curLen <= 1) break;//到达根节点,退出//比较和父节点的关系,比父节点小则交换parentLen = curLen >> 1;if (arr[curLen] > arr[parentLen]){break;}swap(arr[curLen], arr[parentLen]);curLen = parentLen;}}int pop(){/*删除堆顶元素*/if (this->size == 1){this->size = 0;return arr[1];}//1. 最后一个元素覆盖堆顶元素int temp = arr[1];arr[1] = arr[this->size];int curLen = 1;//当前节点int childLen = curLen << 1;//孩子节点while (true){//下移超过了边界则退出if (((curLen << 1) > this->size) || (curLen << 1 | 1) > this->size){break;}//找到两个孩子中最小的一个childLen = curLen << 1;//默认最小的是左孩子if (arr[childLen] > arr[childLen + 1]){childLen += 1;//最小的为右孩子}//堆顶比最小的孩子还小,则无需交换if (arr[this->size] < arr[childLen]) break;//交换当前节点与孩子节点的值swap(arr[childLen], arr[curLen]);curLen = childLen;//下移到孩子}this->size--;//最后总的个数要减一个return temp;}
};
signed main()
{Tree t;int n;cin >> n;for (int i = 1; i <= n; i++){int p;cin >> p;t.InsertData(p);}while (t.size != 0){cout << t.pop() << " ";}return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

HTML课堂笔记

HTML 课堂笔记 文章目录相关概念code我的第一个html页面基本标签相关概念 1、什么是HTML&#xff1f; Hyper Text Markup Language 超文本标记语言 超文本&#xff1f;超级文本&#xff0c;例如流媒体&#xff0c;声音、视频、图片等。 标记语言&#xff1f;这种语言是由大量…

【Git】使用Git上传项目到远程仓库Gitee码云步骤详解

电脑里存放了很多项目&#xff0c;有的备份&#xff0c;有的没备份&#xff0c;如果不仔细分类管理的话&#xff0c;时间一长&#xff0c;到时看到那就会觉得非常杂乱&#xff0c;很难整理&#xff0c;这里有一个叫源代码托管&#xff0c;用过它的都知道&#xff0c;方便管理和…

【7/101】101次面试之测试技术面试题

01、什么是兼容性测试&#xff1f;兼容性测试侧重哪些方面&#xff1f;答&#xff1a;兼容性测试是一种软件测试类型&#xff0c;它的主要目的是确保一个应用程序在不同的操作系统、不同的浏览器、不同的设备、不同的网络环境等各种环境下能够正常运行&#xff0c;并且不会产生…

【并发编程十八】线程局部存储(TLS)

【并发编程十八】线程局部存储(TLS&#xff09;一、定义二、线程局部存储的实现1、windows系统2、linux系统3、c11三、windows系统1、线程局部存储是分块的&#xff08;TLS_MINIMUM_AVAILABLE&#xff09;2、获得索引3、通过索引&#xff1a;存储数据、取出数据4、释放索引和内…

UI自动化测试、接口测试等自动化测试策略

今天跟大家介绍UI测试、接口测试、单元测试主要内容&#xff0c;以及每种测试花费时间讨论。 UI测试【Selenium】 UI测试是最接近软件真实用户使用行为的测试类型。通常是模拟真实用户使用软件的行为&#xff0c;即模拟用户在软件界面上的各种操作&#xff0c;并验证这些操作对…

从0探索NLP——神经网络

从0探索NLP——神经网络 1.前言 一提人工智能&#xff0c;最能想到的就是神经网络&#xff0c;但其实神经网络只是深度学习的主要实现方式。 现在主流的NLP相关任务、模型大都是基于深度学习也就是构建神经网络实现的&#xff0c;所以这里讲解一下神经网络以及简单的神经网络…

Anaconda和PyCharm的一些安装问题和命令

今天更新了Windows上的Anaconda到2.3.2&#xff0c;PyCharm到2022.3。 ——发现是纯纯的犯贱orz。出了一堆问题。在这里记录一下供后来者参考。 Anaconda安装 将.\anaconda3\Scripts 和.\anaconda3\Library\bin添加到系统环境变量中。 新建环境的目录在.\anaconda3\envs下 N…

【黑盒模糊测试】路由器固件漏洞挖掘实战--AFL++ qemu_mode

前言 很久之前就想写AFL++的qemu_mode了,只是模糊测试专题的文章有些过于耗费时间,加上工作原因导致一直搁置。最近需要出差会用到黑盒模糊测试,所以就当做复习一遍,我记得Fuzzing 101也有一个qemu_mode的练习,有空的话下一篇文章更新吧~ 编写不易,如果能够帮助到你,希望…

linux的文件权限介绍

文件权限 在linux终端输入 ls -lh 出现下面界面 介绍 基本信息 其中的开头代表着文件类型和权限 而 root 和kali 则分别代表用户名和用户组名用户名顾名思义就是这个文件属于哪一个用户用户组是说自己在写好一个文件后&#xff0c;这个文件是属于该用户所有&#xff0c;…

Java中的Stack与Queue

文章目录一、栈的概念及使用1.1 概念1.2 栈的使用1.3 栈的模拟实现二、队列的概念及使用2.1 概念2.2 队列的使用2.3 双端队列(Deque)三、相关OJ题3.1 用队列实现栈。3.2 用栈实现队列。总结一、栈的概念及使用 1.1 概念 栈&#xff1a;一种特殊的线性表&#xff0c;其只允许在…

Linux系统安装MySQL8.0版本详细教程【亲测有效】

首先官网下载安装包&#xff1a;https://downloads.mysql.com/archives/community/ 一、上传到安装服务器 二、解压 tar -xvf mysql-8.0.31-linux-glibc2.12-x86_64.tar.xz三、移动位置并重新命名 mv mysql-8.0.31-linux-glibc2.12-x86_64 /usr/local/mysql四、创建mysql用户…

Docker 如何配置镜像加速

Docker 镜像加速 国内从 DockerHub 拉取镜像有时会遇到困难&#xff0c;此时可以配置镜像加速器。Docker 官方和国内很多云服务商都提供了国内加速器服务&#xff0c;例如&#xff1a; 科大镜像&#xff1a;https://docker.mirrors.ustc.edu.cn/网易&#xff1a;https://hub-…

代码随想录【Day21】| 530. 二叉搜索树的最小绝对差、501. 二叉搜索树中的众数、236. 二叉树的最近公共祖先

530. 二叉搜索树的最小绝对差 题目链接 题目描述&#xff1a; 给你一棵所有节点为非负值的二叉搜索树&#xff0c;请你计算树中任意两节点的差的绝对值的最小值。 示例&#xff1a; 提示&#xff1a;树中至少有 2 个节点。 难点&#xff1a; 解答错误&#xff01;仅考虑了…

【Npde.js】express以及nodemon

express初始Express什么是Express不使用Express可以创建web服务器吗&#xff1f;Express能做什么安装Express监听GET请求和post请求获取URL中携带的查询参数获取URL中携带的动态参数托管静态资源nodemon为什么使用nodemon初始Express 什么是Express 官方给出的概念&#xff0…

Vue3 基础

Vue3 基础 概述 Vue (发音为 /vjuː/&#xff0c;类似 view) 是一款用于构建用户界面的 JavaScript 框架。它基于标准 HTML、CSS 和 JavaScript 构建&#xff0c;并提供了一套声明式的、组件化的编程模型&#xff0c;帮助你高效地开发用户界面。无论是简单还是复杂的界面&…

Java:Java与Python — 编码大战

Java和Python是目前市场上最热门的两种编程语言&#xff0c;因为它们具有通用性、高效性和自动化能力。两种语言都有各自的优点和缺点&#xff0c;但主要区别在于Java 是静态类型的&#xff0c;Python是动态类型的。它们有相似之处&#xff0c;因为它们都采用了“一切都是对象”…

单片机输入输出模式

单片机输入输出模式输入模式模拟输入、浮空输入、上拉输入、下拉输入GPIO输出模式推挽输出、开漏输出、复用推挽输出、复用开漏输出。上下拉电阻上拉电阻下拉电阻输入模式 模拟输入、浮空输入、上拉输入、下拉输入 模拟输入&#xff1a;I/O端口的模拟信号&#xff08;电压信号…

日志收集笔记(架构设计、Log4j2项目初始化、Lombok)

1 架构设计 ELK 技术栈架构设计图&#xff1a; 从左往右看&#xff0c; Beats&#xff1a;主要是使用 Filebeat&#xff0c;用于收集日志&#xff0c;将收集后的日志数据发送给 Kafka&#xff0c;充当 Kafka 的生产者Kafka&#xff1a;高性能消息队列&#xff0c;主要起缓冲…

关于客户背景调查的两个案例,说下我的真实看法

这篇文章我只是想客观陈述下事实&#xff0c;并没有对他人的贬低与对自己的吹捧之意。只是想通过这样两件小事&#xff0c;传递出来一个观点&#xff1a;在外贸业务开发过程中&#xff0c;很多时候正是那些我们内心抗拒&#xff0c;不愿意沉下心去做的事&#xff0c;才给了我们…

C#与三菱PLC MC协议通信,Java与三菱PLC MC协议通信

三菱PLC的MC协议是一种常用的通信协议&#xff0c;用于实现三菱PLC与其他设备之间的通信。以下是一些关于MC协议的基本信息&#xff1a;协议格式MC协议的通信数据格式如下&#xff1a;数据头网络编号PC编号目标模块IO编号目标模块站号本机模块IO编号本机模块站号请求数据长度请…