JS堆排序 #

// 一般用数组来表示堆，下标为 i 的结点的父结点下标为(i-1)/2；其左右子结点分别为 (2i + 1)、(2i + 2)
const s = [1, 5, 34, 34, 56, 7, 110, 9];

function swap(index1, index2) {
  const k = s[index1];
  s[index1] = s[index2];
  s[index2] = k;
}

function sort() {
  console.log(s, new Date().getTime());
  buildMaxHeap(s.length);
  for (let i = s.length - 1; i >= 0; i--) {
    swap(0, i);
    console.log(s, "++++++");
    buildMaxHeap(i - 1);
  }
  console.log(s, new Date().getTime());
}

// 判断节点I是否需要切换
function heapSwap(i, len) {
  const li = 2 * i + 1;
  const ri = 2 * i + 2;
  let cMax = li;

  if (li > len) return;
  if (ri <= len && s[ri] > s[li]) {
    cMax = ri;
  }

  if (s[i] < s[cMax]) {
    swap(i, cMax);
    heapSwap(cMax, len);
  }
}

// 构建最大堆
function buildMaxHeap(len) {
  for (let i = len - 1; i >= 0; i--) {
    heapSwap(i, len);
  }
  console.log(s, "---");
}

sort();