Dijkstra Heap

const int N = 100005;

template<typename T> // max path type
class Heap
{
public:
    int vec[N], pos[N];
    T val[N];
    int siz;

    Heap() //number of vertexes
    {
        siz = 0;
        for (int i = 0; i < N; i++)
            pos[i] = -1;
    }

    void siftDown(int v)
    {
        while (true)
        {
            int u = (v << 1) | 1;
            if (u + 1 < siz && val[vec[u + 1]] < val[vec[u]])
                ++u;
            if (u < siz && val[vec[u]] < val[vec[v]])
            {
                swap(pos[vec[u]], pos[vec[v]]);
                swap(vec[u], vec[v]);
                v = u;
            }
            else
                break;
        }
    }

    void siftUp(int v)
    {
        while (v)
        {
            int u = ((v - 1) >> 1);
            if (val[vec[u]] > val[vec[v]])
            {
                swap(pos[vec[u]], pos[vec[v]]);
                swap(vec[u], vec[v]);
                v = u;
            }
            else
                break;
        }
    }

    Heap(vector<T> a)
    {
        vec = a;
        for (int i = siz - 1; i >= 0; i--)
            siftDown(i);
    }

    T best_vertex()
    {
        return vec[0];
    }

    void push(int v, T value)
    {
        if (pos[v] == -1)
        {
            vec[siz++] = v;
            pos[v] = siz - 1;
        }
        val[v] = value;
        siftUp(pos[v]);
    }

    void pop()
    {
        swap(vec[0], vec[siz - 1]);
        swap(pos[vec[0]], pos[vec[siz - 1]]);
        pos[vec[siz - 1]] = -1;
        siz--;
        siftDown(0);
    }

    int size()
    {
        return siz;
    }
};