javascript堆排序

二叉堆

二叉堆是一颗完全二叉树，实际操作中是把二叉堆放到数组中顺序存储的，而不是像二叉树一样链式存储

二叉堆添加元素，上浮操作

function upAdjust1(arr) {
      //找到新添加的元素的父节点在数组中的下标
      let childIndex = arr.length - 1
      let parentIndex = parseInt((childIndex - 1) / 2)
      while(childIndex) {
        if(arr[parentIndex] > arr[childIndex]) {
          let temp = arr[parentIndex]
          arr[parentIndex] = arr[childIndex]
          arr[childIndex] = temp
        }else{
          break
        }
        childIndex = parentIndex
        parentIndex = parseInt((childIndex - 1) / 2)
       //console.log(parentIndex)
      }
    }
    //升级版,不是两两交换
    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)
      }  
    }
    //大招终极
    function upAdjust(arr) {
      //找到位置把要添加的元素放进去
      let childIndex = arr.length - 1
      let parentIndex = parseInt((childIndex - 1) / 2)
      let element = arr[childIndex]
      while (childIndex && arr[parentIndex] > element) {
        arr[childIndex] = arr[parentIndex]
        childIndex = parentIndex
        parentIndex = parseInt((childIndex - 1) / 2)
      }
      arr[childIndex] = element
    }

二叉堆删除堆顶元素，下沉操作

//删除堆顶元素，进行单一节点下调（堆已有序）, 元素交换，自己写的第一版
    function downAdjust2(arr, parentIndex) {
      //把最后一个叶子节点赋值给删除的索引处
      arr[parentIndex] = arr[arr.length - 1]; //数组长度 - 1
      arr.splice(arr.length - 1, 1); 
      while (2 * parentIndex + 2 <= arr.length) {
        let rightChildIndex = 2 * parentIndex + 2;
        if (rightChildIndex >= arr.length) {
          let temp = arr[parentIndex];
          arr[parentIndex] = arr[rightChildIndex - 1];
          arr[rightChildIndex - 1] = temp;
          parentIndex = rightChildIndex - 1;
        } else {
          if (arr[rightChildIndex - 1] > arr[rightChildIndex]) {
            let temp = arr[parentIndex];
            arr[parentIndex] = arr[rightChildIndex];
            arr[rightChildIndex] = temp;
            parentIndex = rightChildIndex;
          } else {
            let temp = arr[parentIndex];
            arr[parentIndex] = arr[rightChildIndex - 1];
            arr[rightChildIndex - 1] = temp;
            parentIndex = rightChildIndex - 1;
          }
        }
      }
    }


//删除堆顶元素，进行单一节点下调（堆已有序），非元素交换, 自己写的第二版
    function downAdjust1(arr, parentIndex) {
      //把最后一个叶子节点赋值给删除的索引处
      let element = arr[arr.length - 1];
      //数组长度 - 1
      arr.splice(arr.length - 1, 1);
      //let len = arr.length;
      let rightChildIndex = 2 * parentIndex + 2;
      while (rightChildIndex <= arr.length) {
        if (rightChildIndex === arr.length) {
          arr[parentIndex] = arr[rightChildIndex - 1];
          parentIndex = rightChildIndex - 1;
        } else {
          if (arr[rightChildIndex - 1] > arr[rightChildIndex]) {
            arr[parentIndex] = arr[rightChildIndex];
            parentIndex = rightChildIndex;
          } else {
            arr[parentIndex] = arr[rightChildIndex - 1];
            parentIndex = rightChildIndex - 1;
          }
        }
        rightChildIndex = 2 * parentIndex + 2;
        //console.log(parentIndex)
      }
      //找到位置了
      arr[parentIndex] = element;
    }

    

构造二叉堆(无序完全二叉树 ---> 二叉堆)

//写的第一版，按正常逻辑，异常麻烦


//只是做节点下沉操作，数组长度不动它,用作构造二叉堆，进行堆排序操作，此时整个二叉堆是无序的
  function downAdjust3(arr, parentIndex) {
    let element = arr[parentIndex];
    let rightChildIndex = 2 * parentIndex + 2;
    while (rightChildIndex <= arr.length) {
      if (rightChildIndex === arr.length) {
        if (element > arr[rightChildIndex - 1]) {
          arr[parentIndex] = arr[rightChildIndex - 1]; 
        }else{
          break
        }
        parentIndex = rightChildIndex - 1;
      } else {
        if (arr[rightChildIndex - 1] > arr[rightChildIndex]) {
          if (element > arr[rightChildIndex]) {
            arr[parentIndex] = arr[rightChildIndex];
          }else{
            break
          }
          parentIndex = rightChildIndex;
        } else {
          if (element > arr[rightChildIndex - 1]) {
            arr[parentIndex] = arr[rightChildIndex - 1];
          }else{
            break
          }
          parentIndex = rightChildIndex - 1;
        }
      }
      rightChildIndex = 2 * parentIndex + 2;
    }
    //找到位置了
    arr[parentIndex] = element;
  }


