using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace WindowsFormsApplication4
{
    class Dheap
    {
        List<int> key=new List<int>();
        List<string> name = new List<string>();
        int d,n;
        public Dheap(int d, int n) 
        {
            this.d = d;
            this.n = n;
        }
        public int Father(int i)
        {
            return (int)((i-2)/d)+1;
        }
        public int FirstChild(int i) 
        {
            if (((i - 1) * d + 2) > n) return 0;
            else return ((i - 1) * d + 2);

        }
        public int LastChild(int i) 
        {
            int k = FirstChild(i);
            if (k == 0) 
                return 0;
            else 
                return Math.Min(k + d - 1, n);
        }
        public int MinChild(int i) 
        {
            int minChild = 0;
            int kf = FirstChild(i);
            if (kf == 0) return i;
            else
            {          
                int k1 = LastChild(i);
                int minKey = key[kf];
                minChild = kf;
                for (int j = kf + 1; j <= k1; ++j)
                    if (key[j] < minKey)
                    {
                        minKey = key[j];
                        minChild = j;
                    }
            }
            return minChild;
        }
        public void Dive(int i)
        {
            int key0 = key[i];
            string name0 = name[i];
            int c = MinChild(i);
            while (c != i && key0 > key[c])
            {
                key[i] = key[c];
                name[i] = name[c];
                i = c;
                c = MinChild(i);
            }
            key[i] = key0;
            name[i] = name0;
        }
        public void Emersion(int i) 
        {
            int key0 = key[i];
            string name0 = name[i];
            int p = Father(i);
            while (i != 0 && key[p] > key0)
            {
                key[i] = key[p];
                name[i] = name[p];
                i = p;
                p = Father(i);
            }
            key[i] = key0;
            name[i] = name0;
        }
        public 
    }
}