数据结构 -- 堆

一.堆的概念

1.1 堆是什么

        堆也叫做优先队列，一些按照重要性或优先级来组织的对象称为优先队列。

1.2 为什么需要堆

        在现实生活中，存在许多需要从一群人、一些任务或一些对象中找出“下一位最重要”目标的情况。例如：在平时处理事情的时候我们总会先把“下一个最重要的”的事情取出来先处理。在处理的过程中，可能还会有其他的事情加进来。因此在事情处理完的事情，我们又要重新找出“下一个最重要”的事情进行处理。

  堆就是处理这种情况的，我们通常把堆中的数据按照一定的重要性进行排序，从而按照顺序一个个取出堆中的元素。

1.3 如何创建一个堆

        通常来说，我们容易想到以下的方法：

        对所有元素进行一次排序然后取出最大值。但这种方法不是很好。它多做了很多无用功。因为其实我可能只要取一个最大值就OK了，但是却画蛇添足地帮我把所有元素都排好序了。很浪费时间。排序的时间复杂度至少为O(nlogn),插入和删除操作的时间复杂度为O(n)。

   而理论上我们所要实现的优先队列的时间复杂度是可以比这个更优的。

二.堆的属性

2.1 定义

  • 堆是一棵（近乎）满二叉树，我们可以用数组来实现这棵二叉树（因为如果是满二叉树的话，其极其符合数组的形式，并且节点也可以用下标来表示，下面会证明）。
  • 堆中的数据是局部有序的。我们使节点储存的值和它的子节点之间存在某种关系,从而利用数组模拟出堆这种形式。

2.2 堆的类型 

  1. 最大值堆：任意一个节点的值都大于它的子节点的值：这样根节点存储的就是这组数据的最大值。
  2. 最小值堆：任意一个节点的值都小于它的子节点的值这样子根节点存储的就是这组数据的最小值。

 

 2.3 堆的特殊规律

  既然堆的逻辑结构是完全二叉树，那么它就同样具有完全二叉树的性质 。

    对于完全二叉树，若从上至下、从左至右编号，以根节点为0开始，则编号为i的节点，其左孩子节点编号为2i+1，右孩子节点编号为2i+2，父亲节点为 (i-1) / 2。 这个规律非常重要！！！

验证：

    一棵节点个数为N的完全二叉树，其高度为 h = log 2 (N+1)，（2为底数）。 

三.堆的实现 

3.1 堆的基本结构

  我们在上面讲解了，对于一个满二叉树形式的结构，我们可以用一个数组来模拟,但有时候我们也可以用其它类型来进行模拟，在库里面，其实底层是一个模板参数，堆可以根据传入的类型来更改底层类型，不过默认为vector.

如下：

namespace My {
	
	template<class T, class Container = vector<T>>
	class Priority_queue 
	{
	public:
	private:
	  Container _con;
	};

}

3.2 堆的向下调整算法 

  向下调整：是让调整的结点与其孩子节点进行比较，若想将其调整为小堆，那么根结点的左右子树必须都为小堆，若想将其调整为大堆，那么根结点的左右子树必须都为大堆，一般用于创建堆。

（小根堆）示例：

  

向下调整算法的基本思想（最小堆示例）：

  1. 从根结点处开始，选出左右孩子中  值较小的孩子。
  2. 让较小的孩子与其父亲进行比较。
  3. 若小的孩子比父亲还小，则该孩子与其父亲的位置进行交换。并将原来小的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。
  4. 若小的孩子比父亲大，则不需处理了，调整完成，整个树已经是小堆了。

注意：这里我们的大根堆和小根堆的大小对比明显是完全不一样的，那么我们就需要写两个向下调整代码吗？ 不，不需要，我们可以在创建一个对象时传入一个仿函数，从而实现让用户自己来控制需要的堆。

  模板修改 + 仿函数实现：

	//构建大根堆函数
	struct Less
	{
		bool operator()(int k1,int k2){
			return k1 < k2;
		}
	};

	//构建小根堆函数
	struct Greater
	{
		bool operator()(int k1, int k2) {
			return k1 > k2;
		}
	};

	//默认构建大根堆
	template<class T,class Kvalue=Less>

向下调整代码的实现：

