结合React源码，五分钟带你掌握优先队列

最近写一个需求用到了优先队列和二叉堆的相关知识，借此机会梳理了一些二叉堆的相关知识分享给大家。

创新互联主要从事网站设计制作、成都网站建设、网页设计、企业做网站、公司建网站等业务。立足成都服务邹城,10余年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:028-86922220

什么是优先队列

  • 优先队列是数据结构中的基础概念，与队列先进先出(FIFO)的出队顺序不同的是 ，它的出队顺序与元素的优先级相关。
  • 例如 React 的时间分片(React Fiber)，它将渲染任务分了优先级，出队的顺序与任务的“重要程度”存在关系，那么满足这种情况的数据结构就是 优先队列 。

优先队列的操作

  • 插入：在优先队列中插入元素，并使队列“有序”
  • 删除最大/最小值：删除并返回最大/最小的元素，并使队列“有序”
  • 查找最大/最小关键字：查找最大/最小的值

优先队列的实现比较

优先队列可以由以上多种方式实现，而优先队列的主要操作是插入和删除，其中二叉搜索树和二叉堆这两项操作的时间复杂度均为 logn ,但二叉树在多次删除之后容易导致树的倾斜，同时查找成本也高于二叉堆，所以最终二叉堆是比较符合实现优先队列的数据结构。

二叉堆

在二叉堆中数组中，要保证每个元素都小于(大于)或等于另外两个特定位置的元素。例如下图的树中，父节点总是小于或等于子节点。

对于二叉堆有如下性质：

  • 节点 k 的父节点下标为 k / 2(向下取整)
  • 已某节点为根节点的子树，该节点是这颗树的极值

二叉堆的操作

插入

二叉堆的插入非常简单，只需要在二叉堆的最后添加要插入的内容，并将其“上浮”到正确位置。

尝试在上面的二叉堆中插入新元素 9，过程如下：

在尾部插入元素 9，与父节点进行对比，有序性被破坏，与父元素替换位置。

替换成功后，继续上一轮操作，与父节点进行对比，仍然无法满足有序性，继续调换位置。

再次替换后符合。

程序框架

 
 
 
 
    
  
  
  
  
  1. function push { 
    2. 
  
  
  
  
  2.   * 在堆尾部添加元素 
    3. 
  
  
  
  
  3.   * 执行上浮循环 
    4. 
  
  
  
  
  4.     * 与父元素对比大小，将较大的放在父节点位置 
    5. 
  
  
  
  
  5.  
    6. 
  
  
  
  
  6.   return minItem 
    7. 
  
  
  
  
  7. } 
    8.

实现

 
 
 
 
    
  
  
  
  
  1. function push(heap: Heap, node: Node): void { 
    2. 
  
  
  
  
  2.   const index = heap.length; 
    3. 
  
  
  
  
  3.   heap.push(node); // 在堆尾部添加元素 
    4. 
  
  
  
  
  4.   siftUp(heap, node, index); // 进行上浮操作 
    5. 
  
  
  
  
  5. } 
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7. function siftUp(heap, node, i) { 
    8. 
  
  
  
  
  8.   let index = i; 
    9. 
  
  
  
  
  9.   while (true) { 
    10. 
  
  
  
  
  10.     const parentIndex = (index - 1) >>> 1; // 父节点位置： parentIndex = childIndex / 2 
    11. 
  
  
  
  
  11.     const parent = heap[parentIndex]; 
    12. 
  
  
  
  
  12.     if (parent !== undefined && compare(parent, node) > 0) { 
    13. 
  
  
  
  
  13.       // The parent is larger. Swap positions. 
    14. 
  
  
  
  
  14.       heap[parentIndex] = node; 
    15. 
  
  
  
  
  15.       heap[index] = parent; 
    16. 
  
  
  
  
  16.       index = parentIndex; 
    17. 
  
  
  
  
  17.     } else { 
    18. 
  
  
  
  
  18.       // The parent is smaller. Exit. 
    19. 
  
  
  
  
  19.       return; 
    20. 
  
  
  
  
  20.     } 
    21. 
  
  
  
  
  21.   } 
    22. 
  
  
  
  
  22. } 
    23.

删除

取出根节点的值对比插入稍微复杂一点，归纳起来可以分为三步：

  • 取出根节点的值
  • 将最后一个元素与根节点进行替换，并删除最后一个元素
  • 下沉

取出根节点。

将最后一个元素与根节点调换，并删除。对比发现有序性被破坏，进行对调。

完成删除。

