DPDK入门(环境搭建以及小demo)

文章目录

  • 零、从`0`开始配置`dpdk`环境的虚拟机
  • 一、`dpdk`的编译`usertool/dpdk-setup.sh`
  • 二、`dpdk`需要什么配置来支持
    • 1.多队列网卡
    • 2.巨页
  • 三、解析接收网络数据的过程经历了什么
    • 1.物理网卡
    • 2.`NIC`
    • 3.内核协议栈
    • 4.标准接口层`Posix API`
    • 5. 应用层
    • 上述过程发生的拷贝
  • 四、`DPDK`介绍
    • 基于上述接收网络数据流程`dpdk`做的事
    • `dpdk`如何组织映射的数据
      • `Huge Page`
    • `dpdk`优化了什么
    • `KNI`机制
    • `DPDK`的技术边界
      • `DPDK`能做什么
  • 五、`DPDK`该怎么学
  • 六、`coding`
    • `rte_eal_init(argc, argv)`初始化`dpdk`应用
    • `rte_pktmbuf_pool_create`创建
    • 对网口的配置
    • 接受数据
      • 使用`API`接受数据
      • 循环遍历解析所有接受到的包
  • **关于`dpdk`无法接收来自主机的数据解决**
    • 重启虚拟机后需要做的事

