public class Heap
    {
        public int heapSize;

        public List<City> data;

        public Heap()
        {
            heapSize = 0;
            data = new List<City>();
        }

        public Heap(List<City> _data)
        {
            heapSize = 0;
            data = _data;
        }

        public City getTop()
        {
            return data[0];
        }

        public void print()
        {
            foreach(City city in data)
            {
                Console.WriteLine(city.source + " za " + Program.d[city.source - 1]);
            }
            Console.WriteLine();
        }

        private void Swap(int index1, int index2)
        {
            City tmp = data[index1];
            data[index1] = data[index2];
            data[index2] = tmp;
        }

        /*
         * root
         * dziecko L roota
         * dziecko P roota
         * dziecko L dziecka L
         * dziecko P dziecka L
         * dziecko L dziecka P
         * dziecko P dziecka P
         *
         * lewe dziecko 2n+1
         * prawe dziecko 2n+2
         *
         * ojciec n-1/2
         */

        public void push(City city)
        {
            data.Add(city);
            heapSize++;
            construct();
        }

        public void construct()
        {
            int index = heapSize;

            while(index > 1)
            {
                if(Program.d[data[index].source] < Program.d[data[index - 1 / 2].source])
                {
                    Swap(index, index - 1 / 2);
                }

                index = index - 1 / 2;
            }
        }

        public void pop()
        {
            data.RemoveAt(0);
            heapSize--;
            construct();
        }
}