using System;
using System.Collections.Generic;

namespace CollectionsExt
{
    // 最大堆
    public class MaxHeap<T>
    {
        private const int InitialCapacity = 4;

        private T[] _arr;
        private int _lastItemIndex;
        private IComparer<T> _comparer;

        public MaxHeap()
            : this(InitialCapacity, Comparer<T>.Default)
        {
        }

        public MaxHeap(int capacity)
            : this(capacity, Comparer<T>.Default)
        {
        }

        public MaxHeap(Comparison<T> comparison)
            : this(InitialCapacity, Comparer<T>.Create(comparison))
        {
        }

        public MaxHeap(IComparer<T> comparer)
            : this(InitialCapacity, comparer)
        {
        }

        public MaxHeap(int capacity, IComparer<T> comparer)
        {
            _arr = new T[capacity];
            _lastItemIndex = -1;
            _comparer = comparer;
        }

        public int Count
        {
            get
            {
                return _lastItemIndex + 1;
            }
        }

        public void Add(T item)
        {
            if (_lastItemIndex == _arr.Length - 1)
            {
                Resize();
            }

            _lastItemIndex++;
            _arr[_lastItemIndex] = item;

            MaxHeapifyUp(_lastItemIndex);
        }

        public T Remove()
        {
            if (_lastItemIndex == -1)
            {
                throw new InvalidOperationException("The heap is empty");
            }

            T removedItem = _arr[0];
            _arr[0] = _arr[_lastItemIndex];
            _lastItemIndex--;

            MaxHeapifyDown(0);

            return removedItem;
        }

        public T Peek()
        {
            if (_lastItemIndex == -1)
            {
                throw new InvalidOperationException("The heap is empty");
            }

            return _arr[0];
        }

        public void Clear()
        {
            _lastItemIndex = -1;
        }

        // 堆顶是最小值
        private void MaxHeapifyUp(int index)
        {
            if (index == 0)
            {
                return;
            }

            int childIndex = index;
            int parentIndex = (index - 1) / 2;

            // 堆顶是最小值
            if (_comparer.Compare(_arr[childIndex], _arr[parentIndex]) > 0)
            {
                // swap the parent and the child
                T temp = _arr[childIndex];
                _arr[childIndex] = _arr[parentIndex];
                _arr[parentIndex] = temp;

                // 递归
                MaxHeapifyUp(parentIndex);
            }
        }

        private void MaxHeapifyDown(int index)
        {
            int leftChildIndex = index * 2 + 1;
            int rightChildIndex = index * 2 + 2;
            int biggestItemIndex = index; // The index of the parent

            if (leftChildIndex <= _lastItemIndex &&
                _comparer.Compare(_arr[leftChildIndex], _arr[biggestItemIndex]) > 0)
            {
                biggestItemIndex = leftChildIndex;
            }

            if (rightChildIndex <= _lastItemIndex &&
                _comparer.Compare(_arr[rightChildIndex], _arr[biggestItemIndex]) < 0)
            {
                biggestItemIndex = rightChildIndex;
            }

            if (biggestItemIndex != index)
            {
                // swap the parent with the biggest of the child items
                T temp = _arr[index];
                _arr[index] = _arr[biggestItemIndex];
                _arr[biggestItemIndex] = temp;

                MaxHeapifyDown(biggestItemIndex);
            }
        }

        private void Resize()
        {
            T[] newArr = new T[_arr.Length * 2];
            for (int i = 0; i < _arr.Length; i++)
            {
                newArr[i] = _arr[i];
            }

            _arr = newArr;
        }
    }
}