# Priority queue, whose elements are ints, and whose priorities can be
# adjusted without taking them out of the queue. Modeled after
# Sedgewick & Wayne's heap class, specifically IndexMinPQ.java,
# available at https://algs4.cs.princeton.edu/
#
# Jesper Larsson, Malmö University 2018–2020

class VertexPQ:
    def __init__(self, max_n):
        self.__n = 0
        self.__pq = [-1] * (max_n+1)             # vertices in heap order
        self.__qp = [-1] * max_n                 # positions of vertices in pq
        self.__dist = [float('inf')] * max_n  # keys of vertices, lower dist means higher prio

    def __exch(self, i, j):
        v = self.__pq[i]
        w = self.__pq[j]
        self.__pq[i] = w
        self.__pq[j] = v
        self.__qp[w] = i
        self.__qp[v] = j
            
    def __swim(self, k):
        while k > 1 and self.__dist[self.__pq[k//2]] > self.__dist[self.__pq[k]]:
            self.__exch(k, k//2)
            k //= 2

    def __sink(self, k):
        while 2*k <= self.__n:
            j = 2*k
            if j < self.__n and self.__dist[self.__pq[j]] > self.__dist[self.__pq[j+1]]:
                j += 1
            if self.__dist[self.__pq[k]] <= self.__dist[self.__pq[j]]:
                break
            self.__exch(k, j)
            k = j

    def set_dist(self, v, d):
        if self.__qp[v] < 0:                 # vertex not in queue, add it
            self.__n += 1
            self.__pq[self.__n] = v
            self.__qp[v] = self.__n
            self.__dist[v] = d
            self.__swim(self.__n)
        else:                         # already in queue, modify
            grows = d > self.__dist[v]
            self.__dist[v] = d
            if grows:
                self.__sink(self.__qp[v])
            else:
                self.__swim(self.__qp[v])

    def get_dist(self, v):
        return self.__dist[v]

    def del_min(self):
        min = self.__pq[1]
        self.__exch(1, self.__n)
        self.__n -= 1
        self.__sink(1)
        self.__qp[min] = -1
        return min

    def __bool__(self):
        return bool(self.__n)