71 lines
1.8 KiB
JavaScript
71 lines
1.8 KiB
JavaScript
// https://www.freecodecamp.org/learn/coding-interview-prep/data-structures/implement-heap-sort-with-a-min-heap
|
|
function isSorted(a) {
|
|
for (let i = 0; i < a.length - 1; i++) if (a[i] > a[i + 1]) return false;
|
|
return true;
|
|
}
|
|
// Generate a randomly filled array
|
|
function createRandomArray(size = 5) {
|
|
let a = new Array(size);
|
|
for (let i = 0; i < size; i++) a[i] = Math.floor(Math.random() * 100);
|
|
|
|
return a;
|
|
}
|
|
const array = createRandomArray(25);
|
|
|
|
var MinHeap = function () {
|
|
// Only change code below this line
|
|
this.heap = [];
|
|
|
|
this.insert = (item) => {
|
|
this.heap.push(item);
|
|
let me = this.heap.length - 1;
|
|
let parent = Math.trunc((me - 1) / 2);
|
|
while (parent != me && this.heap[parent] > this.heap[me]) {
|
|
const tmp = this.heap[parent];
|
|
this.heap[parent] = this.heap[me];
|
|
this.heap[me] = tmp;
|
|
me = parent;
|
|
parent = Math.trunc((me - 1) / 2);
|
|
}
|
|
};
|
|
|
|
this.print = () => this.heap;
|
|
|
|
this.remove = () => {
|
|
if (!this.heap.length) {
|
|
return;
|
|
}
|
|
const max = this.heap[0];
|
|
this.heap[0] = this.heap[this.heap.length - 1];
|
|
this.heap.pop();
|
|
let i = 0;
|
|
while (
|
|
this.heap[i] > this.heap[i * 2 + 1] ||
|
|
this.heap[i] > this.heap[i * 2 + 2]
|
|
) {
|
|
let swapWith = i * 2 + 1;
|
|
if (this.heap[swapWith] > this.heap[swapWith + 1]) swapWith++;
|
|
const tmp = this.heap[i];
|
|
this.heap[i] = this.heap[swapWith];
|
|
this.heap[swapWith] = tmp;
|
|
i = swapWith;
|
|
}
|
|
return max;
|
|
};
|
|
|
|
this.sort = () => {
|
|
const sorted = [];
|
|
while (this.heap.length) {
|
|
sorted.push(this.remove());
|
|
}
|
|
return sorted;
|
|
};
|
|
// Only change code above this line
|
|
};
|
|
|
|
const h = new MinHeap();
|
|
for (let i = 0; i < 10; i++) {
|
|
h.insert(Math.trunc(Math.random() * 100));
|
|
}
|
|
console.log(h.print());
|