{"size": 1325, "ext": "js", "max_stars_repo_path": "heapsort/javascript/maxheap.js", "max_stars_repo_name": "peferron/algo", "max_stars_repo_stars_event_min_datetime": "2015-02-28T06:28:34.000Z", "max_stars_repo_stars_event_max_datetime": "2022-03-23T18:06:46.000Z", "max_issues_repo_path": "heapsort/javascript/maxheap.js", "max_issues_repo_name": "peferron/algo", "max_issues_repo_issues_event_min_datetime": "2015-01-04T01:36:54.000Z", "max_issues_repo_issues_event_max_datetime": "2021-05-06T20:07:58.000Z", "max_forks_repo_path": "heapsort/javascript/maxheap.js", "max_forks_repo_name": "peferron/algo", "max_forks_repo_forks_event_min_datetime": "2016-06-13T06:18:56.000Z", "max_forks_repo_forks_event_max_datetime": "2022-03-05T10:54:06.000Z"}
{"max_stars_count": 104, "max_issues_count": 4, "max_forks_count": 12, "avg_line_length": 17.4342105263, "max_line_length": 47, "alphanum_fraction": 0.4618867925}
export function fastHeapify(a) {
    const end = a.length - 1;
    for (let i = parent(end); i >= 0; i -= 1) {
        bubbleDown(a, i, end);
    }
    return new Heap(a, end);
}

export function slowHeapify(a) {
    const end = a.length - 1;
    for (let i = 1; i <= end; i += 1) {
        bubbleUp(a, i, end);
    }
    return new Heap(a, end);
}

class Heap {
    constructor(a, end) {
        this.a = a;
        this.end = end;
    }

    deleteMax() {
        const maxValue = this.a[0];
        this.a[0] = this.a[this.end];
        this.end -= 1;
        bubbleDown(this.a, 0, this.end);
        return maxValue;
    }
}

function bubbleUp(a, i) {
    const p = parent(i);
    if (p >= 0 && a[p] < a[i]) {
        swap(a, p, i);
        bubbleUp(a, p);
    }
}

function bubbleDown(a, i, end) {
    let max = i;

    const l = leftChild(i);
    if (l <= end && a[l] > a[max]) {
        max = l;
    }

    const r = rightChild(i);
    if (r <= end && a[r] > a[max]) {
        max = r;
    }

    if (max !== i) {
        swap(a, max, i);
        bubbleDown(a, max, end);
    }
}

function swap(a, i, j) {
    const t = a[i];
    a[i] = a[j];
    a[j] = t;
}

function parent(i) {
    return Math.floor((i - 1) / 2);
}

function leftChild(i) {
    return 2 * i + 1;
}

function rightChild(i) {
    return 2 * i + 2;
}