程序框架

 
 
 
 
    
  
  
  
  
  1. function pop { 
    2. 
  
  
  
  
  2.   * 设定 minItem 保存根节点 
    3. 
  
  
  
  
  3.   * 取出最后一个节点与根节点替换，并删除最后一个节点 
    4. 
  
  
  
  
  4.   * 执行下沉循环 
    5. 
  
  
  
  
  5.     * 将根元素与左右子节点对比,挑选较小的与父节点替换位置 
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7.   return minItem 
    8. 
  
  
  
  
  8. } 
    9.

实现

 
 
 
 
    
  
  
  
  
  1. export function pop(heap: Heap): Node | null { 
    2. 
  
  
  
  
  2.   const first = heap[0]; // 取出根节点 
    3. 
  
  
  
  
  3.   if (first !== undefined) { 
    4. 
  
  
  
  
  4.     const last = heap.pop(); // 取出最后一位元素，并删除 
    5. 
  
  
  
  
  5.     if (last !== first) { 
    6. 
  
  
  
  
  6.       heap[0] = last; // 与根节点对调 
    7. 
  
  
  
  
  7.       siftDown(heap, last, 0); // 下沉 
    8. 
  
  
  
  
  8.     } 
    9. 
  
  
  
  
  9.     return first; 
    10. 
  
  
  
  
  10.   } else { 
    11. 
  
  
  
  
  11.     return null; 
    12. 
  
  
  
  
  12.   } 
    13. 
  
  
  
  
  13. } 
    14. 
  
  
  
  
  14.  
    15. 
  
  
  
  
  15. function siftDown(heap, node, i) { 
    16. 
  
  
  
  
  16.   let index = i; 
    17. 
  
  
  
  
  17.   const length = heap.length; 
    18. 
  
  
  
  
  18.   while (index < length) { 
    19. 
  
  
  
  
  19.     const leftIndex = (index + 1) * 2 - 1; 
    20. 
  
  
  
  
  20.     const left = heap[leftIndex]; 
    21. 
  
  
  
  
  21.     const rightIndex = leftIndex + 1; 
    22. 
  
  
  
  
  22.     const right = heap[rightIndex]; 
    23. 
  
  
  
  
  23.  
    24. 
  
  
  
  
  24.     // If the left or right node is smaller, swap with the smaller of those. 
    25. 
  
  
  
  
  25.     // 寻找左右儿子较小的那一个替换 
    26. 
  
  
  
  
  26.     if (left !== undefined && compare(left, node) < 0) { //左子节点小于根节点 
    27. 
  
  
  
  
  27.       if (right !== undefined && compare(right, left) < 0) { 
    28. 
  
  
  
  
  28.         heap[index] = right; 
    29. 
  
  
  
  
  29.         heap[rightIndex] = node; 
    30. 
  
  
  
  
  30.         index = rightIndex; 
    31. 
  
  
  
  
  31.       } else { 
    32. 
  
  
  
  
  32.         heap[index] = left; 
    33. 
  
  
  
  
  33.         heap[leftIndex] = node; 
    34. 
  
  
  
  
  34.         index = leftIndex; 
    35. 
  
  
  
  
  35.       } 
    36. 
  
  
  
  
  36.     } else if (right !== undefined && compare(right, node) < 0) { // 左子节点大于根节点，右子节点小于根节点 
    37. 
  
  
  
  
  37.       heap[index] = right; 
    38. 
  
  
  
  
  38.       heap[rightIndex] = node; 
    39. 
  
  
  
  
  39.       index = rightIndex; 
    40. 
  
  
  
  
  40.     } else { 
    41. 
  
  
  
  
  41.       // Neither child is smaller. Exit. 
    42. 
  
  
  
  
  42.       return; 
    43. 
  
  
  
  
  43.     } 
    44. 
  
  
  
  
  44.   } 
    45. 
  
  
  
  
  45. } 
    46.

