【数据结构】堆和priority_queue

堆的定义

堆是什么？实际上堆是一种特殊的（受限制的）完全二叉树，它在完全二叉树的基础上要求每一个节点都要大于等于或者小于等于它的子树的所有节点。这个大于小于体现在节点的值或者权重。

如图所示：
根节点大于等于子树中所有节点的堆叫做大顶堆（大根堆）
根节点小于等于子树中所有节点的堆叫做小顶堆（小根堆）
在这里插入图片描述

堆的存储

堆属于完全二叉树，因此使用二叉树的顺序存储结构来存储堆是最优的。

堆的核心操作（默认以大根堆为标准）

向上调整算法

一般使用背景：

在堆的最后面插入一个元素之后，要将这个节点调整到正确的位置。

流程：

将该节点的值直接与父节点相比较，如果比父节点大就要与父节点交换。重复此步骤一直到比父节点小 或者 已经换到了根节点，就完成了向上调整，此时这个新来的节点就已经被调整到了正确的位置。

注意事项：

向上调整算法就是子节点要跟父节点换，一个子节点的父节点只有一个，所以直接交换即可。

代码实现

//向上调整 
void up(int child) //传入要调整的节点的下标（下标具有唯一性，堆中允许节点的值相同） 
{
	int parent = child / 2;
	while(parent >= 1 && heap[child] > heap[parent]) // 这里必须是parent >= 1 ，不能是parent > 1 。 parent > 1时，如果该节点是最大的，那么只能被调整到堆顶的子节点的位置。
	{
		swap(heap[child],heap[parent]);
		//被换掉的那个元素就不管了，它已经在正确的位置上了，现在我们要更新child节点 ，然后再由公式得出parent节点 
		child = parent;
		parent = child / 2;
	}
}

向下调整算法

一般使用背景：

先了解堆pop()的原理是什么？
堆pop()删除堆顶元素的逻辑是将目前的堆顶元素与堆的最后一个元素交换，然后将堆的大小-1，这样就访问不到最后的那个元素了（原来的堆顶元素）。

在删除堆顶元素之后，本身在最后位置的元素来到了堆顶（根部），这时候的堆只有左右子树是合法的，整体是不合法的，所以就要进行向下调整算法，将目前的堆顶元素调整到正确的位置。

流程：

将要向下调整的节点的值与两个子节点中最大的那个值相比较，如果该节点的值比子节点的最大值要小，就交换。重复此步骤，直到该节点的值比子节点的最大值大 或者 已经被换到了叶子节点，那么此时该节点就被调整到了正确的位置。

注意事项：

向下调整算法是父节点要跟子节点换，一个父节点最多有两个子节点，所以我们要找出最大的那个子节点作比较。

代码实现

//向下调整 
void down(int parent)
{
	int child = parent * 2; //先默认指向左节点 思考：child是两倍的parent得到的，这个时候有没有可能超出了n呢？所以要先判断child是否存在 
	while(child <= n) //孩子存在才有下文   
	{
		if(child + 1 <=n && heap[child] < heap[child + 1]) child++;
		if(heap[parent] >= heap[child]) return; //heap[parent] >= heap[child]比heap[parent] > heap[child]少走一步，但都是正确的
		swap(heap[parent],heap[child]);
		parent = child;
		child = parent * 2;
		
	}
}

堆的模拟实现

//默认建大根堆 
#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int n,heap[N]; //n用来记录heap存放的有效元素个数，heap用来存储堆的数据，父子关系是靠公式计算得来（堆是完全二叉树） 

//向上调整 
void up(int child) 
{
	int parent = child / 2;
	while(parent >= 1 && heap[child] > heap[parent])
	{
		swap(heap[child],heap[parent]);
		child = parent;
		parent = child / 2;
	}
}

//向下调整
void down(int parent)
{
	int child = parent * 2;  
	while(child < n)   
	{
		if(heap[child] < heap[child + 1]) child++;
		if(heap[parent] >= heap[child]) return;
		swap(heap[parent],heap[child]);
		parent = child;
		child = parent * 2;
		
	}
}

void push(int x)
{
	heap[++n] = x; //最刚开始n=0，存入第一个元素的时候++n，是在1的位置存入，0的位置没有任何元素 
	up(n);
}

void pop()
{
	swap(heap[1],heap[n]);
	n--;
	down(1); //要搞清楚堆的根存放在哪里
}

int size()
{
	return n;
}

int top() 
{
	return heap[1];
}

