Shulou(Shulou.com)06/03 Report--

This article mainly explains "combined with React source code how to quickly grasp the priority queue", the content of the article is simple and clear, easy to learn and understand, the following please follow the editor's ideas slowly in depth, together to study and learn "combined with React source code how to quickly grasp the priority queue" bar!

What is a priority queue?

Priority queue is a basic concept in data structure, which is different from the dequeue order of queue first-in-first-out (FIFO), its dequeue order is related to the priority of elements.

For example, React's time slicing (React Fiber), which prioritizes rendering tasks, and the order of queuing is related to the "importance" of the task, so the data structure that satisfies this situation is the priority queue.

Operation of priority queue

Insert: insert elements into the priority queue and make the queue "orderly"

Delete maximum / minimum: delete and return the maximum / minimum elements and make the queue "ordered"

Find maximum / minimum keywords: find maximum / minimum values

Implementation comparison of priority queues

Priority queues can be implemented in many ways, and the main operations of priority queues are insert and delete, in which the time complexity of binary search tree and binary heap are both logn, but binary tree can easily tilt the tree after many deletions, and the search cost is also higher than binary heap, so in the end, binary heap is more consistent with the data structure of priority queue.

Binary reactor

In an array in a binary heap, make sure that each element is less than (greater than) or equal to the other two elements in a specific location. For example, in the tree shown below, the parent node is always less than or equal to the child node.

For binary heap, it has the following properties:

The parent of node k is subscript k / 2 (rounded down)

A node is a subtree of the root node, and the node is the extreme value of the tree

Operation of binary heap

insert

The insertion of the binary heap is very simple, just add the content to be inserted at the end of the binary heap and "float" it to the correct position.

Try inserting a new element 9 into the binary heap above, as follows:

Insert element 9 at the tail, compare it with the parent node, the ordering is destroyed, and replace the position with the parent element.

After the replacement is successful, continue the previous round of operation, compared with the parent node, still can not meet the order, continue to change positions.

Match after replacement again.

Program framework

Function push {* add an element at the end of the heap * execute a floating loop * compare the size with the parent element, and place the larger one at the parent node position return minItem}

Realize