以下是 react 源码中 scheduler/src/SchedulerMinHeap.js 关于最小堆的完整实现：

 
 
 
 
    
  
  
  
  
  1. /** 
    2. 
  
  
  
  
  2.  * Copyright (c) Facebook, Inc. and its affiliates. 
    3. 
  
  
  
  
  3.  * 
    4. 
  
  
  
  
  4.  * This source code is licensed under the MIT license found in the 
    5. 
  
  
  
  
  5.  * LICENSE file in the root directory of this source tree. 
    6. 
  
  
  
  
  6.  * 
    7. 
  
  
  
  
  7.  * @flow strict 
    8. 
  
  
  
  
  8.  */ 
    9. 
  
  
  
  
  9.  
    10. 
  
  
  
  
  10. // 定义最小堆极其元素，其中 sortIndex 为最小堆对比的 key，若 sortIndex 相同，则对比 id 
    11. 
  
  
  
  
  11. type Heap = Array; 
    12. 
  
  
  
  
  12. type Node = {| 
    13. 
  
  
  
  
  13.   id: number, 
    14. 
  
  
  
  
  14.   sortIndex: number, 
    15. 
  
  
  
  
  15. |}; 
    16. 
  
  
  
  
  16.  
    17. 
  
  
  
  
  17. // 入队操作，在入队完成之后进行“上浮” 
    18. 
  
  
  
  
  18. export function push(heap: Heap, node: Node): void { 
    19. 
  
  
  
  
  19.   const index = heap.length; 
    20. 
  
  
  
  
  20.   heap.push(node); 
    21. 
  
  
  
  
  21.   siftUp(heap, node, index); 
    22. 
  
  
  
  
  22. } 
    23. 
  
  
  
  
  23.  
    24. 
  
  
  
  
  24. // 查找最大值 
    25. 
  
  
  
  
  25. export function peek(heap: Heap): Node | null { 
    26. 
  
  
  
  
  26.   const first = heap[0]; 
    27. 
  
  
  
  
  27.   return first === undefined ? null : first; 
    28. 
  
  
  
  
  28. } 
    29. 
  
  
  
  
  29.  
    30. 
  
  
  
  
  30. // 删除并返回最大值 
    31. 
  
  
  
  
  31. export function pop(heap: Heap): Node | null { 
    32. 
  
  
  
  
  32.   const first = heap[0]; // 取出根节点（哨兵） 
    33. 
  
  
  
  
  33.   if (first !== undefined) { 
    34. 
  
  
  
  
  34.     const last = heap.pop(); // 取出最后一位元素，并删除 
    35. 
  
  
  
  
  35.     if (last !== first) { // 头尾并没有对撞 
    36. 
  
  
  
  
  36.       heap[0] = last; // 与根节点对调 
    37. 
  
  
  
  
  37.       siftDown(heap, last, 0); // 下沉 
    38. 
  
  
  
  
  38.     } 
    39. 
  
  
  
  
  39.     return first; 
    40. 
  
  
  
  
  40.   } else { 
    41. 
  
  
  
  
  41.     return null; 
    42. 
  
  
  
  
  42.   } 
    43. 
  
  
  
  
  43. } 
    44. 
  
  
  
  
  44.  
    45. 
  
  
  
  
  45. // 上浮，调整树结构 
    46. 
  
  
  
  
  46. function siftUp(heap, node, i) { 
    47. 
  
  
  
  
  47.   let index = i; 
    48. 
  
  
  
  
  48.   while (true) { 
    49. 
  
  
  
  
  49.     const parentIndex = (index - 1) >>> 1; // 父节点位置： parentIndex = childIndex / 2，此处使用位操作，右移一位 
    50. 
  
  
  
  
  50.     const parent = heap[parentIndex]; 
    51. 
  
  
  
  
  51.     if (parent !== undefined && compare(parent, node) > 0) { // 对比父节点和子元素的大小 
    52. 
  
  
  
  
  52.       // The parent is larger. Swap positions. 
    53. 
  
  
  
  
  53.       heap[parentIndex] = node; // 若父节点较大，则更换位置 
    54. 
  
  
  
  
  54.       heap[index] = parent; 
    55. 
  
  
  
  
  55.       index = parentIndex; 
    56. 
  
  
  
  
  56.     } else { 
    57. 
  
  
  
  
  57.       // The parent is smaller. Exit. 
    58. 
  
  
  
  
  58.       return; 
    59. 
  
  
  
  
  59.     } 
    60. 
  
  
  
  
  60.   } 
    61. 
  
  
  
  
  61. } 
    62. 
  
  
  
  
  62.  
    63. 
  
  
  
  
  63. // 下沉，调整树结构 
    64. 
  
  
  
  
  64. function siftDown(heap, node, i) { 
    65. 
  
  
  
  
  65.   let index = i; 
    66. 
  
  
  
  
  66.   const length = heap.length; 
    67. 
  
  
  
  
  67.   while (index < length) { 
    68. 
  
  
  
  
  68.     const leftIndex = (index + 1) * 2 - 1; 
    69. 
  
  
  
  
  69.     const left = heap[leftIndex]; 
    70. 
  
  
  
  
  70.     const rightIndex = leftIndex + 1; 
    71. 
  
  
  
  
  71.     const right = heap[rightIndex]; 
    72. 
  
  
  
  
  72.  
    73. 
  
  
  
  
  73.     // If the left or right node is smaller, swap with the smaller of those. 
    74. 
  
  
  
  
  74.     // 寻找左右儿子较小的那一个替换 
    75. 
  
  
  
  
  75.     if (left !== undefined && compare(left, node) < 0) { 
    76. 
  
  
  
  
  76.       if (right !== undefined && compare(right, left) < 0) { // 左子节点小于根节点 
    77. 
  
  
  
  
  77.         heap[index] = right; 
    78. 
  
  
  
  
  78.         heap[rightIndex] = node; 
    79. 
  
  
  
  
  79.         index = rightIndex; 
    80. 
  
  
  
  
  80.       } else { 
    81. 
  
  
  
  
  81.         heap[index] = left; 
    82. 
  
  
  
  
  82.         heap[leftIndex] = node; 
    83. 
  
  
  
  
  83.         index = leftIndex; 
    84. 
  
  
  
  
  84.       } 
    85. 
  
  
  
  
  85.     } else if (right !== undefined && compare(right, node) < 0) { // 左子节点大于根节点，右子节点小于根节点 
    86. 
  
  
  
  
  86.       heap[index] = right; 
    87. 
  
  
  
  
  87.       heap[rightIndex] = node; 
    88. 
  
  
  
  
  88.       index = rightIndex; 
    89. 
  
  
  
  
  89.     } else { 
    90. 
  
  
  
  
  90.       // Neither child is smaller. Exit. 
    91. 
  
  
  
  
  91.       return; 
    92. 
  
  
  
  
  92.     } 
    93. 
  
  
  
  
  93.   } 
    94. 
  
  
  
  
  94. } 
    95. 
  
  
  
  
  95.  
    96. 
  
  
  
  
  96. function compare(a, b) { 
    97. 
  
  
  
  
  97.   // Compare sort index first, then task id. 
    98. 
  
  
  
  
  98.   const diff = a.sortIndex - b.sortIndex; 
    99. 
  
  
  
  
  99.   return diff !== 0 ? diff : a.id - b.id; 
    100. 
  
  
  
  
  100. } 
    101.