int main() 
{
	int a[10] = {1, 41, 23, 10, 11, 2, -1, 99, 14, 0};
	
	for(int i=0;i<sizeof(a)/sizeof(int);i++)
	{
		push(a[i]);
	}
	
	while(size())
	{
		cout << top() << " ";
		pop();
	}
	
	
	return 0;
}

运行结果：
在这里插入图片描述

注意：这个top实际上是有bug的，就是在没有元素的时候是不能调用这个接口的，这样的条件检查我们不在函数内实现，而是在调用前进行检查。同样的，有一个在做题时遇到的小细节值得注意，也是关于栈中top接口的调用。

题外话

P4387 【深基15.习9】验证栈序列

题目描述

给出两个序列 pushed 和 poped 两个序列，其取值从 1 到 n ( n ≤ 100000 ) n(n\le100000) n(n≤100000)。已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出 Yes，否则输出 No。为了防止骗分，每个测试点有多组数据，不超过 5 5 5 组。

输入格式

第一行一个整数 q q q，询问次数。

接下来 q q q 个询问，对于每个询问：

第一行一个整数 n n n 表示序列长度；

第二行 n n n 个整数表示入栈序列；

第三行 n n n 个整数表示出栈序列；

输出格式

对于每个询问输出答案。

输入输出样例 #1

输入 #1

2
5
1 2 3 4 5
5 4 3 2 1
4
1 2 3 4
2 4 1 3

输出 #1

Yes
No

这是我当时的代码：

#include<iostream>
#include<stack>
using namespace std;

const int N = 1e5 + 10; 
int in[N],out[N];

int main()
{	
	int q;
	cin >> q;
	while(q--)
	{
		stack<int> st; //栈必须放在循环内，要不然每次重新接受数据前要清空栈元素 
		int n;
		cin >> n;
		for(int i=1;i<=n;i++) cin >> in[i];	
		for(int i=1;i<=n;i++) cin >> out[i];
		int t = 1; //t指针指向out的第一个元素 
		for(int i=1;i<=n;i++)
		{
			st.push(in[i]);
			while(t <= n && st.top() == out[t] && st.size()) 
			//t <= n不能丢，要不然两个序列完全匹配的时候t就会加到n+1，那样就死循环了 
			{
				st.pop(); 
				t++;
			}
		}
		if(st.size()) cout << "No" << endl;
		else cout << "Yes" << endl;
	}
	
	return 0;
}

看起来似乎没有问题，但是当时一直报错 runtime error ，我也不知道错在哪，到最后才注意到， while() 语句中用 && 连接的连续条件判断是从左到右执行的，在 st.top() 调用之前应该确保栈不为空，所以 st.size() 的检查一定要放在 st.top() == out[t] 的前面。

使用 &&（逻辑与）连接的多个条件判断是有顺序的，这与 C++ 的短路求值（short-circuit evaluation）机制有关。
C++ 在使用 && 连接多个条件时，会从左到右依次评估每个条件表达式。如果左侧的条件已经为 false，则右侧的条件表达式不会被求值，因为无论右侧条件是什么，整个 && 表达式的结果都会是 false。这种行为被称为短路求值。

int a = 0;
int b = 5;

while (a != 0 && b / a > 1) {
    // do something
}

在这个例子中，a != 0 会被首先评估。如果 a 为 0，b / a > 1 这一部分的表达式将不会被求值，避免了除以零的错误。&& 运算符是有顺序的，并且遵循短路求值规则。左侧条件为 false 时，右侧条件不会被求值。

priority_queue

普通的队列是先进先出(FIFO)的结构，priority_queue是一种基于堆实现的优先级队列，priority_queue中的元素都是有优先级的，它在插入元素时，即使是在队尾插入，也会根据优先级调整到相对应的位置，优先级越高越靠近队头的位置。同样删除元素也是删除优先级最高的元素。

priority_queue 的模板定义

priority_queue 的模板定义如下：

template <class T, class Container = std::vector<T>, class Compare = std::less<T>>
class priority_queue;

T：存储的数据类型（如 int）。
Container：底层存储结构，默认是 std::vector（但也可以用 std::deque 等）。
Compare：比较函数对象，决定优先级顺序，默认是 std::less（最大堆）。
默认是 大根堆，std::less 表示大的值优先，std::greater 表示小的值优先。
就是这个比较反人性，跟常规的比较函数是反过来的。

简单创建priority_queue（这样创建默认是大根堆）

#include<iostream>
#include<queue>

using namespace std;

