JavaScriptでヒープソートを実装する

code:js

import Heap from "./heap.js";

class HeapRecursive extends Heap {

heapify(arr, n, i) {

let largest = i;

const childLeft = 2 * i + 1;

const childRight = 2 * i + 2;

// swap needed: parent has an element that has heavier than themselves

if (largest !== i) {

this.heapify(arr, n, largest);

}

}

}

class HeapSort {

constructor(arr, heaper) {

this.arr = arr;

this.heapifier = new heaper();

}

heapSort() {

// 親から子のノード番号は決まるので、親だけ舐めれば OK

const n = this.arr.length;

for (let i = Math.floor(n / 2) - 1; i >= 0; i -= 1) {

this.heapifier.heapify(this.arr, n, i);

}

for (let i = n - 1; i >= 0; i -= 1) {

console.log(this.arr);

this.heapifier.heapify(this.arr, i, 0);

}

return this.arr;

}

}

let arr = "7,3,2,6,5,8,1,4".split(",").map(e => +e);

new HeapSort(arr, HeapRecursive).heapSort();