Function push (heap: Heap, node: Node): void {const index = heap.length; heap.push (node); / / add elements siftUp (heap, node, index) to the tail of the heap; / / float} function siftUp (heap, node, I) {let index = I; while (true) {const parentIndex = (index-1) > > 1; / / parent node location: parentIndex = childIndex / 2 const parent = heap [parentIndex] If (parent! = = undefined & & compare (parent, node) > 0) {/ / The parent is larger. Swap positions. Heap [parentIndex] = node; heap [index] = parent; index = parentIndex;} else {/ / The parent is smaller. Exit. Return;}

Delete

Taking out the value of the root node is a little more complicated than insertion, which can be divided into three steps:

Take out the value of the root node

Replace the last element with the root node and delete the last element

Sinking

Remove the root node.

Swap the last element with the root node and delete it. The comparison found that the order was destroyed and the exchange was carried out.

Finish deleting.

Program framework

Function pop {* set minItem to save the root node * replace the last node with the root node and delete the last node * execute a sinking cycle * compare the root element with the left and right child nodes and select the smaller one to replace the location return minItem with the parent node}

Realize

Export function pop (heap: Heap): Node | null {const first = heap [0]; / take out the root node if (first! = = undefined) {const last = heap.pop (); / / take out the last element and delete if (last! = = first) {heap [0] = last; / / swap siftDown (heap, last, 0) with the root node; / / sink} return first } else {return null;}} function siftDown (heap, node, I) {let index = i; const length = heap.length; while (index)

< length) { const leftIndex = (index + 1) * 2 - 1; const left = heap[leftIndex]; const rightIndex = leftIndex + 1; const right = heap[rightIndex]; // If the left or right node is smaller, swap with the smaller of those. // 寻找左右儿子较小的那一个替换 if (left !== undefined && compare(left, node) < 0) { //左子节点小于根节点 if (right !== undefined && compare(right, left) < 0) { heap[index] = right; heap[rightIndex] = node; index = rightIndex; } else { heap[index] = left; heap[leftIndex] = node; index = leftIndex; } } else if (right !== undefined && compare(right, node) < 0) { // 左子节点大于根节点，右子节点小于根节点 heap[index] = right; heap[rightIndex] = node; index = rightIndex; } else { // Neither child is smaller. Exit. return; } } } 以下是 react 源码中 scheduler/src/SchedulerMinHeap.js 关于最小堆的完整实现： /** * Copyright (c) Facebook, Inc. and its affiliates. * * This source code is licensed under the MIT license found in the * LICENSE file in the root directory of this source tree. * * @flow strict */ // 定义最小堆极其元素，其中 sortIndex 为最小堆对比的 key，若 sortIndex 相同，则对比 id type Heap = Array; type Node = {| id: number, sortIndex: number, |}; // 入队操作，在入队完成之后进行"上浮" export function push(heap: Heap, node: Node): void { const index = heap.length; heap.push(node); siftUp(heap, node, index); } // 查找最大值 export function peek(heap: Heap): Node | null { const first = heap[0]; return first === undefined ? null : first; } // 删除并返回最大值 export function pop(heap: Heap): Node | null { const first = heap[0]; // 取出根节点（哨兵） if (first !== undefined) { const last = heap.pop(); // 取出最后一位元素，并删除 if (last !== first) { // 头尾并没有对撞 heap[0] = last; // 与根节点对调 siftDown(heap, last, 0); // 下沉 } return first; } else { return null; } } // 上浮，调整树结构 function siftUp(heap, node, i) { let index = i; while (true) { const parentIndex = (index - 1) >

> 1; / / parent node location: parentIndex = childIndex / 2, using bit operation here, move one bit to the right: const parent = heap [parentIndex]; if (parent! = = undefined & & compare (parent, node) > 0) {/ / compare the size of the parent node and child elements / / The parent is larger. Swap positions. Heap [parentIndex] = node; / / if the parent node is large, change the location heap [index] = parent; index = parentIndex;} else {/ / The parent is smaller. Exit. Return;}} / / sink, adjust the tree structure function siftDown (heap, node, I) {let index = i; const length = heap.length; while (index)

< length) { const leftIndex = (index + 1) * 2 - 1; const left = heap[leftIndex]; const rightIndex = leftIndex + 1; const right = heap[rightIndex]; // If the left or right node is smaller, swap with the smaller of those. // 寻找左右儿子较小的那一个替换 if (left !== undefined && compare(left, node) < 0) { if (right !== undefined && compare(right, left) < 0) { // 左子节点小于根节点 heap[index] = right; heap[rightIndex] = node; index = rightIndex; } else { heap[index] = left; heap[leftIndex] = node; index = leftIndex; } } else if (right !== undefined && compare(right, node) < 0) { // 左子节点大于根节点，右子节点小于根节点 heap[index] = right; heap[rightIndex] = node; index = rightIndex; } else { // Neither child is smaller. Exit. return; } } } function compare(a, b) { // Compare sort index first, then task id. const diff = a.sortIndex - b.sortIndex; return diff !== 0 ? diff : a.id - b.id; } 堆排序 利用最大/最小堆的特性，我们很容易就能实现对数组的排序，重复执行 pop 就能进行升序排列，如果要降序，使用最大堆即可，该操作时间复杂度为 nlogn 。 多叉堆 为了追求更优的时间复杂度，我们可以将二叉堆改为多叉堆实现，下图为一个三叉堆： 与二叉堆不同的是对于含有 N 个元素的 d 叉堆(通常情况下 d >

= 2), with the increase of d, the slope of tree height K = logdN decreases, but the larger the d, the higher the cost of the delete operation. Therefore, the more child elements, the better. In general, the application of trigeminal heap and quad heap will be more common.

There is a comment https://github.com/enki/libev/blob/master/ev.c#L2227 in libev that mentions that quad trees are more cache-friendly than binary heaps. According to benchmark, a quad tree will have a 5% performance advantage in a scenario of 50000 + watchers.

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

Similarly, the timersBucket data structure of the timer in Go language also uses the minimum quad heap.

Thank you for reading, the above is the content of "how to quickly master priority queue with React source code". After the study of this article, I believe you have a deeper understanding of how to quickly master priority queue with React source code. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.