int main()
{
	priority_queue<int> heap; //默认大根堆
	int a[10] = {1, 41, 23, 10, 11, 2, -1, 99, 14, 0};
	
	for(int i=0;i<sizeof(a)/sizeof(int);i++)
	{
		heap.push(a[i]);
	}
	
	while(heap.size())
	{
		cout << heap.top() << " ";
		heap.pop();
	}
	
	return 0;
}

运行结果：
在这里插入图片描述

创建基本数据类型的优先级队列（可将int替换成其他基本数据类型）

#include<iostream>
#include<queue>

using namespace std;

int a[10] = {1, 41, 23, 10, 11, 2, -1, 99, 14, 0};

void test1()
{
	//priority_queue<数据类型，实现结构，排序方式>
	//大根堆 
	priority_queue<int,vector<int>,less<int>> heap1;
	//小根堆 
	priority_queue<int,vector<int>,greater<int>> heap2;
	
	for(int i=0;i<10;i++)
	{
		heap1.push(a[i]); 
	} 
	while(heap1.size())
	{
		cout << heap1.top() << " ";
		heap1.pop(); 
	}
	
	cout << endl; 
	
	for(int i=0;i<10;i++)
	{
		heap2.push(a[i]); 
	} 
	while(!heap2.empty())
	{
		cout << heap2.top() << " ";
		heap2.pop(); 
	}
} 

int main()
{
	test1();
	
	return 0;
}

运行结果：
在这里插入图片描述

创建结构体数据类型的优先级队列

当 priority_queue 存储的是 结构体 而不是基本类型，C++ 不会默认知道如何比较结构体的优先级。因此我们必须提供比较方式，否则会导致编译错误。

方式一：重载运算符operator<

#include <iostream>
#include <queue>
#include <vector>

struct Person {
    std::string name;
    int age;

    // 重载 < 运算符，默认用于 std::priority_queue
    bool operator<(const Person& other) const 
    {
        return age < other.age; // 年龄大的优先级更高（最大堆）
    }
};

int main() {
    std::priority_queue<Person> pq;
    
    pq.push({"Alice", 25});
    pq.push({"Bob", 30});
    pq.push({"Charlie", 20});

    while (!pq.empty()) 
    {
        std::cout << pq.top().name << " " << pq.top().age << std::endl;
        pq.pop();
    }

    return 0;
}

运行结果：
在这里插入图片描述

方式二：使用自定义比较函数

可以提供一个 自定义比较函数 作为 priority_queue 的第三个模板参数。
这时 priority_queue 的第三个参数的定义：class Compare = std::less ，要求传入的是一个类型，而不是普通函数，所以这个比较函数必须是一个可调用对象。那么自定义比较函数 不能是普通函数，而一般需要使用结构体（仿函数）或 lambda 表达式。

#include <iostream>
#include <queue>
#include <vector>

struct Person {
    std::string name;
    int age;
};

// 自定义比较仿函数
struct ComparePerson {
    bool operator()(const Person& a, const Person& b) {
        return a.age > b.age; // 年龄小的优先级更高（最小堆）
    }
};

int main() {
    std::priority_queue<Person, std::vector<Person>, ComparePerson> pq;

    pq.push({"Alice", 25});
    pq.push({"Bob", 30});
    pq.push({"Charlie", 20});

    while (!pq.empty()) {
        std::cout << pq.top().name << " " << pq.top().age << std::endl;
        pq.pop();
    }

    return 0;
}

方式三：使用 Lambda 表达式

C++11 之后，可以用 lambda 来替代仿函数。
如果 不想写额外的比较结构体，可以直接使用 Lambda 作为比较函数：

#include <iostream>
#include <queue>
#include <vector>

struct Person {
    std::string name;
    int age;
};

int main() {
    // Lambda 比较函数
    auto cmp = [](const Person& a, const Person& b) {
        return a.age > b.age; // 年龄小的优先级更高（最小堆）
    };

    std::priority_queue<Person, std::vector<Person>, decltype(cmp)> pq(cmp);//decltype(cmp) 自动推导 Lambda 类型

    pq.push({"Alice", 25});
    pq.push({"Bob", 30});
    pq.push({"Charlie", 20});

    while (!pq.empty()) {
        std::cout << pq.top().name << " " << pq.top().age << std::endl;
        pq.pop();
    }

    return 0;
}

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

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

相关文章

大语言模型学习--本地部署DeepSeek

大语言模型学习--本地部署DeepSeek

本地部署一个DeepSeek大语言模型 研究学习一下。 本地快速部署大模型的一个工具 先根据操作系统版本下载Ollama客户端 1.Ollama安装 ollama是一个开源的大型语言模型&#xff08;LLM&#xff09;本地化部署与管理工具&#xff0c;旨在简化在本地计算机上运行和管理大语言模型…
阅读更多...
1.Big-endian/ little endian大端对齐、小端对齐

