在 Scheduler 中，使用最小堆的數據結構在對任務進行排序。
// 兩個任務隊列
var taskQueue: Array<Task> = [];
var timerQueue: Array<Task> = [];push(timerQueue, newTask); // 像數組中推入一個任務
pop(timerQueue); // 從數組中彈出一個任務
timer = peek(timerQueue); // 從數組中獲取第一個任務
我們在學習 Scheduler 中最小堆算法之前，需要先了解什么是 二叉堆。
二叉堆
二叉堆是一種基于完全二叉樹的數據結構，它滿足堆屬性：對于每個節點x，x的父節點的值小于等于x的值（最小堆）或者大于等于x的值（最大堆）。
根據二叉堆的定義我們發現一個名次 完全二叉樹。，完全二叉樹是對二叉樹、完全樹的一種特殊情況。
下面我們來了解什么是二叉樹和完全樹
二叉樹
二叉樹是一種特殊的樹結構，它的每個節點最多有兩個子節點，稱為左子節點和右子節點。例如下圖：
完全樹
所謂完全樹，指的是一棵樹再進行填寫的時候，遵循的是“從左往右，從上往下”
例如下面的這些樹，就都是完全樹：
完全樹中的數值
可以分為兩大類：
- 最大堆：父節點的數值大于或者等于所有的子節點
- 最小堆：剛好相反，父節點的數值小于或者等于所有的子節點
最大堆示例：
最小堆示例：
- 無論是最大堆還是最小堆，第一個節點一定是這個堆中最大的或者最小的
- 每一層不是按照一定順序來排列的，比如下面的例子，6可以在左分支，3可以在右分支
- 每一層的所有元素不一定比下一層（非自己的子節點）大或者小
二叉堆主要有兩種類型：
最小堆：對于每個節點x，x的值小于等于它的左子節點和右子節點的值。
最大堆：對于每個節點x，x的值大于等于它的左子節點和右子節點的值。
堆的實現
二叉堆通常用數組來實現
通過數組，我們可以非常方便的找到一個節點的所有親屬。對于任意節點i，它的左孩子的索引為2i+1，右孩子的索引為2i+2，父節點的索引為(i-1)/2。例如：
- 父節點：Math.floor((i - 1) / 2)
| 子節點索引 | 父節點索引 |
|---|---|
| 1 | 0 |
| 3 | 1 |
| 4 | 1 |
| 5 | 2 |
- 左分支節點：i * 2 + 1
| 父節點索引 | 左分支節點索引 |
|---|---|
| 0 | 1 |
| 1 | 3 |
| 2 | 5 |
- 右分支節點：i * 2 + 2
| 父節點索引 | 右分支節點索引 |
|---|---|
| 0 | 2 |
| 1 | 4 |
| 2 | 6 |
react 中對最小堆的應用
在 react 中，最小堆對應的源碼在 SchedulerMinHeap.js 文件中，總共有 6 個方法，其中向外暴露了 3 個方法
- push：向最小堆推入一個元素
- pop：彈出一個
- peek：取出第一個
沒有暴露的是：
- siftUp：向上調整
- siftDown：向下調整
- compare：這是一個輔助方法，就是兩個元素做比較的
所謂向上調整，就是指將一個元素和它的父節點做比較，如果比父節點小，那么就應該和父節點做交換，交換完了之后繼續和上一層的父節點做比較，依此類推，直到該元素放置到了正確的位置
向下調整，就剛好相反，元素往下走，先和左分支進行比較，如果比左分支小，那就交換。
接下來我們學習 React 最小堆算法源碼的具體實現
peek
取出堆頂的任務，堆頂一定是最小的
這個方法極其的簡單，如下：
peek(timerQueue);
export function peek(heap) {// 返回這個數組的第一個元素return heap.length === 0 ? null : heap[0];
}
push
向最小堆推入一個新任務，因為使用的是數組，所以在推入任務的時候，首先該任務是被推入到數組的最后一項，但是這個時候，涉及到一個調整，我們需要向上調整，把這個任務調整到合適的位置
push(timerQueue, newTask);
export function push(heap, node) {const index = heap.length;// 推入到數組的最后一位heap.push(node);// 向上調整，調整到合適的位置siftUp(heap, node, index);
}
pop
pop 是從任務堆里面彈出第一個任務，也就是意味著該任務已經沒有在隊列里面了
pop(taskQueue);
export function pop(heap) {if (heap.length === 0) {return null;}// 獲取數組的第一個任務（一定是最小的）const first = heap[0];// 拿到數組的最后一個const last = heap.pop();if (last !== first) {// 將最后一個任務放到第一個heap[0] = last;// 接下來向下調整siftDown(heap, last, 0);}return first;
}
具體的調整示意圖如下：
)
和LockSupport.park())