//在类外，这个函数是完全不需要的，因此设置为private
private:

	void adjust_down(int parent) {
        //构建仿函数
		Compare _com;

		int child = parent * 2 + 1;
		while (child < _con.size()) {
            //判断右节点有没有越界，顺便求出两个节点较大值
			if (child + 1 < _con.size() && _com(_con[child], _con[child + 1])) {
				child++;
			}
            //根据对应仿函数判断是否需要交换
			if (_com(_con[parent], _con[child])) {

				swap(_con[parent], _con[child]);
				parent = child;
				child = parent * 2 + 1;
			}
            //不符合仿函数判断条件直接返回
			else {
				break;
			}
		}
	}

3.3 堆的创建

 我们都知道，堆的底层结构是一个数组类型， 那么我们除了让一个空堆一个个插入，还能直接用一个数组来构建堆吗，答案是完全可以。

 那么我们该如何做呢？ 首先，堆的底层结构就是一个数组类型，那么我们可以直接用堆内的数组 copy 一下 传入的数组，然后按照向下调整算法，构建一个堆。

  从上面的向下调整算法我们得知，我们使用向下调整算法时，需要保证左右两个子树都为堆，因此，单纯的从头节点开始向下调整是不可以的。

  这里，我们可以把最底层的节点看为一个个堆，从最底层开始调整，但是如果从最底层开始调节，又有点太浪费资源，这里建议：

   从最后一个父节点(size/2）-1 的位置逐个往前调整所有父节点（直到根节点）,确保每一个父节点都是一个最大堆，最后整体上形成一个最大堆 。

  ps：因为最后一个父节点，最多只有两个子节点，因此，它的左右子树也必定是一个堆。

	//在C++ 中 我们现在基本都用迭代器构造 因此，创建一个迭代器模板类型
    template <class InputIterator>
	Priority_queue(InputIterator first, InputIterator last)
		:_con(first, last)//直接调用底层数据结构的迭代器构造
	{   //这里减2 的原因是 数组下标的问题 因为从0开始，所以真正的大小应该减一，在带入先前的算法
		for (int i = (_con.size() - 2) / 2; i >= 0; i--) {
			adjust_down(i);
		}
	}

3.4 堆的向上调整代码 

   向上调整：是让调整的结点与其父亲结点进行比较，当我们已经有一个堆，显然我们在头部插入数据，会破坏原有的堆结构，因此我们需要在堆的末尾插入数据，再对其进行调整，使其任然保持堆的结构，这里我们就需要用到堆的向上调整算法。

  

向上调整算法的基本思想：

  1. 将目标结点与其父结点比较
  2. 若目标结点的值比其父结点的值大，则交换目标结点与其父结点的位置
  3. 将原目标结点的父结点当作新的目标结点继续进行向上调整。若目标结点的值比其父结点的值大，则停止向上调整，此时该树已经是大堆了

代码示例：

void adjust_up(int child) {

	Compare _com;
	int parent = (child - 1) / 2;
	while (child > 0) {
		if (_com(_con[parent], _con[child])) {
			swap(_con[child], _con[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
}

3.5 堆的插入

   我们直接对数组进行尾插，然后在插入位置向上调整，因为插入时，只改变插入位置到根这一条路径，因此，只向上调整一次即可。

  代码示例：

	void push(const T& x) {

		_con.push_back(x);
		adjust_up(_con.size() - 1);
	}

3.6 堆的删除

  堆的删除这里我们有特殊的规则，像我们直接删掉尾部的数据，其实是不改变堆的结构的，但那样有意义吗？

  堆本来就起到一个排序的作用，你怎么知道最后一位数据，到底是多少呢？堆只能取到头部的顺序，因此，在我们删除时，是删除头部的数据。

  但是直接删除的话，会把我们的堆结构变得极其混乱，对此，我们提出了另一种解法：

  我们把头元素和尾部元素进行一次交换，然后把新尾部删除，让新头部元素向下调整（这样交换后，头元素的左右依旧是堆结构，只需要一次调整就能得到一个新堆。

  代码如下：

	void pop() {

		swap(_con[0], _con[_con.size() - 1]);
		_con.pop_back();
		adjust_down(0);
	}

3.7 其它接口

	bool empty() const {
		return _con.empty();
	}

	size_t size() const {
		return _con.size();
	}


四.代码测试
  

oid test1() {
		My::Priority_queue < int> pq1;
		pq1.push(5);
		pq1.push(2);
		pq1.push(3);
		pq1.push(9);
		pq1.push(4);

		while (!pq1.empty()) {
			cout << pq1.top()<< endl;
			pq1.pop();
		}
	}

	void test2()
	{
		vector<int> v1 = { 1,3,4,5,8,10,12 };
		Priority_queue<int> q1(v1.begin(), v1.end());
		Priority_queue<int, vector<int>, Greater<int>> q2(v1.begin(), v1.end());


		cout << "size:" << q1.size() << endl;
		while (!q1.empty())
		{
			cout << q1.top() << ' ';
			q1.pop();
		}
		cout << endl;

		cout << "size:" << q2.size() << endl;
		while (!q2.empty())
		{
			cout << q2.top() << ' ';
			q2.pop();
		}
		cout << endl;
		


	}

答案：

 

五.完整代码 

My_Priority_Queue.h

#pragma once
#include<iostream>
#include<vector>

using namespace std;

namespace My {

	template<class T>
	struct Less {
		bool operator()(const T& t1, const T& t2) {
			return t1 < t2;
		}
	};

	template<class T>
	struct Greater {
		bool operator()(const T& t1, const T& t2) {
			return t1 > t2;
		}
	};

	template<class T, class Container = vector<T>, class Compare = Less<T >>
	class Priority_queue {

	public:
		Priority_queue() {
		}

		template <class InputIterator>
		Priority_queue(InputIterator first, InputIterator last)
			:_con(first, last)
		{
			for (int i = (_con.size() - 2) / 2; i >= 0; i--) {
				adjust_down(i);
			}
		}


		bool empty() const {
			return _con.empty();
		}

		size_t size() const {
			return _con.size();
		}

		void push(const T& x) {

			_con.push_back(x);
			adjust_up(_con.size() - 1);
		}

		void pop() {

			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}

		const T& top() {

			return _con[0];
		}

	private:

		void adjust_down(int parent) {

			Compare _com;
			int child = parent * 2 + 1;
			while (child < _con.size()) {

				if (child + 1 < _con.size() && _com(_con[child], _con[child + 1])) {
					child++;
				}

				if (_com(_con[parent], _con[child])) {

					swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else {
					break;
				}
			}
		}

		void adjust_up(int child) {

			Compare _com;
			int parent = (child - 1) / 2;
			while (child > 0) {
				if (_com(_con[parent], _con[child])) {
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else {
					break;
				}
			}
		}

	private:
		Container _con;
	};


	void test1() {
		My::Priority_queue < int> pq1;
		pq1.push(5);
		pq1.push(2);
		pq1.push(3);
		pq1.push(9);
		pq1.push(4);

		while (!pq1.empty()) {
			cout << pq1.top()<< endl;
			pq1.pop();
		}
	}

	void test2()
	{
		vector<int> v1 = { 1,3,4,5,8,10,12 };
		Priority_queue<int> q1(v1.begin(), v1.end());
		Priority_queue<int, vector<int>, Greater<int>> q2(v1.begin(), v1.end());


		cout << "size:" << q1.size() << endl;
		while (!q1.empty())
		{
			cout << q1.top() << ' ';
			q1.pop();
		}
		cout << endl;

		cout << "size:" << q2.size() << endl;
		while (!q2.empty())
		{
			cout << q2.top() << ' ';
			q2.pop();
		}
		cout << endl;
		


	}
}

 test.cc

#include"My_Priority_Queue.h"


int main() {

	try
	{
		My::test2();
	}
	catch (...)
	{
		cout << "未知异常" << endl;
	}

	return 0;
}

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

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

相关文章

事件和事件源

事件和事件源

事件监听 在JS当中写事件监听是这个函数&#xff0c;写了这个函数&#xff0c;前面是DOM对象&#xff0c;当由DOM树和CSSOM树形成的渲染树也有这个监听&#xff0c;这个函数可以添加到DOM树&#xff0c;最后渲染树也有。渲染树会渲染标签当标签发生该事件就会执行这个函数。这个…
阅读更多...
操作系统——进程管理算法和例题

操作系统——进程管理算法和例题

1、概述 1.1 进程调度 当进程的数量往往多于处理机的个数&#xff0c;出现进程争用处理机的现象&#xff0c;处理机调度是对处理机进行分配&#xff0c;就是从就绪队列中&#xff0c;按照一定的算法&#xff08;公平、髙效&#xff09;选择一个进程并将处理机分配给它运行&am…
阅读更多...
Python---搭建Python自带静态Web服务器

Python---搭建Python自带静态Web服务器

1. 静态Web服务器是什么&#xff1f; 可以为发出请求的浏览器提供静态文档的程序。 平时我们浏览百度新闻数据的时候&#xff0c;每天的新闻数据都会发生变化&#xff0c;那访问的这个页面就是动态的&#xff0c;而我们开发的是静态的&#xff0c;页面的数据不会发生变化。 …
阅读更多...
帆软报表 - 数据显示为列表，但是数据仍全部显示在同一行上？

帆软报表 - 数据显示为列表，但是数据仍全部显示在同一行上？

文章目录 1 问题截图2 解决办法3 原因分析3.1 数据设置&#xff1a;全是列表 1 问题截图 想要的效果&#xff1a;每行显示一组数据得到的效果&#xff1a;数据全部显示在一行&#xff0c;以逗号隔开 2 解决办法 修改扩展方向。将 “不扩展” 修改为 “纵向” 3 原因分析 3.1…
阅读更多...
消除蛋蛋派

消除蛋蛋派

欢迎来到程序小院 消除蛋蛋派 玩法&#xff1a;消除游戏&#xff0c;三个相同形状的蛋蛋连成一条直线即可消除&#xff0c;点击鼠标左键移动球球进行消除&#xff0c; 可以使用道具&#xff0c;共有50关卡&#xff0c;快去闯关吧^^。开始游戏https://www.ormcc.com/play/gameS…
阅读更多...
3. BlazorSignalRApp 结合使用 ASP.NET Core SignalR 和 Blazor

3. BlazorSignalRApp 结合使用 ASP.NET Core SignalR 和 Blazor

参考&#xff1a;https://learn.microsoft.com/zh-cn/aspnet/core/blazor/tutorials/signalr-blazor?viewaspnetcore-8.0&tabsvisual-studio 1.创建新项目 BlazorSignalRApp 2.添加项目依赖项 依赖项&#xff1a;Microsoft.AspNetCore.SignalR.Client 方式1 管理解决方案…
阅读更多...
c语言：文件操作（2），认识各种文件操作函数

c语言：文件操作（2），认识各种文件操作函数

fgets 作用 fgets是C语言标准库中用于从文件中读取字符串的函数。 fgets函数从指定的文件流stream中读取最多n-1个字符&#xff0c;或者直到遇到换行符&#xff08;包括换行符在内&#xff09;&#xff0c;并将其存储到以str指向的字符数组中。读取的字符串会以null字符\0结…
阅读更多...
模拟电路基础知识经典 200问，收藏这些就够了！

模拟电路基础知识经典 200问，收藏这些就够了！

大家总说模电知识总是学不会&#xff0c;IC修真院为大家整理了模电经典200问&#xff0c;看看你掌握了多少&#xff0c;文末可以获取全部哦。 文末可领全部文档 1、半导体材料制作电子器件与传统的真空电子器件相比有什么特点? 答&#xff1a;频率特性好、体积小、功耗小&…
阅读更多...
信息收集 - 谷歌hack

信息收集 - 谷歌hack

搜索引擎 FOFA网络空间测绘：https://fofa.info/ FOFA（FOcus on Assets）是一个网络空间搜索引擎，可以帮助用户快速定位和收集特定目标的信息。 ZoomEye：https://www.zoomeye.org ZoomEye 是一个网络空间搜索引擎，可以用于发现和收集特定目标的网络设备、Web应用程序、开放…
阅读更多...
OpenCV-Python(18):图像梯度

OpenCV-Python(18):图像梯度

目录 背景介绍及应用 学习目标 原理 Sobel算子和Scharr算子 Laplacian 算子 代码示例 重要提醒 背景介绍及应用 图像的梯度是指图像中每个像素点的强度变化情况。计算图像的梯度可以帮助我们了解图像中物体的边界和纹理等信息。梯度在计算机视觉和图像处理领域有着广泛…
阅读更多...
【Amazon 实验③】Amazon WAF功能增强之追踪 Amazon WAF RequestID，排查误杀原因

【Amazon 实验③】Amazon WAF功能增强之追踪 Amazon WAF RequestID，排查误杀原因

文章目录 1. 方案介绍2. 架构图3. 操作演示 本实验将介绍如何利用 Amazon LambdaEdge&#xff0c;在 Amazon CloudFront 自定义错误页面 上展示每个由 Amazon WAF 返回的“403 Forbidden”错误的 Request ID。通过这个唯一的 WAF Request ID&#xff0c;网站运维工程师能够快速…
阅读更多...
Swift 周报 第四十一期

Swift 周报 第四十一期

文章目录 前言新闻和社区2024 年 Swift Student Challenge 公布现推出超过 30 个新的开发者活动 提案正在审查的提案 Swift论坛话题讨论推荐博文关于我们 前言 本期是 Swift 编辑组整理周报的第四十一期&#xff0c;每个模块已初步成型。各位读者如果有好的提议&#xff0c;欢…
阅读更多...
不受父容器大小约束的TextView

不受父容器大小约束的TextView

序言 为了实现以下效果&#xff0c;特意开发了一个自定义控件。主要是红色的点赞数和评论数。 问题分析 自定义控件 该控件主要是在于忽略的父容器的大小限制&#xff0c;这样可以展示出全部内容。注意父容器的属性中需要下列配置。 package com.trs.myrb.view.count;impor…
阅读更多...
[JS设计模式]Flyweight Pattern

[JS设计模式]Flyweight Pattern

Flyweight pattern 享元模式是一种结构化的设计模式&#xff0c;主要用于产生大量类似对象而内存又有限的场景。享元模式能节省内存。 假设一个国际化特大城市SZ&#xff1b;它有5个区&#xff0c;分别为nanshan、futian、luohu、baoan、longgang&#xff1b;每个区都有多个图…
阅读更多...
Java 基础学习（十三）集合框架、List集合

Java 基础学习（十三）集合框架、List集合

1 集合框架 1.1 Collection 1.1.1 集合框架概述 Java 集合框架是一组实现了常见数据结构&#xff08;如列表、树集和哈希表等&#xff09;的类和接口&#xff0c;用于存储一组数据。 开发者在使用Java的集合类时&#xff0c;不必考虑数据结构和算法的具体实现细节&#xff…
阅读更多...
使用selenium webdriver和mitmproxy代理模拟用户点击抓包（抓华为应用商城app数据）

使用selenium webdriver和mitmproxy代理模拟用户点击抓包（抓华为应用商城app数据）

文章目录 安装PythonMacWindows 安装程序需要的依赖安装chorm驱动编写代码自动化程序开始抓包 问题处理 本文简单记录一下使用selenium webdriver和mitmproxy代理模拟用户点击抓包的过程。 用于模拟真实的用户访问网站&#xff0c;达到抓包的目的。 作者水平有限&#xff0c;可…
阅读更多...
深度解析自动化测试流程(纯干货)

深度解析自动化测试流程(纯干货)

今天就通过这篇文章给大家深度解析一下自动化测试的流程。 自动化测试的流程和功能测试其实挺相似的&#xff0c;整个流程也是按照需求分析及测试计划阶段、测试设计阶段、测试执行和测试总结阶段&#xff0c;总结下来就是下面一张图&#xff0c;ppt中纯手绘&#xff0c;效果不…
阅读更多...
天猫数据分析（软件工具）-2023年11月天猫保健品行业分析报告：市场需求扩容，年轻人是主流群体

天猫数据分析（软件工具）-2023年11月天猫保健品行业分析报告：市场需求扩容，年轻人是主流群体

近年来&#xff0c;随着健康经济、颜值经济的兴起&#xff0c;越来越多的年轻人加入养生大军&#xff0c;成为保健食品市场上的一股新力量&#xff0c;带动市场扩容。根据鲸参谋电商数据分析平台的相关数据显示&#xff0c;今年11月份&#xff0c;天猫平台上保健食品的销量为24…
阅读更多...
怎么提取视频中的背景音乐？

怎么提取视频中的背景音乐？

当我们在刷视频的时候&#xff0c;有时候听到一个背景音乐很好听&#xff0c;但是又不知道歌名&#xff0c;比如英语歌&#xff0c;这个时候我们很难找到这首歌&#xff0c;相信有很多朋友会遇到这样的问题&#xff0c;不知道怎么弄&#xff0c;下面小编给大家推荐一些方法帮助…
阅读更多...
主流数据库体系结构

主流数据库体系结构

MySQL 我们通常所说的 MySQL 数据库服务器由一个实例&#xff08;instance&#xff09;以及一个数据库&#xff08;database&#xff09;组成。实例包括一组后台进程/线程和许多内存结构&#xff0c;用于管理数据库&#xff1b;数据库由一组磁盘文件组成&#xff0c;用于存储数…
阅读更多...
最新文章

Copyright @ 2022~2023