using System;

/// <summary>
/// 最小堆
/// </summary>
class MinHeap<T> where T : IComparable
{
    private T[] container; // 存放堆元素的容器
    private int capacity;  // 堆的容量，最大可以放多少个元素
    private int count; // 堆中已经存储的数据个数

    /// <summary>
    /// 构造函数
    /// </summary>
    /// <param name="_capacity"></param>
    public MinHeap(int _capacity)
    {
        capacity = _capacity;
        container = new T[capacity + 1];
        count = 0;
    }

    /// <summary>
    /// 向堆中添加元素
    /// </summary>
    /// <param name="item"></param>
    /// <returns></returns>
    public bool AddItem(T item)
    {
        if (count >= capacity)
            return false;
        count++;
        container[count] = item;
        int index = count;
        while (index > 1)
        {
            if (container[index].CompareTo(container[index / 2]) < 0)
            {
                container[0] = container[index];
                container[index] = container[index / 2];
                container[index / 2] = container[0];
                index = index / 2;
            }
            else
            {
                break;
            }
        }
        return true;
    }

    /// <summary>
    /// 获取最小的元素
    /// </summary>
    /// <returns></returns>
    public T GetMinItem()
    {
        if (count > 0)
            return container[1];
        else
            return default;
    }
    /// <summary>
    /// 删除最小的元素(堆顶元素)
    /// </summary>
    /// <returns></returns>
    public bool DeteleMinItem()
    {
        if (count < 1)
            return false;
        container[1] = container[count];
        container[count] = default;
        count--;
        int index = 1;
        int tempIndex = -1;
        bool change = true;
        while (2*index <= count && change)
        {
            change = false;
            container[index] = container[index];
            tempIndex = -1;
            if (2 * index + 1 <= count)
            {
                if (container[2 * index].CompareTo(container[2 * index + 1]) <= 0)
                {
                    if (container[2 * index].CompareTo(container[index]) < 0)
                    {
                        container[0] = container[index];
                        container[index] = container[2 * index];
                        container[2*index] = container[0];
                        change = true;
                    }
                    tempIndex = 2 * index;
                }
                else
                {
                    if (container[2 * index + 1].CompareTo(container[index]) < 0)
                    {
                        container[0] = container[index];
                        container[index] = container[2*index+1];
                        container[2 * index + 1] = container[0];
                        change = true;
                    }
                    tempIndex = 2 * index + 1;
                }
            }
            else
            {
                if (container[2 * index].CompareTo(container[index]) < 0)
                {
                    container[0] = container[index];
                    container[index] = container[2 * index];
                    container[2 * index] = container[0];
                    change = true;
                }
                tempIndex = 2 * index;
            }
            index = tempIndex;
        }
        return true;
    }

    /// <summary>
    /// 输出堆中元素
    /// </summary>
    public void ShowHeap()
    {
        if (count < 1)
            return;
        for (int i = 1; i <= count; i++)
        {
            Console.WriteLine(container[i]);
        }
    }
}