js算法:heap sort 使用堆排序

原

'use strict';

//堆排序

//堆: 完全二叉树
//最大堆定义: 父节点>= 左子节点 父节点 >= 右子节点

//维持最大堆性质
function maxHeapify(arr, i, heapSize) {
  let r = right(i);    //右子节点
  let l = left(i);     //左子节点

  let largest = i;
  //求right,left和parent三者中最大者
  if (r < heapSize && arr[r] > arr[i]) {
    largest = r;
  }

  if (l < heapSize && arr[l] > arr[largest]) {
    largest = l;
  }

  //如果三者最大者不是parent i,那么需要i和相应的最大者进行交换,以便维持最大堆性质
  if (largest != i) {
    //交换
    let max = arr[largest];
    arr[largest] = arr[i];
    arr[i] = max;
    //交换以后,子节点有可能违背了最大堆定义,所以需要递归处理子节点
    maxHeapify(arr, largest, heapSize);
  }
}

//i的右子节点下标
function right(i) {
  return 2 * i + 2;
}

//i的左子节点下标
function left(i) {
  return 2 * i + 1;
}

//构建最大堆
function buildMaxHeap(arr) {
  for(var i=parseInt(arr.length / 2); i >= 0; i--) {
    maxHeapify(arr, i, arr.length);
  }
}

//使用最大堆排序
function maxHeapSort(arr) {
  //因为最大数总是在堆顶,所以每次把堆顶最大数拿出来,然后重新构建最大堆,再把堆顶数拿出来,以此递归,就能拿到一个从小到大排列的数组
  buildMaxHeap(arr);
  let heapSize = arr.length;
  for(var i=arr.length-1; i>0; i--) {
    let max = arr[0];
    arr[0] = arr[i];
    arr[i] = max;
    heapSize = heapSize - 1;
    maxHeapify(arr, 0, heapSize);
  }
}


//随机获取一个数组
function randNum() {
  return parseInt(Math.random() * 100);
}

function getRandArr(length) {
  var arr = [];
  for(var i=0; i<length; i++) {
    arr.push(randNum());
  }
  return arr;
}

var arr = getRandArr(10);
console.info("随机生成的数组:", arr);
maxHeapSort(arr);
console.info("用堆排序后数组:", arr);

//某次运行结果如下:
//随机生成的数组: [ 29, 92, 50, 89, 96, 64, 36, 47, 34, 96 ]
//用堆排序后数组: [ 29, 34, 36, 47, 50, 64, 89, 92, 96, 96 ]