class PriorityQueue<TKey, TValue>
    {
        private List<KeyValuePair<TKey, TValue>> _heap;
        public int size;
        private IComparer<TKey> _comparer;

        public PriorityQueue() : this(Comparer<TKey>.Default)
        {
        }

        public PriorityQueue(IComparer<TKey> comparer)
        {
            _heap = new List<KeyValuePair<TKey, TValue>>();
            _comparer = comparer;
        }

        public void Enqueue(TKey key, TValue value)
        {
            Console.WriteLine(_heap.Capacity);
            KeyValuePair<TKey, TValue> tmp = new KeyValuePair<TKey, TValue>(key, value);
            _heap.Add(tmp);
            ++size;
            SiftUp();
        }

        private void SiftUp()
        {
            int cur = _heap.Count - 1;
            int parents = (cur - 1)/2;
            while (cur > 0)
            {
                if (!Swap(cur, parents))
                    break;

                cur = parents;
                parents = (cur - 1)/2;
            }
        }

        private void SiftDown()
        {
            if (size < 2) return;
            int cur = 0;
            int child = 0;

            while (cur < size)
            {
                child = cur*2 + 1;
                if (child > size - 1) return;
                if (child + 1 < size && _comparer.Compare(_heap[child].Key, _heap[child + 1].Key) > 0)
                    ++child;

                if (!Swap(child, cur))
                    break;

                cur = child;
            }
        }

        public KeyValuePair<TKey, TValue> Dequeue()
        {
            KeyValuePair<TKey, TValue> result = _heap[0];
            int idx = _heap.Count - 1;
            _heap[0] = _heap[idx];
            _heap.RemoveAt(idx);
            --size;
            SiftDown();
            return result;
        }

        private bool Swap(int parents, int cur)
        {
            if (_comparer.Compare(_heap[parents].Key, _heap[cur].Key) < 0)
            {
                KeyValuePair<TKey, TValue> tmp = _heap[parents];
                _heap[parents] = _heap[cur];
                _heap[cur] = tmp;
                return true;
            }
            return false;
        }
    }