中文
devexamples

In-Place Heap Sort With Comparator

Build a max heap and sort an array in place in O(n log n) time with no extra allocations, using a pluggable comparator for custom orders.

JavascriptData Integrity

Code

snippet
export function heapSort(items, compare = defaultCompare) {
  if (!Array.isArray(items)) throw new TypeError("items must be an array");
  if (typeof compare !== "function") throw new TypeError("compare must be a function");
  const size = items.length;
  for (let root = (size >> 1) - 1; root >= 0; root -= 1) {
    siftDown(items, root, size, compare);
  }
  for (let end = size - 1; end > 0; end -= 1) {
    swap(items, 0, end);
    siftDown(items, 0, end, compare);
  }
  return items;
}

function siftDown(items, root, size, compare) {
  let current = root;
  while (true) {
    const left = current * 2 + 1;
    const right = left + 1;
    let largest = current;
    if (left < size && compare(items[left], items[largest]) > 0) largest = left;
    if (right < size && compare(items[right], items[largest]) > 0) largest = right;
    if (largest === current) return;
    swap(items, current, largest);
    current = largest;
  }
}

function swap(items, left, right) {
  const temporary = items[left];
  items[left] = items[right];
  items[right] = temporary;
}

function defaultCompare(left, right) {
  return left < right ? -1 : left > right ? 1 : 0;
}

const numbers = [9, 4, 7, 1, 8, 4, 2];
console.log(heapSort(numbers));
console.log(heapSort([3, 1, 2], (left, right) => right - left));

Related Examples