Sunday, 26 November 2017

MaxHeap and MinHeap

public class MaxHeap : AbstractHeap
{
    #region constructors

    public MaxHeap() : base()
    {
    }
    #endregion

    #region internal methods
    internal override void heapifyDown()
    {
        int index = 0;
        while (hasLeftChild(index))
        {
            int largerChildIndex = getLeftChildIndex(index);
            if (hasRightChild(index) && rightChild(index) > leftChild(index))
            {
                largerChildIndex = getRightChildIndex(index);
            }

            if (Nodes[largerChildIndex] > Nodes[index])
                swap(index, largerChildIndex);
            else
                break;
            index = largerChildIndex;
        }
    }
    internal override void heapifyUp()
    {
        int index = Size - 1;

        while (hasParent(index) && parent(index) < Nodes[index])
        {
            swap(index, getParentIndex(index));
            index = getParentIndex(index);
        }
    }
    #endregion
}

public class MinHeap : AbstractHeap
{
    #region constructors
    public MinHeap() : base()
    {
    }
    #endregion

    #region internal methods
    internal override void heapifyDown()
    {
        int index = 0;
        while (hasLeftChild(index))
        {
            int smallerChildIndex = getLeftChildIndex(index);
            if (hasRightChild(index) && rightChild(index) < leftChild(index))
            {
                smallerChildIndex = getRightChildIndex(index);
            }

            if (Nodes[smallerChildIndex] < Nodes[index])
                swap(index, smallerChildIndex);
            else
                break;
            index = smallerChildIndex;
        }
    }
    internal override void heapifyUp()
    {
        int index = Size - 1;

        while (hasParent(index) && parent(index) > Nodes[index])
        {
            swap(index, getParentIndex(index));
            index = getParentIndex(index);
        }
    }
    #endregion
}

No comments:

Post a Comment