index

class MinPriorityQueue {
    constructor(priority = e => e) {
        this.heap = [];
        this.priority = priority;
    }
 
    getLeftChildIndex(parentIndex) {
        return 2 * parentIndex + 1;
    }
 
    getRightChildIndex(parentIndex) {
        return 2 * parentIndex + 2;
    }
 
    getParentIndex(childIndex) {
        return Math.floor((childIndex - 1) / 2);
    }
 
    hasLeftChild(index) {
        return this.getLeftChildIndex(index) < this.heap.length;
    }
 
    hasRightChild(index) {
        return this.getRightChildIndex(index) < this.heap.length;
    }
 
    hasParent(index) {
        return this.getParentIndex(index) >= 0;
    }
 
    leftChild(index) {
        return this.heap[this.getLeftChildIndex(index)];
    }
 
    rightChild(index) {
        return this.heap[this.getRightChildIndex(index)];
    }
 
    parent(index) {
        return this.heap[this.getParentIndex(index)];
    }
 
    swap(index1, index2) {
        [this.heap[index1], this.heap[index2]] =
            [this.heap[index2], this.heap[index1]];
    }
 
    size() {
        return this.heap.length;
    }
 
    isEmpty() {
        return this.heap.length === 0;
    }
 
    front() {
        return this.heap[0];
    }
 
    enqueue(item) {
        this.heap.push(item);
        this.heapifyUp();
    }
 
    dequeue() {
        if (this.isEmpty()) return undefined;
 
        const item = this.heap[0];
 
        this.heap[0] = this.heap[this.heap.length - 1];
        this.heap.pop();
 
        if (!this.isEmpty()) {
            this.heapifyDown();
        }
 
        return item;
    }
 
    heapifyUp() {
        let index = this.heap.length - 1;
 
        while (
            this.hasParent(index) &&
            this.priority(this.parent(index)) >
            this.priority(this.heap[index])
        ) {
            const parentIndex = this.getParentIndex(index);
 
            this.swap(parentIndex, index);
 
            index = parentIndex;
        }
    }
 
    heapifyDown() {
        let index = 0;
 
        while (this.hasLeftChild(index)) {
            let smallerChildIndex = this.getLeftChildIndex(index);
 
            if (
                this.hasRightChild(index) &&
                this.priority(this.rightChild(index)) <
                this.priority(this.leftChild(index))
            ) {
                smallerChildIndex = this.getRightChildIndex(index);
            }
 
            if (
                this.priority(this.heap[index]) <=
                this.priority(this.heap[smallerChildIndex])
            ) {
                break;
            }
 
            this.swap(index, smallerChildIndex);
 
            index = smallerChildIndex;
        }
    }
}