React prioritization queues React prioritization queues React prioritization queues React prioritization queues React prioritization queues React prioritization queues

preface

Recently, I used the knowledge of priority queue and binary heap to write a requirement. I took this opportunity to sort out some knowledge of binary heap to share with you.

What is a priority queue

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

For example, React Fiber prioritizes rendering tasks, and the queue order is related to the “importance” of the task. Therefore, the data structure that meets this situation is priority queue.

Priority queue operation

  • Insert: Inserts elements into the priority queue and makes the queue “ordered”
  • Remove Max/Min: Remove and return the Max/min element and make the queue “ordered”
  • Find the maximum/minimum keyword: Find the maximum/minimum value

Implementation comparison of priority queues

implementation insert delete Find the maximum/minimum keyword
An array of 1 n n
The list 1 n 1
Orderly array N or logn n 1
Order list n 1 1
Binary search tree logn logn logn
Binary heap logn logn 1

Priority queue can be implemented in the above ways, and the main operations of priority queue are insertion and deletion. The time complexity of binary search tree and binary heap are both Logn, but binary tree is prone to tilt after multiple deletion, and the search cost is also higher than binary heap. Therefore, the binary heap is the data structure suitable for priority queue implementation.

Binary heap

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

The binary heap has the following properties:

  • The subscript of the parent of node K is k / 2 (rounded down)
  • Subtree that has a node as the root node. The node is the extreme value of the tree

Binary heap operation

insert

Binary heap insertion is very simple, just add what you want to insert at the end of the binary heap and “float up” it to the correct location.

Try to insert a new element 9 into the binary heap above as follows:

Insert element 9 at the end, compare with the parent node, the order is broken, and replace with the parent element.

After successful replacement, continue the previous operation and compare with the parent node, but still cannot meet the order, continue to switch positions.

Again, it fits.

Application framework

function push {* Add an element to the end of the heap * perform a floating loop * compare the size of the parent element and place the larger one at the parent nodereturn minItem
}
Copy the code

implementation

function push(heap: Heap, node: Node) :void {
  const index = heap.length;
  heap.push(node); // Add an element to the end of the heap
  siftUp(heap, node, index); // Float up
}

function siftUp(heap, node, i) {
  let index = i;
  while (true) {
    const parentIndex = (index - 1) > > >1; 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; }}}Copy the code

delete

Fetching the value of the root node is a little more complicated than inserting, which can be summarized into three steps:

  1. Fetch the value of the root node
  2. Replace the last element with the root node and remove the last element
  3. sinking

Extract the root node.

Swap the last element with the root node and delete it. The comparison found that the order was destroyed, the swap.

The deletion is complete.

Application framework

Function pop {* Set minItem to save the root node * retrieve the last node to replace with the root node and remove the last node * Perform a sinking loop * Compare the root element with the left and right child nodes and select the smaller one to replace with the parent node return minItem}Copy the code

implementation