1.Big-endian/ little endian大端对齐、小端对齐

一、大端模式、小端模式的介绍 Little endian&#xff1a;是低位字节排放在内存的低地址端、高位字节排放在内存的高地址端。 Big-endian&#xff1a;是高位字节排放在内存的低地址端、低位字节排放在内存的高地址端。 西门子是大端模式&#xff0c;因为比如 MW100 MB100(高位…
阅读更多...
基于Python的PDF特殊字体提取器开发实践

基于Python的PDF特殊字体提取器开发实践

基于Python的PDF特殊字体提取器开发实践 一、应用背景与功能概述 在PDF文档处理场景中&#xff0c;我们常常需要针对特定格式的文本内容进行提取分析。本文介绍的"PDF特殊字体提取器"是一款基于Python开发的桌面应用程序&#xff0c;主要解决以下业务需求&#xff…
阅读更多...
【基础4】插入排序

【基础4】插入排序

核心思想 插入排序是一种基于元素比较的原地排序算法&#xff0c;其核心思想是将数组分为“已排序”和“未排序”两部分&#xff0c;逐个将未排序元素插入到已排序部分的正确位置。 例如扑克牌在理牌的时候&#xff0c;一般会将大小王、2、A、花牌等按大小顺序插入到左边&…
阅读更多...
搭建laravle 数字产品销售平台 php

搭建laravle 数字产品销售平台 php

一个专为单一供应商设计的数字市场平台&#xff0c;旨在为销售数字产品和服务提供一站式解决方案。无论是软件、电子书、音乐、视频还是其他类型的数字内容&#xff0c;都能帮助商家高效地管理和销售他们的数字商品。 主要特点 单一供应商模式&#xff1a;专注于单一品牌或供应…
阅读更多...
flink集成tidb cdc

flink集成tidb cdc

Flink TiDB CDC 详解 1. TiDB CDC 简介 1.1 TiDB CDC 的核心概念 TiDB CDC 是 TiDB 提供的变更数据捕获工具&#xff0c;能够实时捕获 TiDB 集群中的数据变更&#xff08;如 INSERT、UPDATE、DELETE 操作&#xff09;&#xff0c;并将这些变更以事件流的形式输出。TiDB CDC 的…
阅读更多...
大模型——打造自己的AI搜索引擎

大模型——打造自己的AI搜索引擎

大模型系列——打造自己的AI搜索引擎 你可能听说过 Perplexity，这是一个引起轰动的 AI 搜索引擎，但它是收费的。本文介绍使用开源 AI工具创建本地 Perplexity 的替代方案。 你可能听说过 Perplexity，这是一个引起轰动的 AI 搜索引擎。与传统搜索相比，它提供简洁、综合的查…
阅读更多...
五、并发爬虫

五、并发爬虫

本节聚焦于使用协程、线程、进程实现并发爬虫任务。 Python 线程受全局解释器锁&#xff08;GIL&#xff09;制约&#xff0c;同一时刻仅能执行一个线程&#xff0c;无法充分利用多核 CPU 优势&#xff0c;且频繁切换线程会增加开销&#xff0c;影响爬虫性能。 协程是轻量级线程…
阅读更多...
Avalonia 中文乱码

Avalonia 中文乱码

代码字体文件设置成支持中文的&#xff0c;但是编译的代码还是显示的乱码&#xff0c;原因是代码文件的文件编码格式不支持中文导致的。 如下面的2个页面一部分中文显示正常&#xff0c;一部分显示正常&#xff0c;一部分显示乱码。
阅读更多...
Verilog学习方法—基础入门篇（一）

Verilog学习方法—基础入门篇（一）

前言&#xff1a; 在FPGA开发中&#xff0c;Verilog HDL&#xff08;硬件描述语言&#xff09;是工程师必须掌握的一项基础技能。它不仅用于描述数字电路&#xff0c;还广泛应用于FPGA的逻辑设计与验证。对于初学者来说&#xff0c;掌握Verilog的核心概念和基本语法&#xff0…
阅读更多...
PCB电路板基础知识与应用详解：结构与工作原理

PCB电路板基础知识与应用详解：结构与工作原理