//只是做节点下沉操作，数组长度不动它, 用作构造二叉堆，进行堆排序操作 第二版
  function downAdjust(arr, parentIndex) {
    let element = arr[parentIndex];
    let childIndex = 2 * parentIndex + 1;
    while (childIndex < arr.length) {
      //这里当 childIndex + 1  = arr.length时，arr[arr.length] == undefined
      let tempIndex
      // if(arr[childIndex + 1]) {
      //   tempIndex = arr[childIndex] < arr[childIndex + 1] ? childIndex : ++childIndex;
      // } else {
      //   tempIndex = childIndex
      // }
      arr[childIndex + 1] ? (tempIndex = arr[childIndex] < arr[childIndex + 1] ? childIndex : ++childIndex) : (tempIndex = childIndex)
      if(element > arr[tempIndex]) {
        arr[parentIndex] = arr[tempIndex];
        parentIndex = tempIndex;
        childIndex = 2 * parentIndex + 1;
      }else{
        break
      }
    }
    //找到位置了
    arr[parentIndex] = element;
  }

//放大招
//最小堆，堆顶删除，重新生成最小堆
function downAdjust(arr, parentIndex) {
    let element = arr[parentIndex];
    let childIndex = 2 * parentIndex + 1;
    while (childIndex < arr.length) {
      //这里当 childIndex + 1  = arr.length时，arr[arr.length] == undefined
      //高级，体现水平
      if((childIndex + 1 < arr.length) && (arr[childIndex] > arr[childIndex + 1])) {
        childIndex ++;
      }
      if(element > arr[childIndex]) {
        arr[parentIndex] = arr[childIndex];
        parentIndex = childIndex;
        childIndex = 2 * parentIndex + 1;
      }else{
        break
      }
    }
    //找到位置了
    arr[parentIndex] = element;
  }

  //最大堆，堆顶删除，重新生成最大堆
  function downAdjustBig(arr, parentIndex) {
    let element = arr[parentIndex];
    let childIndex = 2 * parentIndex + 1;
    while (childIndex < arr.length) {
      //这里当 childIndex + 1  = arr.length时，arr[arr.length] == undefined
      //高级，体现水平
      if((childIndex + 1 < arr.length) && (arr[childIndex] < arr[childIndex + 1])) {
        childIndex ++;
      }
      if(element < arr[childIndex]) {
        arr[parentIndex] = arr[childIndex];
        parentIndex = childIndex;
        childIndex = 2 * parentIndex + 1;
      }else{
        break
      }
    }
    //找到位置了
    arr[parentIndex] = element;
  }

构造堆，自己的思路

自己实现了两版的排序，不过都需要重新new一个数组，空间复杂度一下上去了

//为了从小到大排序，构建一个最大堆, 如果构造最小堆，循环也可以正向来
function buildHeap(arr) {
    for (let i = parseInt((arr.length - 1) / 2); i >= 0; i--) {
      downAdjustBig(arr, i);
    }
    //return arr;
  }

//自己实现的版本一，简洁，因为每一轮都buildHeap，这样做可能效率低下，每一轮其实只需要downAdjust

  function heapSort1(arr){
    let temparr = []
    let len = arr.length
    for(let i = 0; i < len; i++) {
      buildHeap(arr)
      temparr.unshift(arr[0])
      arr.splice(0, 1)
    }
    console.log(temparr)
  }

// 自己实现的版本二，调用时需要传数组长度, 使用downAdjust
function heapSort(arr, len){
    //① 从小到大排序，首先构造成最大堆
    //② 依次删除堆顶，执行downAdjust操作产生新的堆顶
    buildHeap(arr)
    let temparr = []
    //删除堆顶元素
    for(let i = 0; i < len; i++) {
      temparr.unshift(arr[0])
      //单向赋值即可
      arr[0] = arr[len - i - 1]
      //new 新堆，新堆是原堆长度--
      arr.splice(len - i - 1, i + 1)
      downAdjustBig(arr, 0)
    }
    console.log(temparr)
  }

构造堆，不重新new一个数组，降低空间复杂度

思路是执行downAdjust调整时，指定downAdjust的调整范围

//构建一个最大堆,并指定比较范围

  function downAdjustBig1(arr, parentIndex, len) {
    let element = arr[parentIndex];
    let childIndex = 2 * parentIndex + 1;
    while (childIndex < len) {
      //这里当 childIndex + 1  = arr.length时，arr[arr.length] == undefined
      //高级，体现水平
      if((childIndex + 1 < len) && (arr[childIndex] < arr[childIndex + 1])) {
        childIndex ++;
      }
      if(element < arr[childIndex]) {
        arr[parentIndex] = arr[childIndex];
        parentIndex = childIndex;
        childIndex = 2 * parentIndex + 1;
      }else{
        break
      }
    }
    //找到位置了
    arr[parentIndex] = element;
  }


function heapSort(arr){
    buildHeap(arr)
    for(let i = 0; i < arr.length; i++) {
      //上来直接交换元素
      let temp = arr[0]
      arr[0] = arr[arr.length - i - 1]
      arr[arr.length - i - 1] = temp
      //在指定范围内进行调整
      downAdjustBig1(arr, 0, arr.length - i - 1)
    }
  }

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