export function pop(heap: Heap) :Node | null {
  const first = heap[0]; // Fetch the root node
  if(first ! = =undefined) {
    const last = heap.pop(); // Fetch the last element and delete it
    if(last ! == first) { heap[0] = last; // Switch to the root node
      siftDown(heap, last, 0); / / 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.
    // Find the one whose son is smaller
    if(left ! = =undefined && compare(left, node) < 0) { // The left child is smaller than the root
      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) { // The left child is larger than the root, and the right child is smaller than the root
      heap[index] = right;
      heap[rightIndex] = node;
      index = rightIndex;
    } else {
      // Neither child is smaller. Exit.
      return; }}}Copy the code

The scheduler in which of the following is the react source/SRC/SchedulerMinHeap js about minimum heap full implementation:

/**
 * 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* /

// Define the minimum heap and its elements, where sortIndex is the key of the minimum heap comparison, if sortIndex is the same, then the comparison id
type Heap = Array<Node>;
type Node = {|
  id: number.sortIndex: number|};// Float up after joining the queue
export function push(heap: Heap, node: Node) :void {
  const index = heap.length;
  heap.push(node);
  siftUp(heap, node, index);
}

// Find the maximum value
export function peek(heap: Heap) :Node | null {
  const first = heap[0];
  return first === undefined ? null : first;
}

// Delete and return the maximum value
export function pop(heap: Heap) :Node | null {
  const first = heap[0]; // Remove the root node (sentry)
  if(first ! = =undefined) {
    const last = heap.pop(); // Fetch the last element and delete it
    if(last ! == first) {// There was no head-to-tail collision
      heap[0] = last; // Switch to the root node
      siftDown(heap, last, 0); / / sink
    }
    return first;
  } else {
    return null; }}// Float up and adjust the tree structure
function siftUp(heap, node, i) {
  let index = i;
  while (true) {
    const parentIndex = (index - 1) > > >1; // Parent node position: parentIndex = childIndex / 2, use bitwise operation, move right one bit
    const parent = heap[parentIndex];
    if(parent ! = =undefined && compare(parent, node) > 0) { // Compare the size of the parent 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.
    // Find the one whose son is smaller
    if(left ! = =undefined && compare(left, node) < 0) {
      if(right ! = =undefined && compare(right, left) < 0) { // The left child is smaller than the root
        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) { // The left child is larger than the root, and the right child is smaller than the root
      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;
  returndiff ! = =0 ? diff : a.id - b.id;
}
Copy the code

Heap sort

Using the Max/min heap nature, it is easy to sort an array by repeating pop to sort it in ascending order, or descending order by using the Max heap, which takes nlogn.

Many fork heap

In order to pursue better time complexity, we can change the binary heap to the multi-fork heap implementation, as shown in the following figure:

Different from binary heap, for d-heap containing N elements (d >= 2 in general), the slope of tree height K = logdN will decrease with the increase of D. However, with the increase of D, the cost of deletion will be higher. So not as many children as possible, and in general, the use of tri-heap and quadheap is more common.

There is a comment in libev github.com/enki/libev/… According to Benchmark, quad trees have a 5% performance advantage in a 50,000 + Watchers scenario.

/* * 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 50000+ watchers. */Copy the code

Similarly, the data structure of timersBucket of timer in Go language also adopts the minimum quadheap.

conclusion

Multi-fork heaps, such as quad-heap, are more suitable for scenarios with large data volumes and friendly cache requirements. Binary heap applies to scenarios where the amount of data is small and data is frequently inserted or deleted. In general, binary heap can meet the requirements of most cases, if you write low-level code, and have higher performance requirements, then you can consider multi-fork heap implementation priority queue.

Recommended reading

Write high quality maintainable code: Awesome TypeScript

Writing high quality maintainable code: Component abstraction and granularity

, recruiting

ZooTeam, a young passionate and creative front-end team, belongs to the PRODUCT R&D department of ZooTeam, based in picturesque Hangzhou. The team now has more than 40 front-end partners, with an average age of 27, and nearly 30% of them are full-stack engineers, no problem in the youth storm group. The members consist of “old” soldiers from Alibaba and netease, as well as fresh graduates from Zhejiang University, University of Science and Technology of China, Hangzhou Electric And other universities. In addition to daily business docking, the team also carried out technical exploration and practice in material system, engineering platform, building platform, performance experience, cloud application, data analysis and visualization, promoted and implemented a series of internal technical products, and continued to explore the new boundary of front-end technology system.

If you want to change what’s been bothering you, you want to start bothering you. If you want to change, you’ve been told you need more ideas, but you don’t have a solution. If you want change, you have the power to make it happen, but you don’t need it. If you want to change what you want to accomplish, you need a team to support you, but you don’t have the position to lead people. If you want to change the pace, it will be “5 years and 3 years of experience”; If you want to change the original savvy is good, but there is always a layer of fuzzy window… If you believe in the power of believing, believing that ordinary people can achieve extraordinary things, believing that you can meet a better version of yourself. If you want to be a part of the process of growing a front end team with deep business understanding, sound technology systems, technology value creation, and impact spillover as your business takes off, I think we should talk. Any time, waiting for you to write something and send it to [email protected]