概念入门

完全二叉树

一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树

堆

堆是一棵完全二叉树，其存储结构一般用的是数组

小顶堆

小顶堆就是堆顶的元素是当前子树里最小的一个元素的堆，对任意非叶子节点 有 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2];

操作

构造

构造一棵小顶堆 即在存储数组的末尾添加一个元素 然后判断其能否满足小顶堆的性质，不满足即 把他与父节点交换位置，重复此步骤直到找到正确的位置:

  1. /*
  2. react scheduler React v0.20.1
  3. */
  4. function siftUp(heap,node){
  5.     let nodeIndex = heap.length;
  6.     heap[nodeIndex] = node;
  7.     while(true){
  8.         /*
  9.         * left - 1 是 2i 
  10.         * right - 1 是 2i + 1；
  11.         * 然后再右移相当于除以2向下取整都能得到正确的
  12.         * 父节点位置  至于这里为什么用无符号右移而没有用>> 这点尚未清楚
  13.         */
  14.         let parentNodeIndex = nodeIndex - 1 >>> 1
  15.         let parentNode = heap[parentNodeIndex]
  16.         if( 
  17.             parentNode !== undefined 
  18.                 &&
  19.             parentNode > node
  20.         ){
  21.             heap[parentNodeIndex] = node
  22.             heap[nodeIndex] = parentNode
  23.             nodeIndex = parentNodeIndex
  24.         }else{
  25.             return;
  26.         }
  27.     }
  28. }

更多相关文章

  1. Mysql Cluster7.4.6安装与配置
  2. 4-10（二叉搜索树）
  3. 【DB宝18】在Docker中安装使用MySQL高可用之MGR
  4. 2021-04-10：给定两个可能有环也可能无环的单链表，头节点head1和hea
  5. Elasticsearch 最佳运维实践 - 总结（一）
  6. dom树元素的增删改查
  7. 【微信公众号】【深入解析】DRM和read-mostly locking
  8. 【论文解读】LGN: 基于词典构建的中文NER图神经网络
  9. 日志分析ELK平台部署第一节

随机推荐

  1. Android 5.1系统禁止通知状态栏下拉
  2. Android SDK中国在线更新镜像服务器 解决
  3. App 权限一点知识
  4. Android Map开发基础知识学习笔记(转)
  5. Android AndroidManifest.xml文件的andro
  6. Android 搭建环境配置
  7. Android Pitfall - Fragment.startActivi
  8. 获取Android设备电池电量状态
  9. Android(安卓)四大组件之 Service（二）
  10. android camera(一)：camera模组CMM介绍