堆排序

利用最大/最小堆的特性，我们很容易就能实现对数组的排序，重复执行 pop 就能进行升序排列，如果要降序，使用最大堆即可，该操作时间复杂度为 nlogn 。

多叉堆

为了追求更优的时间复杂度，我们可以将二叉堆改为多叉堆实现，下图为一个三叉堆：

与二叉堆不同的是对于含有 N 个元素的 d 叉堆(通常情况下 d >= 2)，随着 d 的增加，树高 K = logdN 的斜率会下降，然而 d 越大，删除操作的成本会更高。所以子元素不是越多越好，通常情况下三叉堆和四叉堆的应用会比较常见。

在libev中有这么一段注释 https://github.com/enki/libev/blob/master/ev.c#L2227，他提及了四叉树相比二叉堆来说缓存更加友好。 根据benchmark，在 50000+ 个 watchers 的场景下，四叉树会有 5% 的性能优势。

 
 
 
 
    
  
  
  
  
  1. /* 
    2. 
  
  
  
  
  2.  * at the moment we allow libev the luxury of two heaps, 
    3. 
  
  
  
  
  3.  * a small-code-size 2-heap one and a ~1.5kb larger 4-heap 
    4. 
  
  
  
  
  4.  * which is more cache-efficient. 
    5. 
  
  
  
  
  5.  * the difference is about 5% with 50000+ watchers. 
    6. 
  
  
  
  
  6.  */ 
    7.

同样 Go 语言中的定时器的 timersBucket 的数据结构也采用了最小四叉堆。

结语

多叉堆，例如四叉堆更加适合数据量大，对缓存要求友好对场景。二叉堆适用数据量比较小且频繁插入和删除的场景。通常情况下二叉堆可以满足大部分情况下的需求，如果编写底层代码，并且对性能有更高的要求，那么可以考虑多叉堆实现优先队列。

当前题目：结合React源码，五分钟带你掌握优先队列
文章位置：http://www.shufengxianlan.com/qtweb/news2/3552.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

网页设计公司知识

分类信息网站

鸿艺文化传播　　 　郫县网站建设　　 　泸县网站建设　　 　宏昇商务服务　　 　鼎尚理发店　　 　电子商务商城网站　　 　网站定制　　 　成都托管服务器　　 　香港云服务器　　 　网站制作报价　　 　成都品牌官网设计公司　　 　成都展柜设计　　 　软文推广　　 　四川黔盛装饰　　 　注册域名　　 　app开发公司　　 　成都企业网站建设　　 　成都户外广告牌设计　　 　网络整合营销　　 　绵竹网站建设