区块链技术博客
www.b2bchain.cn

优先级队列基础

这篇文章主要介绍了优先级队列基础的讲解,通过具体代码实例进行16910 讲解,并且分析了优先级队列基础的详细步骤与相关技巧,需要的朋友可以参考下https://www.b2bchain.cn/?p=16910

本文实例讲述了2、树莓派设置连接WiFi,开启VNC等等的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7039.html。具体如下:

文章目录

  • 1.预学习 二叉树的顺序存储
    • 存储方式
    • 下标关系
  • 2. 堆 Heap
    • 定义
    • 基本操作
      • 向下取整
      • 建堆

1.预学习 二叉树的顺序存储

存储方式

  • 数组保存二叉树结构,方式为层序遍历放入数组
  • 只适用于完全二叉树,非完全二叉树会造成空间浪费(存储大量的空节点)
  • 这种方法与堆的使用联系在一起

下标关系

  • 双亲下标 -> 孩子下标
    • leftChild = 2 * parent + 1;
    • rightChild = 2 * parent + 2;
  • 孩子下标 -> 双亲下标
    • 不区分左右孩子
    • parent = (child – 1) / 2;

2. 堆 Heap

定义

逻辑上 物理存储
完全二叉树 数组形式
  • 大根堆
    根节点为整个树的最大值,又称作大根堆、最大堆、大堆
  • 小根堆
    根节点为整个树的最小值,别名小根堆、最小堆

堆的作用:快速找到集合中的最值

基本操作

向下取整

##前提条件:## 左右子树必须已经是一个堆

名称 意义
array 存储栈的数组
size 栈存储数据个数
cur 调整位置的下标
left cur的左孩子
right cur的右孩子
min left与right的最小值

优先级队列基础

时间复杂度:O(log(n))

public void adjustDown ( int parent, int len ) {         int child = parent*2+1;         while ( child < len ) {             if ( child+1 < len && this.elem[child] < this.elem[child+1] ) {                 child++;             }             if ( this.elem[child] > this.elem[parent] ){                 int tmp = this.elem[child];                 this.elem[child] = this.elem[parent];                 this.elem[parent] = tmp;                 parent = child;                 child = child*2+1;             }else {                 break;             }         }     } 

建堆

本文转自互联网,侵权联系删除优先级队列基础

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 优先级队列基础
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们