电路板&#xff0c;简称PCB&#xff08;Printed Circuit Board&#xff09;&#xff0c;是电子设备的核心部分&#xff0c;几乎所有现代电子产品都离不开电路板的支撑。本文将带您全面了解电路板的基本结构、工作原理及其在电子工程中的重要作用。 什么是电路板&#xff1f; 电…
阅读更多...
使用Qt调用HslCommunication（C++调用C#库）

使用Qt调用HslCommunication（C++调用C#库）

使用C/CLI 来调用C#的dll 任务分解&#xff1a; 1、实现C#封装一个调用hsl的dll&#xff1b; 2、实现C控制台调用C#的dll库&#xff1b; 3、把调用C#的dll用C再封装为一个dll&#xff1b; 4、最后再用Qt调用c的dll&#xff1b; 填坑&#xff1a; 1、开发时VS需要安装CLI项目库…
阅读更多...
标签的ref属性 vue中为什么不用id标记标签

标签的ref属性 vue中为什么不用id标记标签

标签的ref属性 vue中为什么不用id标记标签 假设有一对父子组件&#xff0c;如果父组件和子组件中存在id相同的标签&#xff0c;会产生冲突。通过id获取标签会获取到先加载那个标签。 标签的ref属性的用法 在父组件App中&#xff0c;引入了子组件Person。 并使用ref标记了Pe…
阅读更多...
嵌入式硬件发展历程

嵌入式硬件发展历程

微型计算机架构&#xff1a;CPURAM存储设备 以前常把CPU称为MPU,但现在随着发展&#xff0c;分为两条道路&#xff1a; 一、发展历程 1、集成 然后把CPURAMFlash其他模块集成在一起&#xff0c;就称为MCU也称单片机&#xff0c;他们Flash和RAM比较小&#xff0c;运行裸机程…
阅读更多...
Java进阶：Zookeeper相关笔记

Java进阶：Zookeeper相关笔记

概要总结&#xff1a; ●Zookeeper是一个开源的分布式协调服务&#xff0c;需要下载并部署在服务器上(使用cmd启动&#xff0c;windows与linux都可用)。 ●zookeeper一般用来实现诸如数据订阅/发布、负载均衡、命名服务、集群管理、分布式锁和分布式队列等功能。 ●有多台服…
阅读更多...
Java spring客户端操作Redis

Java spring客户端操作Redis

目录 一、创建项目引入依赖 二、controller层编写 &#xff08;1&#xff09;String类型相关操作测试&#xff1a; &#xff08;2&#xff09;List类型相关操作测试&#xff1a; &#xff08;3&#xff09;Set类型相关操作测试&#xff1a; &#xff08;4&#xff09;Has…
阅读更多...
TMS320F28P550SJ9学习笔记1：CCS导入工程以及测试连接单片机仿真器

TMS320F28P550SJ9学习笔记1：CCS导入工程以及测试连接单片机仿真器

学习记录如何用 CCS导入工程以及测试连接单片机仿真器 以下为我的CCS 以及驱动库C2000ware 的版本 CCS版本&#xff1a; Code Composer Studio 12.8.1 C2000ware &#xff1a;C2000Ware_5_04_00_00 目录 CCS导入工程&#xff1a; 创建工程&#xff1a; 添加工程&#xff1a; C…
阅读更多...
【Java学习】String类变量

【Java学习】String类变量

面向对象系列七 一、String类似复刻变量 1.似复刻变量 1.1结构 1.2常量池检查 1.3构造方法 1.4""形式 1.5引用 2、字符数组 2.1不可变性 2.2常创性 二、String类变量里的方法 1.获取 1.1引用获取&#xff1a; 1.2字符获取&#xff1a; 1.3数组获取 1.…
阅读更多...
3.1、密码学基础

3.1、密码学基础

目录 密码学概念与法律密码安全分析密码体制分类 - 私钥密码/对称密码体制密码体制分类 - 公钥密码/非对称密码体制密码体制分类 - 混合密码体制 密码学概念与法律 密码学主要是由密码编码以及密码分析两个部分组成&#xff0c;密码编码就是加密&#xff0c;密码分析就是把我们…
阅读更多...
【问题解决】Jenkins使用File的exists()方法判断文件存在，一直提示不存在的问题

【问题解决】Jenkins使用File的exists()方法判断文件存在，一直提示不存在的问题

小剧场 最近为了给项目组提供一个能给Java程序替换前端、后端的增量的流水线&#xff0c;继续写上了声明式流水线。 替换增量是根据JSON配置文件去增量目录里去取再替换到对应位置的&#xff0c;替换前需要判断增量文件是否存在。 判断文件是否存在&#xff1f;作为一个老Ja…
阅读更多...
最新文章

Copyright @ 2022~2023