零、从0开始配置dpdk环境的虚拟机

  • 外部配置

    • 配置网卡

      • 初始网卡选择桥接模式作为dpdk运行的网卡,添加第二张网卡NAT模式用于ssh连接

      • 内存与CPU核数选择

        • 内存选择8g以上,核数选择8核以上
    • 修改源文件让网卡支持多队列

      • 修改虚拟机的vmx文件,修改ethernet0.virtualDev = "e1000"的值并添加一行
      ethernet0.virtualDev = "vmxnet3"
      ethernet0.wakeOnPcktRcv = "TRUE"
      
  • 内部配置

    • 配置网卡

      • 在安装``ubunt_userver时,存在多个网卡时需要选择默认网关网卡,这里选择用于ssh连接网卡ens33`

      • ens160是多队列网卡,配置其静态ip地址,在/etc/network/interface追加下面行

        auto ens160
        iface ens160 inet static
        address 10.17.43.34
        netmask 255.255.0.0
        

        ip需要根据主机的ip地址的网段和掩码一致,因为这是桥接模式,第二章nat网卡直接使用dhcp自动获取ip网关dns服务器即可

        使用route -n可以查看默认网关

    • 修改系统启动参数

      • 修改etc/default/grub文件

        GRUB_CMDLINE_LINUX_DEFAULT=""
        GRUB_CMDLINE_LINUX=""
        >>>>修改后
        GRUB_CMDLINE_LINUX_DEFAULT="quiet"
        GRUB_CMDLINE_LINUX="find_preseed=/preseed.cfg noprompt net.ifnames=0 biosdevname=0 default_hugepages=1G hugepagesz=2M hugepages=1024 isolCPUs=0-2"
        

        修改后update-grubreboot会发现网卡名字变为了eth*,此时修改/etc/network/interfaces文件

        • eth0对应第一张也就是桥接模式的网卡,就替换ens160
        • eth1替换ens33

一、dpdk的编译usertool/dpdk-setup.sh

  • 下载dpdk-19.08.2,在dpdk-stable-19.08.2文件夹下执行./usertools/dpdk-setup.sh

  • 选择不带appx86_64-native-linux-gcc[39],因为它可以改源码

  • 设置运行时环境变量

    export RTE_SDK=/home/ljq/share/module/dpdk-stable-19.08.2/
    
  • 设置运行时环境的目标

    export RTE_TARGET=x86_64-native-linux-gcc
    
  • ./usertools/dpdk-setup.sh选择[43] or [44]插入IGB_UIO模块 or插入V

  • 选择[45]插入KNI模块

  • 选择[46] or [47]巨页的配置

    • 46代表采用no numa方式管理多内存编号,47代表采用numa方式管理多内存编号

      numa表示不是同一的编码方式,每个内存块都从索引0开始,no-numa表示同一编码方式,内存块之间的索引是连着的

    • 512来设置1g的巨页

  • 选择[49] or [50]

    • 把对应网卡的绑定设备绑定在哪个模块上[49]->UIO [50]->VFIO

    • 两者选一个 我选49

      • 接着输入PCI地址来绑定IGB UIO

        找到eth0对应的行,输入其前面的数字字符串 我的是0000:03:00.0

        回车后会警告:

        Warning: routing table indicates that interface 0000:03:00.0 is active. Not modifying OK,意思是还在工作中 没有修改成功

        我们要给他down掉,就是不让对应的NIC接收数据,让dpdk去绑定这个网卡去截获,网卡的数据就不会往内核里面走了

        ifconfig eth0 down

        再次选择49,输入0000:03:00.0后绑定成功

        此时ifconfig是不存在eth0,也就是说明此时eth0对应的NIC不会再去接管他了,之后所有数据就是走到dpdk里面了

编译前需要安装的

sudo apt-get install libnuma-dev libpcap-dev make

dpdk接管网卡的两种方式

  • 通用型IO
  • 虚拟IO

注意有可能45出会出现错误,此时使用grep CONFIG_RTE_KNI /boot/config-$(uname -r)查看CONFIG_RTE_KNI是否被设置为了m或者y,如果没有则需要手动添加进去

二、dpdk需要什么配置来支持

1.多队列网卡

dpdk要指定用哪一个队列来接收数据

2.巨页

三、解析接收网络数据的过程经历了什么

1.物理网卡

  • 物理网卡接收(vmware的网络适配器就是一个网卡,是vmware模拟的)
  • 物理网卡是光信号或者电信号与数字信号的相互转换

2.NIC

  • 接收后每个网卡都会配对的有一个网络适配器(NIC
    • 问题,NIC什么数据结构存?
    • 使用ifconfig就是查看NIC的数量以及相关信息
    • 网卡每来一帧数据NIC都会将它组织成sk_buff(其中有很多指针,指向数据包中的各个层的头部),发送给协议栈,协议栈就解析其各个头

3.内核协议栈

  • NIC把数据抛给内核协议栈,协议栈解析其sk_buff中指向的各个头,注意这个协议栈是所有网卡共用的
    • 协议栈与NIC驱动的数据交互是怎样的
      • 网卡每来一帧数据NIC都会将它组织成sk_buff(其中有很多指针,指向数据包中的各个层的头部),发送给协议栈,协议栈就解析其各个头

4.标准接口层Posix API

  • 标准接口层调用各种网络系统调用

5. 应用层

应用层就接收到了…

上述过程发生的拷贝

  1. 网卡数据拷贝到NIC,组织出sk_buff

  2. APP调用recv..将数据从内核态拷贝到用户态

  3. 上述操作需要CPU的参与

四、DPDK介绍

基于上述接收网络数据流程dpdk做的事

  • 把网卡通过一种映射的方式,把网卡接收数据的存储空间映射到用户态的内存空间中,

    这其中没有拷贝,是通过DMA的方式,直接网络适配器与硬盘驱动器与内存交互

  • dpdk主要做的事:把网卡的数据快速转移到用户态内存里

dpdk如何组织映射的数据

Huge Page

  • 正常的内存操作,一个页4k,假设一秒钟来了1G的数据,那么4k的页划分的包就为256x1024,太多了,于是dpdk采用巨页

dpdk优化了什么

threadCPU的亲缘性

  • 某一线程只在同一个CPU上运行

KNI机制

dpdk只想处理一种协议,其他协议还是通过内核协议栈来处理

  • dpdk提供了一种方式,将不需要的数据写入到内核协议栈,内核网络接口(Kernel Network Interface<kni>)

DPDK的技术边界

dpdk处理数据时是跨过了NIC这一层,在NIC接收数据前就截获了数据,与NIC平级,改变了数据流程

DPDK能做什么

  1. 路由器、SDN网络定制开发
  2. 网络协议栈
  3. 防火墙,防ddos攻击
    1. 接收数据,检测异常数据
  4. VPN
    1. 直接往原始数据中加入vxline或加上隧道技术再从网卡中发送出去

五、DPDK该怎么学

环境搭建完后该做的事

  • coding,代码可控
    • 实现一个协议栈(eth,ip,arp,icmp,tcp,udp)
    • posix api, epoll的实现
  • 协议栈是与dpdk相生相辅
  • 行业的应用
    • 三层网络层的vpp
    • 二层传输层考虑ovs
    • 负载均衡dpvs
    • 发包工具pktgen
  • 1-2款上线的产品。。。

六、coding

rte_eal_init(argc, argv)初始化dpdk应用

rte_pktmbuf_pool_create创建

rte_pktmbuf_pool_create(
	const char * name,
    unsigned int n,  // 初始化mbufpoll池能放多少个mbuf
    unsigned int cache_size,  // 0
    uint16_t priv_size,  // 0
    unit16_t data_room_size,
    int socket_id  // 设置为一个全局的一个变量per_lcore_socket_id
);
// 返回一个rte_mempoll结构体
  • 名字中的mbuf就是内核中的sk_buf
  • namePacket Buffer 池的名称,可以是任何字符串,建议使用有意义的名称。
  • nPacket Buffer 池中 Packet Buffer 的数量,建议设置为大于等于 1024
  • cache_sizePacket Buffer 池中的本地缓存大小,可以根据使用场景进行调整,建议设置为 Packet Buffer 数量的1/8左右。
  • priv_sizePacket Buffer 中每个 Packet Buffer 的私有数据大小,如果不需要私有数据,则可以设置为 0
  • data_room_sizePacket Buffer 中数据区域的大小,即可以存储数据包的空间大小,建议设置为 2048 或更大。
  • socket_id:用于分配内存的 NUMA 节点编号,建议设置为套接字绑定的CPU所在的NUMA节点编号。

对网口的配置

TCP/IP网络中,当一个网络设备接收到来自其他设备的数据包时,就会触发RX操作,将数据包解析并交给上层协议或应用程序

tx与rx是什么分别用在什么地方

txqueue主要用于管理应用程序待发送的数据包,当应用程序需要向网络中发送数据时,首先将其封装成一个数据包,并添加到txqueue中。

rxqueue主要用于管理已经从网络中接收到的数据包,当网络中有数据包到达时,DPDK会将其添加到rxqueue中,应用程序可以从rxqueue中取出数据包并进行进一步的处理。

	// setup
	uint16_t nb_rx_queues = 1;
	uint16_t nb_tx_queues = 0;
	const struct rte_eth_conf port_conf_default = {
		.rxmode = {.max_rx_pkt_len = RTE_ETHER_MAX_LEN }
	};
	
	rte_eth_dev_configure(gDpdkPortId, 
                          nb_rx_queues, 
                          nb_tx_queues, 
                          &port_conf_default); 

	// 设置第gDpdkPortId个绑定网口的信息,使用了索引为0对应的rx队列,设置了rx队列的大小为128,使用mbuf_pool来存储接收队列缓存
	rte_eth_rx_queue_setup(gDpdkPortId,  // 设置第gDpdkPortId个绑定网口的信息
                           0,   		 // 使用了索引为0对应的rx队列
                           128,			 // 设置了rx队列的大小为128
                           rte_eth_dev_socket_id(gDpdkPortId), 
                           NULL, 
                           mbuf_pool);	 // 使用mbuf_pool来存储接收队列缓存
	// 
	rte_eth_dev_start(gDpdkPortId);

	// disable
	//rte_eth_promiscuous_enable(gDpdkPortId); //

  • rte_eth_dev_configureAPI介绍

    ret_eth_dev_configure(
    	unit16_t port_id,  //网口 nic 的id是什么
        unit16_t nb_rx_q,  // rx队列 ,对应索引  0表示使用第一个
        unit16_t nb_tx_q,  
        const struct rte_eth_conf* dev_conf  // 配置信息  每个包的长度
    );
    
    • port_id:以太网设备的端口 ID。
    • nb_rx_queue:用于接收数据包的 RX 队列数量。
    • nb_tx_queue:用于发送数据包的 TX 队列数量。
    • eth_conf:一个结构体,包含了以太网设备的配置信息,如 CRC 校验、硬件 RSS 散列、速率控制,以及杂项配置等。
  • rte_eth_rx_queue_setup API介绍

    int rte_eth_rx_queue_setup(
        uint16_t port_id,      // 要绑定的网口索引号 0代表使用第一个网口
        uint16_t rx_queue_id,  // 要绑定的队列的索引,0代表绑定第一个rx队列
    	uint16_t nb_rx_desc,   // 指定队列可以装多少mbuf
        unsigned int socket_id,
    	const struct rte_eth_rxconf *rx_conf,
    	struct rte_mempool *mb_pool
    );
    
    • port_id:以太网设备的端口 ID。
    • rx_queue_id:将要创建的接收队列的队列号。
    • nb_rx_desc:用于网卡接收队列的缓存区描述符数量,可以简单理解为接收队列的缓存容量。(是网卡上面的rx_queue_id对应id的接收队列的大小,前面mbuf_pool内存池的大小就是用来接收这个队列中的节点,所以这个内存池的大小肯定要比rx队列大小大)
    • socket_id:用于分配和管理内存资源的 NUMA 节点 ID,一般使用 rte_socket_id() 函数获取。
    • rx_conf:用于指定接收队列的配置信息,如 RSS 散列、哈希过滤器和 Ptype 解析等特性。如果不需要使用这些特性,可以将该参数设置为 NULL
    • mb_pool:用于存储接收队列缓存的内存池指针。

接受数据

    while(1){
        //..后面的代码都在这个里面
    }

使用API接受数据

		struct rte_mbuf *mbufs[MBUF_SIZE];  // 32
		unsigned num_recvd = rte_eth_rx_burst(
            gDpdkPortId,   // 绑定的网口
            0,             // rx队列索引
            mbufs, 
            MBUF_SIZE  // 设置的32
        );
		if (num_recvd > MBUF_SIZE) {
			rte_exit(EXIT_FAILURE, "rte_eth_rx_burst Error\n");
		}
  • rte_eth_rx_burst

    uint16_t rte_eth_rx_burst(uint16_t port_id, 
                              uint16_t queue_id,
                              struct rte_mbuf **rx_pkts,  // 传出参数
                              const uint16_t nb_pkts
                           	  );
    // 不需要考虑释放  在内存池中直接将对应id取出来直接用
    
    • port_id:以太网设备的端口 ID
    • queue_id:用于接收数据包的 RX 队列 ID
    • rx_pkts:指向 rte_mbuf 结构体指针的数组,用于存储接收到的数据包。
    • nb_pkts:要读取的最大数据包数量。

循环遍历解析所有接受到的包

unsigned i = 0;
for (i = 0;i < num_recvd;i ++) {
    // 宏函数
    struct rte_ether_hdr *ehdr = rte_pktmbuf_mtod(
        mbufs[i], 
        struct rte_ether_hdr *
    );
    if (ehdr->ether_type != rte_cpu_to_be_16(RTE_ETHER_TYPE_IPV4)) {
        continue;
    }

    struct rte_ipv4_hdr *iphdr = rte_pktmbuf_mtod_offset(
        mbufs[i], 
        struct rte_ipv4_hdr *, 
        sizeof(struct rte_ether_hdr)
    );

    if (iphdr->next_proto_id == IPPROTO_UDP) {

        struct rte_udp_hdr* udphdr = (struct rte_udp_hdr*)(iphdr + 1);  // 加上IP头得到udp头
        uint16_t length = udphdr->dgram_len;
        *((char*) udphdr + length - 1) = '\0';
        printf("udp: %s\n",  (char*)(udphdr+1));
    }
}
  • rte_pktmbuf_mtod 是一个宏,而不是一个函数。在 DPDKrte_mbuf.h 文件中,可以看到 rte_pktmbuf_mtod 的定义如下:

    #define rte_pktmbuf_mtod(m, t)  ((t)((char *)((m)->buf_addr) + (m)->data_off))
    

    这个宏的实现使用了强制类型转换,其目的是将缓冲区中数据的地址转换为用户指定的数据类型 t 的指针,从而方便用户访问和处理接收到的数据包。需要注意的是,在使用 rte_pktmbuf_mtod 宏时,应当确保传入的参数合法,并且传入的数据类型和数据包的格式相符,否则可能会导致程序错误。

设置arp静态映射

arp静态映射 就可以用网络调试工具调试了

注意设置的ip地址是要与本机网卡ip地址是同一个网段

arp -s 10.17.31.80 00-0C-29-AF-77-5C

arp -d 10.17.31.80

# The ARP entry addition failed: Access is denied

netsh i i show in  # 查看网络接口的索引号

netsh -c i i add neighbors 18 10.17.31.80 00-0C-29-AF-77-5C

netsh -c "i i" delete neighbors 1

关于dpdk无法接收来自主机的数据解决

  • 保证绑定网卡前主机可以ping通虚拟机的eth0的桥接网卡

  • eth0ip要在主机上静态绑定eth0mac请添加图片描述

重启虚拟机后需要做的事

  • 查看主机ip是否改变(连接不同的网络都会改变)
    • 如果改变了就重新设置/etc/network/interfaces文件,设置eth的静态ip,需要与主机ip为同一网段即可

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

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

相关文章

人人看得懂的AI教程

人人看得懂的AI教程&#xff0c;从0开始入门AI教程&#xff0c;一步一步AI&#xff0c;人工智能学习笔记 现在写书真的方便&#xff0c;闲来无事写了本从0开始学AI的书籍&#xff0c;哈哈 一、基础知识 1.1 人工智能概览 1.2 机器学习 1.3 深度学习 1.4 数据科学 二、编程知…

chatGPT中文版入口-chatGPT不可以用的地区

ChatGPT老出现不可用 如果您在使用ChatGPT时发现它经常不可用&#xff0c;可能是由于以下原因&#xff1a; OpenAI API的服务不稳定。由于技术问题、网络问题或维护&#xff08;如软件更新&#xff09;等原因导致OpenAI API服务不稳定&#xff0c;会导致ChatGPT无法使用。 接…

2345看图王阻止文件删除和U盘弹出 - 解决方案

2345看图王阻止文件删除和U盘弹出 - 解决方案前言2345看图王解决方案临时方案永久方案前言 用户在使用2345看图王查看图片后&#xff0c;可能会出现图片文件/文件夹无法删除或U盘无法弹出等问题&#xff0c;这是因为2345看图王的辅助模块正在占用图片文件&#xff0c;因此无法…

VS2022下载安装与基本使用(写C语言)

最近遇到一种问题&#xff0c;就是想要写一写C语言的代码&#xff0c;但是网页编辑器功能不全&#xff0c;GCC需要安装Liunx系统&#xff0c;VS又体量太大过于复杂&#xff0c;用keil又需要连接硬件&#xff0c;所以比较纠结。 工作中通常使用的是Keil&#xff0c;但是如果有时…

Nginx实现会话保持,集群模式下session域共享

前言 生产环境下&#xff0c;多数系统为了应对线上多种复杂情况而进行了集群架构的部署&#xff0c;保证系统的高性能、价格有效性、可伸缩性、高可用性等。通常将生产环境下的域名指向Nginx服务&#xff0c;通过它做HTTP协议的Web负载均衡。 session是什么 在计算机中&…

8万字智慧旅游景区信息化建设方案word

本资料来源公开网络&#xff0c;仅供个人学习&#xff0c;请勿商用&#xff0c;如有侵权请联系删除。 1.1. 整体建设框架 XXXXXX智慧景区旅游建设对于全面整合景区旅游资源&#xff0c;提升景区旅游产业发展能级&#xff0c;进一步增强景区旅游业的核心竞争力具有十分重要的支…

【Python搞笑游戏】因蔡徐坤打篮球动作超火,被某程序员写成了一款游戏,画面美到不敢看,成功学到了精髓~(附源码免费)

导语 之前网络最火的梗&#xff0c;非“C徐坤打篮球”莫属。个人感觉&#xff0c;只有多年前的“春哥纯爷们”堪与匹敌&#xff01; 虽然说C徐坤打篮球是一个老梗了&#xff0c;但是确实非常搞笑&#xff0c;今天就跟着小编一起来回忆一下吧&#xff01; “我是练习两年半的…

SQL SERVER调Web Service时候权限错误的解决

日期 2023/4/15 18:00:00 日志 作业历史记录 (AIPACS) 步骤 ID 1 服务器 GOOGLE 作业名称 AIPACS 步骤名称 RUNWS 持续时间 00:00:00 SQL 严重性 16 SQL 消息 ID 15281 已通过电子邮件通知的操作员 已通过…

江苏三年制专转本法学类考纲配套课程网课题库

江苏三年制专转本法学类考纲配套课程网课题库1、江苏专转本的考试科目都有哪些&#xff1f; 2022年开始江苏专转本成绩主要由语文/数学英语/日语专业课三科的成绩构成&#xff0c;满分500分。分别给大家解释一下 语文/数学&#xff1a;满分150分&#xff08;文科考语文&#xf…

C++ -3- 类和对象 (中) | 拷贝构造函数 赋值运算符重载

文章目录 4.拷贝构造函数什么是拷贝构造函数&#xff1f;应用——示例&#xff1a;日期计算器什么情况下需要自己实现拷贝构造函数&#xff1f; 5.赋值运算符重载运算符重载&#xff08;重要&#xff09;赋值运算符重载 拷贝构造函数和赋值重载函数 4.拷贝构造函数 什么是拷贝…

Vue2 API-源码解析

目录 Vue.extend(option) delimiters functional Vue.component(id, Function | Object) Vue.directive( id, [definition] ) Vue.filter( id, function) Vue.nextTick() Vue.set() Vue.delete(target, index/key) Vue.compile(template) Vue.observable(object) …

一文讲解系统性能分析之|iowait是什么?

我们对系统性能进行优化时&#xff0c;一般会使用 top 命令来查看系统负载和系统中各个进程的运行情况&#xff0c;从而找出影响系统性能的因素。如下图所示&#xff1a; top top 命令会输出很多系统相关的信息&#xff0c;如&#xff1a;系统负载、系统中的进程数、CPU使用率…

四十六、docker-compose部署

一个项目肯定包含多个容器&#xff0c;每个容器都手动单独部署肯定费时费力。docker-compose可以通过脚本来批量构建镜像和启动容器&#xff0c;快速的部署项目。 使用docker-compose部署主要是编写docker-compose.yml脚本。 一、项目结构 不论是Dockerfile还是docker-compo…

实验室汇报汇报汇报

1、kafka是什么 Producer&#xff1a;即生产者&#xff0c;消息的产生者&#xff0c;是消息的入口&#xff1b;Consumer&#xff1a;消费者&#xff0c;即消息的消费方&#xff0c;是消息的出口&#xff1b;Broker&#xff1a;中间代理&#xff0c;即一个broker就是一个server。…

接口优化的常见方案实战总结

一、背景 针对老项目&#xff0c;去年做了许多降本增效的事情&#xff0c;其中发现最多的就是接口耗时过长的问题&#xff0c;就集中搞了一次接口性能优化。本文将给小伙伴们分享一下接口优化的通用方案。 &#xfeff; &#xfeff; &#xfeff;&#xfeff; 二、接口优化…

设计模式-结构型模式之装饰模式

3. 装饰模式3.1. 模式动机一般有两种方式可以实现给一个类或对象增加行为&#xff1a;继承机制使用继承机制是给现有类添加功能的一种有效途径&#xff0c;通过继承一个现有类可以使得子类在拥有自身方法的同时还拥有父类的方法。但是这种方法是静态的&#xff0c;用户不能控制…

java基础——迭代器,数据结构,List,Set ,TreeSet集合,Collections工具类

迭代器&#xff0c;数据结构,List,Set ,TreeSet集合,Collections工具类 第一章 Iterator迭代器 1.1 Iterator接口 在程序开发中&#xff0c;经常需要遍历集合中的所有元素。针对这种需求&#xff0c;JDK专门提供了一个接口java.util.Iterator。 想要遍历Collection集合&…

链表基础知识

1.链表必知必会 什么是链表? 链表是一种通过指针串联在一起的线性结构&#xff0c;每一个节点由两部分组成&#xff0c;一个是数据域一个是指针域&#xff08;存放指向下一个节点的指针&#xff09;&#xff0c;最后一个节点的指针域指向null&#xff08;空指针的意思&#…

【好刊推荐】知名出版社影响因子7+被踢出SCI,投稿前如何选期刊?

今年3月Hindawi旗下的19本期刊被SCIE剔除&#xff0c;其中有一本影响因子7&#xff0c;以下从期刊各个指标方面分析一下具体原因&#xff1a; 期刊剔除&#xff1a;影响因子7 期刊简介 期刊名称&#xff1a; OXIDATIVE MEDICINE AND CELLULAR LONGEVITY ISSN / eISSN&#…

数据结构——堆和优先队列

文章目录前言堆堆的引入堆的定义堆的储存结构优先队列优先队列简介优先队列的基础操作入队出队优先队列的实现堆的应用堆排序TOP-K问题什么是TOP-K问题TOP-K问题的排序解法TOP-K问题的堆解法总结前言 堆是一个比较基础&#xff0c;且实现起来难度也不算太大的一个数据结构。而…