Heapsort

internal class Heap : StorageObjectSort
    {
        private object[] items;

        public int Size { get; set; } = 0;

        public override IEnumerable<T> Sort<T>(IComparer<T> sortFunction, IEnumerable<T> collection)
        {
            List<T> objectList = collection.ToList();
            Initialize(objectList.Count);
            objectList.ForEach(o => Insert(o, sortFunction));
            objectList.Clear();

            while (Size > 0)
                objectList.Add((T)Remove(sortFunction));
            return objectList;
        }

        protected override void Insert<T>(object item, IComparer<T> sortFunction)
        {
            items[Size] = item;
            Size++;

            UpHeap(sortFunction);
        }

        protected override object Remove<T>(IComparer<T> sortFunction)
        {
            object buffer = items[0];
            items[0] = null;
            Size--;

            DownHeap(sortFunction);
            return buffer;
        }

        private void Initialize(int count)
        {
            items = new object[count];
        }

        private void Swap(int first, int second)
        {
            object buffer = items[first];
            items[first] = items[second];
            items[second] = buffer;
        }

        private int GetLeftChild(int index)
        {
            return GetRightChild(index) - 1;
        }

        private int GetRightChild(int index)
        {
            return 2 * (index + 1);
        }

        private int GetParent(int index)
        {
            return (index + 1) / 2 - 1;
        }

        private void UpHeap<T>(IComparer<T> sortFunction)
        {
            if (Size <= 1) return;

            int currentElement = Size - 1;
            int currentElementParent = GetParent(currentElement);
            while(currentElementParent >= 0 && sortFunction.Compare((T)items[currentElementParent], (T)items[currentElement]) > 0)
            {
                Swap(currentElement, currentElementParent);
                currentElement = currentElementParent;
                currentElementParent = GetParent(currentElement);
            }
        }

        private void DownHeap<T>(IComparer<T> sortFunction)
        {
            int currentIndex = 0;
            int leftChild = GetLeftChild(currentIndex);
            int rightChild = GetRightChild(currentIndex);
            while (leftChild < items.Length || rightChild < items.Length)
            {
                int smallerChild = GetSmallerChild<T>(sortFunction, leftChild, rightChild);
                if (smallerChild == -1) return; //There is no smaller child.

                if (items[currentIndex] == null || sortFunction.Compare((T)items[smallerChild], (T)items[currentIndex]) < 0)
                {
                    Swap(smallerChild, currentIndex);
                    currentIndex = smallerChild;
                    leftChild = GetLeftChild(currentIndex);
                    rightChild = GetRightChild(currentIndex);
                    continue;
                }

                return;
            }
        }

        private int GetSmallerChild<T>(IComparer<T> sortFunction, int first, int second)
        {
            if (first >= items.Length) return second;
            else if (second >= items.Length) return first;
            else if (items[first] != null && items[second] == null) return first;
            else if (items[second] != null && items[first] == null) return second;
            else if (items[first] == null && items[second] == null) return -1;
            return (sortFunction.Compare((T)items[first], (T)items[second]) < 0) ? first : second;
        }
    }

100

101

102

103

104

105

106

107

108

109

110

internal class Heap : StorageObjectSort

{

private object[] items;

public int Size { get; set; } = 0;

public override IEnumerable<T> Sort<T>(IComparer<T> sortFunction, IEnumerable<T> collection)

{

List<T> objectList = collection.ToList();

Initialize(objectList.Count);

objectList.ForEach(o => Insert(o, sortFunction));

objectList.Clear();

while (Size > 0)

objectList.Add((T)Remove(sortFunction));

return objectList;

}

protected override void Insert<T>(object item, IComparer<T> sortFunction)

{

items[Size] = item;

Size++;

UpHeap(sortFunction);

}

protected override object Remove<T>(IComparer<T> sortFunction)

{

object buffer = items[0];

items[0] = null;

Size--;

DownHeap(sortFunction);

return buffer;

}

private void Initialize(int count)

{

items = new object[count];

}

private void Swap(int first, int second)

{

object buffer = items[first];

items[first] = items[second];

items[second] = buffer;

}

private int GetLeftChild(int index)

{

return GetRightChild(index) - 1;

}

private int GetRightChild(int index)

{

return 2 * (index + 1);

}

private int GetParent(int index)

{

return (index + 1) / 2 - 1;

}

private void UpHeap<T>(IComparer<T> sortFunction)

{

if (Size <= 1) return;

int currentElement = Size - 1;

int currentElementParent = GetParent(currentElement);

while(currentElementParent >= 0 && sortFunction.Compare((T)items[currentElementParent], (T)items[currentElement]) > 0)

{

Swap(currentElement, currentElementParent);

currentElement = currentElementParent;

currentElementParent = GetParent(currentElement);

}

private void DownHeap<T>(IComparer<T> sortFunction)

{

int currentIndex = 0;

int leftChild = GetLeftChild(currentIndex);

int rightChild = GetRightChild(currentIndex);

while (leftChild < items.Length || rightChild < items.Length)

{

int smallerChild = GetSmallerChild<T>(sortFunction, leftChild, rightChild);

if (smallerChild == -1) return; //There is no smaller child.

if (items[currentIndex] == null || sortFunction.Compare((T)items[smallerChild], (T)items[currentIndex]) < 0)

{

Swap(smallerChild, currentIndex);

currentIndex = smallerChild;

leftChild = GetLeftChild(currentIndex);

rightChild = GetRightChild(currentIndex);

continue;

}

return;

}

private int GetSmallerChild<T>(IComparer<T> sortFunction, int first, int second)

{

if (first >= items.Length) return second;

else if (second >= items.Length) return first;

else if (items[first] != null && items[second] == null) return first;

else if (items[second] != null && items[first] == null) return second;

else if (items[first] == null && items[second] == null) return -1;

return (sortFunction.Compare((T)items[first], (T)items[second]) < 0) ? first : second;

}