JSFiddle - React, Tailwind, and code Playground

by Mike Lin

JavaScript

const array = [8, 10, 4342, 2, 34, 18, 11, 77, 16, 66]

class MinBinaryHeap {
  constructor(array) {
    this.heap = [...array]
    this.length = this.heap.length
    
    this.buildHeap()
  }
  buildHeap() {
    for(let i = Math.floor(this.length / 2) - 1; i >= 0; i -= 1) {
      this.bubbleDown(this.heap, i, this.length - 1)
    }
  }
  
  bubbleDown(array, parentIndex, length) {
  	// 可以看出这种向下调整的操作是以父节点找子节点的行为
    let childIndex = parentIndex * 2 + 1
    // parentIndex的值会和子节点、孙子节点等节点进行比较，直到找到属于自己的位置
    let temp = array[parentIndex]
    while (childIndex < length) {
      
      if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
        childIndex += 1
      }
      // 找到了有一个节点比父节点大，此时的位置便是父节点的最终位置
      if (temp <= array[childIndex]) {
        break
      }
      
      array[parentIndex] = array[childIndex]
      // 将替换的节点作为父节点，继续遍历下面的子节点
      parentIndex = childIndex
      childIndex = childIndex * 2 + 1
    }
    array[parentIndex] = temp 
  }
  bubbleUp(array) {
  	// 可以看出这种向上调整的操作是以子节点找父节点的行为
  	let childIndex = array.length - 1
    
    let parentIndex = Math.floor((childIndex - 1) / 2)
    
    let temp = array[childIndex]
    while(childIndex > 0 && array[parentIndex] > temp) {
    	array[childIndex] = array[parentIndex]
      childIndex = parentIndex
      parentIndex = Math.floor((parentIndex - 1) / 2)
    } 
    
    array[childIndex] = temp
  }
  insert(newNode) {
  	// 插入节点操作，放在最后面，然后进行自下而上的操作
    this.heap.push(newNode)
    this.length++
    this.bubbleUp(this.heap)
  }
  print() {
  	return this.heap
  }
  remove() {
  	
  	// 二叉堆的删除操作指的是删除根节点，之后自稳定
    if (this.length === 1) {
    	return this.heap[0]
    }
    const lastEle = this.heap.pop()
    const top = this.heap[0]
    this.heap[0] = lastEle
    this.length--
    this.buildHeap()
    return top
  }
  sort() {
  	const result = []
    let i = this.heap.length
    while (i > 0) {
    	result.push(this.remove())
      i -= 1
    }
    return result
  }
}

const...