PriorityQueue.coffee

sortedIndex = require('lodash/sortedIndex')

module.exports = class PriorityQueue

    constructor: () ->
        @heap = []
        @length = 0
        
    push: (item, priority=0) ->
        data =
            data: item,
            priority: priority
    
        index = sortedIndex @heap, data, "priority"
      
        @heap.splice index, 0, data
        return @length = @heap.length
    
    pop: () ->
        item = @heap.pop()
        @length = @heap.length
        if item then item.data else undefined

PriorityQueue.ts

import sortedIndex from 'lodash/sortedIndex';

interface QueueItem<T> {
    data: T;
    priority: number;
}

export default class PriorityQueue<T> {
    private heap: QueueItem<T>[] = [];

    constructor() {
        return new Proxy(this, {
            get: (target, prop) => {
                if (prop === 'length') {
                    return target.heap.length;
                }
                if (prop === 'peek') {
                    return target.heap.length > 0 ? target.heap[target.heap.length - 1].data : undefined;
                }
                return Reflect.get(target, prop);
            }
        });
    }

    push(item: T, priority = 0): number {
        const queueItem: QueueItem<T> = { data: item, priority };
        const index = sortedIndex(this.heap, queueItem, 'priority');
        this.heap.splice(index, 0, queueItem);
        return this.heap.length;
    }

    pop(): T | undefined {
        return this.heap.pop()?.data;
    }

    [Symbol.iterator](): Iterator<T> {
        return this.heap.map(item => item.data)[Symbol.iterator]();
    }
}