javascript实现二叉堆添加元素（上浮），删除元素（下浮），构建二叉堆（最小堆）

添加元素（上浮）操作

// 写的第一版

function upAdjust2(arr) {
      //而是把添加的元素找到合适的位置
      let childIndex = arr.length - 1
      let parentIndex = parseInt((childIndex - 1) / 2)
      let element = arr[childIndex]
      while (childIndex) {
        if(arr[parentIndex] > arr[childIndex]) {
          arr[childIndex] = arr[parentIndex]
          arr[parentIndex] = element
        }else{
          break
        }
        childIndex = parentIndex
        parentIndex = parseInt((childIndex - 1) / 2)
      }
      //console.log(childIndex)
      
    }
    //优化一版，不要随便在循环中使用break, continue这些
    function upAdjust3(arr) {
      let childIndex = arr.length - 1
      let parentIndex = parseInt((childIndex - 1) / 2)
      let element = arr[childIndex]
      while (childIndex && arr[parentIndex] > arr[childIndex]) {
        arr[childIndex] = arr[parentIndex]
        arr[parentIndex] = element
        childIndex = parentIndex
        parentIndex = parseInt((childIndex - 1) / 2)
      }  
    }


//往最小堆添加元素，这时需要把添加的元素进行upAdjust()调整
    function upAdjust1(arr) {
      //获取新添加元素在数组中的下标
      let childIndex = arr.length - 1
      //parent index
      let parentIndex = (childIndex - 1) / 2
      //交换 
      while(childIndex > 0 && arr[parentIndex] > arr[childIndex]) {
         //进行交换,不推荐
         let temp = arr[parentIndex]
         //console.log(temp)
         arr[parentIndex] = arr[childIndex]
         arr[childIndex] = temp
         //对childIndex与parentIndex进行替换
         //这里通过 parentIndex - 1或 parentIndex - 2 ,然后取整 parseInt得到下标
         childIndex = parentIndex
         parentIndex = parseInt((parentIndex - 1) / 2) 
         //console.log(childIndex, parentIndex)
      }
      return arr
    }

   function upAdjust(arr) {
      //获取新添加元素在数组中的下标
      let childIndex = arr.length - 1
      //parent index
      let parentIndex = parseInt((childIndex - 1) / 2)
      //把新元素存起来,下边给它找到合适的位置放进去即可,这样效率比两个两个交换更高，推荐
      let temp = arr[childIndex]
      while(childIndex > 0 && arr[parentIndex] > temp){
        arr[childIndex] = arr[parentIndex]
        childIndex = parentIndex
        parentIndex = parseInt((parentIndex - 1) / 2) 
      }
      arr[childIndex] = temp
      return arr
    }

删除元素（下浮)操作

//arr是原堆，parentIndex是被删除父节点下标,即要进行下沉操作的父节点下标
    function downAdjust(arr, parentIndex) {
      let temp = arr[parentIndex]
      let childIndex = 2 * parentIndex + 1
      while(childIndex < arr.length){
        //找到左右子树较小者的下标,推荐
        // if(childIndex + 1 < arr.length && arr[childIndex + 1] < arr[childIndex]) {
        //   childIndex ++
        // }
        if(childIndex + 1 < arr.length) {
          let minV = Math.min(arr[childIndex], arr[childIndex + 1])
          childIndex = (minV === arr[childIndex] ? childIndex : childIndex + 1)
        }
        
        if(temp <= arr[childIndex]){
            break
        }
        arr[parentIndex] = arr[childIndex]
        parentIndex = childIndex
        childIndex = 2 * parentIndex + 1
      }
      arr[parentIndex] = temp
      return arr
    }

构建二叉堆(无序二叉树构建成最小堆）

//把一个无序的二叉堆构建成有序的最小堆
    //思路是从后一个非叶子节点开始执行downAdjust操作,构造最小堆也可以从第一个非叶子节点执行downAdjust操作
    //但构造最大堆则必须从最后一个非叶子节点开始操作
    function buildHeap(arr) {
      for(let i = parseInt((arr.length - 1) / 2); i >= 0; i--){
          downAdjust(arr, i)
      }
      return arr
    }

测试用例

    //模拟最小堆添加元素0,进行上浮操作
    const binaryHeapUpAdjust = [1,3,2,6,5,7,8,9,10,0]
    //模拟删除最小堆第一个元素，进行下沉操作
    const binaryHeapDownAdjust = [5, 1, 2, 6, 3, 7, 8, 9, 10]
    //模拟删除最小堆第二个元素，进行下沉操作
    const binaryHeapDownAdjust2 = [0, 5, 2, 6, 3 , 7, 8, 9, 10]
    //从一个无序二叉树构建最小堆
    const buildHeapArr = [7, 1, 3, 10, 5, 2, 8, 9, 6]
    
    console.log(upAdjust(binaryHeapUpAdjust))
    console.log(upAdjust1(binaryHeapUpAdjust))
    console.log(downAdjust(binaryHeapDownAdjust2, 1))
    console.log(downAdjust(binaryHeapDownAdjust1, 0))
    console.log(buildHeap(buildHeapArr))

本文由 dealdot ＜dealdot＃163.com＞ 创作, Full Stack Developer @ DeepBlue
本文最后编辑时间为: Jun 10, 2021 at 17:43 pm
转载请注明来源