Node = Struct.new :priority, :element, :prev, :next

attr_reader :head, :tail, :size

def initialize(items = [])
    @head, @tail = nil, nil
    @size = 0
end

# O(n)
def enqueue(priority, element)
    n = Node.new priority, element

    found_min = @tail
    while found_min && found_min.priority > n.priority
        found_min = found_min.prev
    end

    unless found_min
        push_front n
    else
        insert_after found_min, n
    end

    [priority, element]
end

alias_method :<<, :enqueue
alias_method :push, :enqueue

# O(1)
def dequeue
    return nil unless @head

    n = @head
    if @size == 1
        clear
        return [n.priority, n.element]
    end

    @head.next.prev = nil
    @head = @head.next
    @size -= 1
    [n.priority, n.element]
end

alias_method :pop, :dequeue

# O(1)
def min
    return nil unless @head
    [@head.priority, @head.element]
end

alias_method :front, :min

# O(1)
def empty?
    @size == 0
end

# O(1)
def clear
    @head, @tail = nil, nil
    @size = 0
end

# O(n)
def each_forward
    return unless @head

    n = @head
    while n
        yield n.priority, n.element
        n = n.next
    end
end

alias_method :each, :each_forward

# O(n)
def each_backward
    return unless @tail

    n = @tail
    while n
        yield n.priority, n.element
        n = n.prev
    end
end

alias_method :reverse_each, :each_backward

def push_front(n)
    if @head
        n.next = @head
        @head.prev = n
        @head = n
    else
        @head = @tail = n
    end
    @size += 1
end

def insert_after(predecessor, successor)
    successor.next = predecessor.next
    predecessor.next = successor
    successor.prev = predecessor
    @size += 1
end