React的小顶堆排序法

前言

想要了解react源码，还是得要了解一丢丢的算法，周末学习一个堆排序里面的小顶堆。

为什么要了解堆排序，因为react17源码里任务优先级调度，采用的就是小顶堆。

基础知识

假如一个数组[1,2,3,4,5,6,7],生成二叉树的结构是什么样，就是下面的样子,小括号里面是对应数组的索引

一个父节点有两个子节点，左边叫左子节点，右边叫右子节点

其中数字1相当于2，3的父节点，2相当于4，5的父节点，3相当于6，7的父节点

代码安排

假如一个随机的数组arr1 = [3,6,4,9,2,1,7]，里面是数代表着，不同的任务，对应的数字越小，代表优先级最高

数组排列成小顶堆

小顶堆：每一个父节点都比它的两个子节点小，第一个父节点是最小的

• 每次push进去一个元素，和这个元素的索引
• 找出这个子元素的父元素，然后比较大小，递归执行该方法，直到找到最上层第一个元素

排列之后：

排序

排序的过程实际上也是react事件的调度的过程

取出最顶端元素（优先级最高的任务去执行）；最后一位元素，移动到第一位；再重新排序

1.根据父节点的索引0，找出它的两个子节点

2.父节点和左子节点比较

• 左子节点小于父节点，再比较左子节点与右子节点
  • 右子节点小于左子节点，将右子节点与父节点互换，右子节点作为父节点，继续循环比较
  • 右子节点大于左子节点，将左子节点与父节点互换，左子节点作为父节点，继续循环比较
• 左子节点大于父节点，比较右子节点与父节点
  • 右子节点小于父节点，将右子节点与父节点互换，右子节点作为父节点，继续循环比较

var arr1 = [3,6,4,9,2,1,7];
var heap = []  // 存排列好的小顶堆
var stack = [] // 排序好的数组
for(let i=0,len = arr1.length;i<len;i++) {
    const index = heap.length;
    const node =  arr1[i] 
    heap.push(node);
    siftUp(heap, node, index);
}

while(heap.length) {
    const first = heap[0]
    const last = heap.pop()
    stack.push(first)
    if(first !=last) {
        heap[0] = last;
        siftDown(heap, last, 0)
    } else {
        break;
    }
}
    
function siftDown(heap, node, i) {
    let index = i;
    const length = heap.length
    const halfLength = length >>> 1
    while(index < halfLength) {
       // 根据顶层父节点索引，找出它的左右子节点
       const leftIndex = (index + 1) * 2 - 1
       const left = heap[leftIndex]
       const rightIndex = leftIndex + 1
       const right = heap[rightIndex]
       // 左子节点小于父节点
       if (left < node) {
           // 右子节点小于左子节点,两个交换，右子节点作为父节点，继续循环
           if(rightIndex < length && right < left) {
               heap[index] = right
               heap[rightIndex] = node
               index = rightIndex
           } else {
               // 右子节点大于左子节点,两个交换，左子节点作为父节点，继续循环
               heap[index] = left
               heap[leftIndex] = node
               index = leftIndex
           }
       } else if (rightIndex < length && right < node) {
           // 右子节点小于父节点，两个交换，右子节点作为父节点，继续循环
           heap[index] = right
           heap[rightIndex] = node
           index = rightIndex
       } else {
          return 
       }
    }
}
    
function siftUp(heap, node, i) {
    let index = i
    // 找到第一个元素，不再比较
    while(index > 0) {
        // 根据子节点索引，找到父节点
        const parentIndex = (index - 1) >>> 1
        const parent = heap[parentIndex]
        // 父节点大于子节点，父子节点交换位置
        if (parent > node) {
            heap[parentIndex] = node
            heap[index]= parent
            // 指针移动到父节点位置，作为子节点，找它的父节点
            index = parentIndex
        } else {
            return
        }
    }
}
    

总结

堆也是一种数据类型，React的事件调度采用最小堆，非常经典的算法运用。空闲时间还是需要加强算法。

感兴趣的小伙伴可以看看源码react/packages/scheduler/src/SchedulerMinHeap.js

最后祝大家周末愉快，求点赞~