using System;

namespace DataStructure.HeapPQ
{
    /// <summary>
    /// Class1 的摘要说明。
    /// </summary>
    class PriorityQueueApplet
    {
        /// <summary>
        /// 应用程序的主入口点。
        /// </summary>
        [STAThread]
        static void Main(string[] args)
        {
            
            int n=10;
            ComparisonKey[] A=new ComparisonKey[n];//A为需要进行排序的数组，10个
            //将数组A初始化为进行10个整数的排序并对其进行打印
            for(int i=0;i<n;i++)
            {
                A[i]=new PQItem(squareOf(3*i-13));
                Console.Write(A[i]+",");
            }
            Console.WriteLine();
            //            本排序的整数输出为：169.100.49.16.1.4.25.64.121.196
            //利用priorityQueue sorting对数组进行排序
            priorityQueueSort(A);
            //排序之后打印数组A中的值
            for(int i=0;i<n;i++)
            {
                Console.WriteLine(A[i]+",");
            }
            Console.WriteLine();
        }
        public static int squareOf(int x) { return x*x; }
        public static void priorityQueueSort(ComparisonKey[] A)
        {
            int i;//i为一个整数数组的索引变量
            int n=A.Length;//N为要排序数组A的长度
            PriorityQueue PQ=new PriorityQueue();//PQ初始为空
            for(i=0;i<n;i++) PQ.insert(A[i]);//将A的元素插入PQ中
            for(i=n-1;i>=0;i--) PQ.remove();//删除PQ的元素并将其插入A中
        }
    }


    public class ListNode
    {
        public ComparisonKey item;
        public ListNode link;
    }

    class PriorityQueue
    {
        private int count;//优先队列中的元素数目
        private int capacity;//可用数组位置的数量
        private int capacityIncrement;//在数组扩展过程中容量的增幅

        private ComparisonKey[] itemArray;//存放PQ元素的数组

        /*---------------------*/

        //定义构造函数
        public PriorityQueue()
        {
            count=0;
            capacity=16;
            capacityIncrement=8;
            itemArray=new ComparisonKey[capacity];
        }

        public int Size()
        {
            return count;
        }

        
        /*insert()方法在链表中插入一个新的元素*/

        public void insert(ComparisonKey newItem)
        {
            //如果itemArray容量不够
            //可以通过capacityIncrement
            if(count==capacity-1)
            {
                capacity+=capacityIncrement;
                ComparisonKey[] tempArray=new ComparisonKey[capacity];
                for(int i=1;i<=count;i++)
                {
                    tempArray[i]=itemArray[i];
                }
                itemArray=tempArray;
            }

            //优先队列数量递增1 并在当前优先对联元素顺序的末端插入newItem
            count++;
            int childLoc=count;
            int parentLoc=childLoc/2;

            while(parentLoc!=0)
            {
                if(newItem.compareTo(itemArray[parentLoc])<=0)
                {
                    itemArray[childLoc]=newItem;//存储newItem并返回
                    return;
                }
                else
                {
                    itemArray[childLoc]=itemArray[parentLoc];
                    childLoc=parentLoc;
                    parentLoc=childLoc/2;//变换位置
                }
            }
            itemArray[childLoc]=newItem;//将newItem放入最终剩下的位置

        }

        public ComparisonKey remove()
        {
            if(count==0)//如果优先队列为空，返回true;
            {
                return null;
            }
            else//否则，返回根元素重新堆化
            {
                //声明
                int currentLoc;//当前查看的位置
                int childLoc;//currentLoc的孩子
                ComparisonKey itemToPlace;//重新定位的元素值
                ComparisonKey itemToReturn;//返回的删除元素值
                //初始化
                itemToReturn=itemArray[1];//存储稍后返回的根元素
                itemToPlace=itemArray[count--];//末端的叶子元素
                currentLoc=1;//从根开始的currentLoc
                childLoc=2*currentLoc;//从根的左孩子开始childLoc

                while(childLoc<=count)//当仍然存在孩子的时候
                {
                    //设childLoc为currentLoc的较大的孩子
                  if(childLoc<count)
                  {//如果存在右孩子
                    if(itemArray[childLoc+1].compareTo(itemArray[childLoc])>0)
                        childLoc++;
                  }
                    //如果childLoc的元素大于itemToPlace
                    //那么将这个较大元素移动到currentLoc;
                    //并将currentLoc下移
        
                    if(itemArray[childLoc].compareTo(itemToPlace)>0)
                    {
                        itemArray[currentLoc]=itemArray[childLoc];
                        currentLoc=childLoc;
                        childLoc=2*currentLoc;
                    }
                    else
                    {
                        itemArray[currentLoc]=itemToPlace;
                        return itemToReturn;
                    }
                }
                //itemToPlace的最终替换
                itemArray[currentLoc]=itemToPlace;
                //返回最初在根中的元素
                return itemToReturn;
            }

        }
    }

    interface ComparisonKey
    {
        //        如果K1和K2均为ComparisonKey，那么K1.compareTo(k2)就会有三个值0,1,-1,
        //        就是K1==K2,K1>K2,K1<K2顺序是compareTo方法定义的优先级别顺序
        int compareTo(ComparisonKey value);
        //将ComparisonKey转换成可以打印的字符串
        string toOurString();
    }

    public class PQItem:ComparisonKey
    {

        private int key;//key数据包括给出元素优先级别的整数关键字
        public PQItem(int value)
        {
            key=value;
        }
        ComparisonKey 成员

    }
}