欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 文旅 > 艺术 > 优先级队列-PriorityQueue

优先级队列-PriorityQueue

2025/7/5 15:21:28 来源:https://blog.csdn.net/qq_39203337/article/details/143769981  浏览:    关键词:优先级队列-PriorityQueue

相关概念介绍:

满二叉树

 国内地定义:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的深度为K,且结点总数是(2^k) -1 ,则它就是满二叉树

国外定义:a binary tree T is full if each node is either a leaf or possesses exactly two childnodes

大意为:如果一棵二叉树的结点要么是叶子结点,要么它有两个子结点,这样的树就是满二叉树

在国外的定义中,该种二叉树也是满二叉树

完全二叉树

        一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。大白话就是:二叉树的数据是从上到下,从左到右组织的

        是一棵完全二叉树。二叉树用数组存储数据时,满足如下特性:

假设i为结点在数组中的下标,则有以下性质

  • 结点 i 的父结点为(i-1)/2
  • 结点 i 的左孩子节点为2 * i+1,右孩子节点为2 * i+2

简介

        无界队列,数据存储于内部数组中,数据采用堆(默认小顶锥)的组织形式

数据进队列操作

插入数据逻辑规则:

1 将数据存入数组最后位置

2 将数组最后元素向上调整,直至满足堆特性

数据出队列

出队列数据逻辑规则

1  将第一个元素和最后一个元素交换位置,删除最后一个元素

2 将第一个元素向下调整,直至满足堆特性

堆的创建

从堆的创建和元素的插入,删除逻辑可知,优先级队列的实现原理。

推荐一篇优先级队列原理讲解较为清晰的博文:

PriorityQueue——优先级队列(堆)-CSDN博客

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词