priority queue

priority_queue.ts

class MinMaxHeap {
    private heap: number[];
    private type: HeapType;
    private compare: (a: number, b: number) => boolean;

    constructor(type: HeapType = 'min') {
        this.heap = [];
        this.type = type;
        this.compare = type === 'min' 
            ? (a, b) => a < b
            : (a, b) => a > b;
    }

    // Get index of parent node
    private getParentIndex(index: number): number {
        return Math.floor((index - 1) / 2);
    }

    // Get index of left child node
    private getLeftChildIndex(index: number): number {
        return 2 * index + 1;
    }

    // Get index of right child node
    private getRightChildIndex(index: number): number {
        return 2 * index + 2;
    }

    // Swap two nodes
    private swap(index1: number, index2: number): void {
        [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
    }

    // Move the node up the heap until it's in the correct position
    private heapifyUp(): void {
        let currentIndex = this.heap.length - 1;
        
        while (currentIndex > 0) {
            const parentIndex = this.getParentIndex(currentIndex);
            
            if (!this.compare(this.heap[currentIndex], this.heap[parentIndex])) {
                break;
            }
            
            this.swap(currentIndex, parentIndex);
            currentIndex = parentIndex;
        }
    }

    // Move the node down the heap until it's in the correct position
    private heapifyDown(): void {
        let currentIndex = 0;
        const length = this.heap.length;
        
        while (true) {
            const leftChildIndex = this.getLeftChildIndex(currentIndex);
            const rightChildIndex = this.getRightChildIndex(currentIndex);
            let targetIndex = currentIndex;
            
            if (leftChildIndex < length && 
                this.compare(this.heap[leftChildIndex], this.heap[targetIndex])) {
                targetIndex = leftChildIndex;
            }
            
            if (rightChildIndex < length && 
                this.compare(this.heap[rightChildIndex], this.heap[targetIndex])) {
                targetIndex = rightChildIndex;
            }
            
            if (targetIndex === currentIndex) {
                break;
            }
            
            this.swap(currentIndex, targetIndex);
            currentIndex = targetIndex;
        }
    }

    // Insert a new element into the heap
    public insert(value: number): void {
        this.heap.push(value);
        this.heapifyUp();
    }

    // Remove and return the root element (min or max depending on heap type)
    public extractRoot(): number | undefined {
        if (this.heap.length === 0) {
            return undefined;
        }
        
        if (this.heap.length === 1) {
            return this.heap.pop();
        }
        
        const root = this.heap[0];
        this.heap[0] = this.heap.pop()!;
        this.heapifyDown();
        
        return root;
    }

    // Get the root element without removing it
    public peek(): number | undefined {
        return this.heap[0];
    }

    // Get the size of the heap
    public size(): number {
        return this.heap.length;
    }
}