Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 | 30x 76x 76x 31x 31x 31x 56x 56x 76x 76x 76x 19x 76x 76x 4x 76x 56x 20x 20x 8x 19x 19x 19x 18x 19x 19x 19x 30x 30x 19x 11x 11x 64x 4x 60x 22x 38x 38x 38x 38x 57x | /**
* A classical min-heap.
*/
/** API documentation barrier */
/**
* Comparator function for the min-heap.
*/
export type Comparator<T> = (left: T, right: T) => number;
function parentIdx(idx: number): number {
return Math.trunc((idx - 1) / 2);
}
function leftChildIdx(idx: number): number {
return 2 * idx + 1;
}
function rightChildIdx(idx: number): number {
return 2 * idx + 2;
}
function swap<T>(array: T[], leftIdx: number, rightIdx: number): void {
const temp = array[leftIdx];
array[leftIdx] = array[rightIdx];
array[rightIdx] = temp;
}
function heapify<T>(array: T[], comparatorFn: Comparator<T>, rootIdx: number) {
// Precondition: indices leftChildIdx(rootIdx) and rightChildIdx(rootIdx) are roots of heaps
let currentIdx = rootIdx;
do {
let minIdx = currentIdx;
const l = leftChildIdx(currentIdx);
if (l < array.length && comparatorFn(array[l], array[minIdx]) < 0) {
minIdx = l;
}
const r = rightChildIdx(currentIdx);
if (r < array.length && comparatorFn(array[r], array[minIdx]) < 0) {
minIdx = r;
}
if (minIdx === currentIdx) {
break;
}
swap(array, currentIdx, minIdx);
currentIdx = minIdx;
} while (true);
}
/**
* A binary min-heap.
*
* @typeparam T the type of elements held in this min heap
*/
export default class MinHeap<T> {
private readonly comparatorFn_: Comparator<T>;
private readonly array_: T[];
constructor(iterable: Iterable<T>, comparatorFn: Comparator<T>) {
this.comparatorFn_ = comparatorFn;
this.array_ = Array.from(iterable);
for (let i = Math.trunc(this.array_.length / 2) - 1; i >= 0; --i) {
heapify(this.array_, this.comparatorFn_, i);
}
}
/**
* Inserts the given element into this min-heap.
*
* The runtime of this operation is O(log n).
*
* @param element the element to add
*/
public add(element: T): void {
this.array_.push(element);
let currentIdx = this.array_.length - 1;
do {
const p = parentIdx(currentIdx);
if (currentIdx <= 0 || this.comparatorFn_(this.array_[p], this.array_[currentIdx]) < 0) {
break;
}
swap(this.array_, p, currentIdx);
currentIdx = p;
} while (true);
}
/**
* Retrieves and removes the minimum element of this min-heap.
*
* The runtime of this operation is O(log n).
*
* @return the minimum element or undefined if the min-heap is empty
*/
public extractMin(): T | undefined {
if (this.array_.length === 0) {
return undefined;
} else if (this.array_.length === 1) {
return this.array_.pop();
}
const min = this.array_[0];
this.array_[0] = this.array_.pop()!;
heapify(this.array_, this.comparatorFn_, 0);
return min;
}
/**
* Returns whether this min-heap is empty.
*/
public isEmpty(): boolean {
return this.array_.length === 0;
}
}
|