Heaps and Heapsort Algorithms

Arrays<public> := module:

    <# Array utility to swap the elements contained in indices I and J #>
    (Array:[]t where t:type).Swap<public>(FirstIndex:int, SecondIndex:int)<decides><transacts>:[]t =
        ArrayTemp := Array.ReplaceElement[FirstIndex, Array[SecondIndex]]
        return ArrayTemp.ReplaceElement[SecondIndex, Array[FirstIndex]]


Heaps<public> := module:

    using { Arrays }

    MinHeap<public>(t:type) := class<concrete>:

        # Properties 
        Heap<internal>:[]t = array{}
        Size<internal>:int = 0
        LessThan<internal>:?type{_(:t,:t)<decides><transacts>:void} = false
        Equivalent<internal>:?type{_(:t,:t)<decides><transacts>:void} = false

        # Get the size of the heap array
        GetSize<public>()<transacts>:int =
            Size

        # Get a copy of the heap array 
        GetHeap<public>()<transacts>:[]t =
            Heap

        # Get the less than comparison function
        # Fails if no less than specified, succeeds and returns the function if specified
        GetLessThan<public>()<decides><transacts>:type{_(:t,:t)<decides><transacts>:void} =
            LessThan?

        # Get the equivalent comparison function
        # Fails if no equivalent specified, succeeds and returns the function if specified
        GetEquivalent<public>()<decides><transacts>:type{_(:t,:t)<decides><transacts>:void} =
            Equivalent?
   
        # Get the minimum value in the heap
        # Fails if heap is empty, succeeds and returns minimum value otherwise
        GetMin<public>()<decides><transacts>: t =
            Heap[0]

        # Get the index in the heap array of the element with the given key
        # Fails if key is not found, succeeds and returns the index key is found
        GetIndex<public>(Key:t)<decides><transacts>:int =
            var ReturnIndex:?int = false
            var LoopIndex:int = 0
            # Traverse the array linearly to find the index of the provided key
            loop:
                if (LoopIndex = Size):
                    break
                else:
                    if (Equivalent?[Heap[LoopIndex], Key]):
                        set ReturnIndex = option{LoopIndex}
                        break
                set LoopIndex += 1
            ReturnIndex?

        # Get the element key of the element at index ElementIndex
        # Fails if ElementIndex is either negative or greater than the size of the array, succeeds otherwise
        GetKey<public>(ElementIndex:int)<decides><transacts>:t =
            Heap[ElementIndex]

        # Get the index of the parent of the element at index ElementIndex
        # Should not fail
        Parent<public>(ElementIndex:int)<decides><transacts>:int =
            Floor((ElementIndex - 1) / 2)

        # Get the index of the left child of the element at index ElementIndex
        Left<public>(ElementIndex:int)<transacts>: int =
            (2 * ElementIndex) + 1

        # Get the index of the right child of the element at index ElementIndex
        Right<public>(ElementIndex: int)<transacts>:int =
            (2 * ElementIndex) + 2

        # Extract the minimum value from the Heap and return resultant Heap 
        ExtractMin<public>()<decides><transacts>:tuple(MinHeap(t), t) =
            # Get the minimum value, move the last value in the heap to the front of the heap array
            HeapMin := Self.GetMin[]
            var NewHeapArr:[]t = Self.Heap
            NewRoot := NewHeapArr[NewHeapArr.Length - 1]
            set NewHeapArr[0] = NewRoot
            NewArrTemp := NewHeapArr.RemoveElement[NewHeapArr.Length - 1]
            set NewHeapArr = NewArrTemp
            ReturnHeap:MinHeap(t) = MinHeap(t):
                MakeMinHeap<constructor>(Self)
                Heap := NewHeapArr
                Size := NewHeapArr.Length
            # Heapify the first value in the array and return this new heap and the previous minimum value
            if (ReturnHeap.GetSize() > 0):
                (ReturnHeap.Heapify[0], HeapMin)
            else:
                (ReturnHeap, HeapMin)

        # Decrease the value of the key located in position Index to value Key and return resultant Heap 
        # Succeeds if `0 <= ElementIndex < Self.Size`
        DecreaseKey<public>(ElementIndex:int, Key:t)<decides><transacts>:MinHeap(t) =
            # Decrease the value of the element in index ElementIndex to the new value Key
            var CurrentKey:int = ElementIndex
            var NewHeapArr:[]t = Self.Heap
            set NewHeapArr[ElementIndex] = Key
            # Decreaseing the value of the element's key might break the heap property
            # Since the Key is decreased, the element might need to move higher in the tree
            # Start with the current position of the element and move up the tree until
            # the heap property is satisfied
            loop:
                if:
                    CurrentKey = 0 or
                    LessThan?[NewHeapArr[Parent[CurrentKey]], NewHeapArr[CurrentKey]] or
                    Equivalent?[NewHeapArr[Parent[CurrentKey]], NewHeapArr[CurrentKey]]
                then:
                    break
                else:
                    if (KeyTmp := Parent[CurrentKey], HeapArrTemp := NewHeapArr.Swap[CurrentKey, KeyTmp]):
                        set NewHeapArr = HeapArrTemp
                        set CurrentKey = KeyTmp
                    else:
                        break
            MinHeap(t):
                MakeMinHeap<constructor>(Self)
                Heap := NewHeapArr

        # Delete the key at the given index while maintaining the Heap Property and return resultant heap
        # Succeeds if `0 <= ElementIndex < Self.Size`
        DeleteKeyAtIndex<public>(ElementIndex:int)<decides><transacts>:MinHeap(t) =
            # Decrease the value of the key at Index to the minimum value, extract that value, then return the resulting heap
            Self.DecreaseKey[ElementIndex, Self.GetMin[]].ExtractMin[](0)

        # Delete the first instance of this Key from the heap and return resultant heap 
        # Fails if the heap does not contain an element with key Key
        DeleteKey<public>(Key:t)<decides><transacts>:MinHeap(t) =
            Self.DeleteKeyAtIndex[Self.GetIndex[Key]]

        # Insert the given Key into the heap while maintaining the Heap Property and return resultant heap
        InsertKey<public>(Key:t)<transacts>:MinHeap(t) =
            # Insert the new key at the end of the heap's array
            var NewHeapArr:[]t = Self.Heap + array{Key}
            var ElementIndex:int = NewHeapArr.Length - 1
            # Traverse the heap tree from the bottom up starting with the newly inserted element
            # swapping the newly inserted element with its parent if it violates the heap property
            # Terminate this process and break the loop once the heap property is satisfied
            loop:
                if:
                    ElementIndex > 0
                    ParentIndex := Parent[ElementIndex]
                    Self.LessThan?[NewHeapArr[ElementIndex], NewHeapArr[ParentIndex]]
                    HeapArrTemp := NewHeapArr.Swap[ParentIndex, ElementIndex]
                then:
                    set NewHeapArr = HeapArrTemp
                    set ElementIndex = ParentIndex
                else:
                    break
            MinHeap(t):
                MakeMinHeap<constructor>(Self)
                Heap := NewHeapArr
                Size := NewHeapArr.Length

        # Construct a heap by positioning the element in index i in the proper location to maintain heap property
        # Heapify correctly places the element at index ElementIndex in the subtree rooted at index ElementIndex
        # Succeeds if `0 <= ElementIndex < Self.Size`
        Heapify<public>(ElementIndex:int)<decides><transacts>:MinHeap(t) =
            var Smallest:int = ElementIndex
            var NewHeapArr:[]t = array{}
            SmallestElement:t = Self.Heap[ElementIndex]
            LeftNode:int = Left(ElementIndex)
            RightNode:int = Right(ElementIndex)
            # If the element at index ElementIndex has a left child and the left child is smaller
            # update the index of the smallest element to the left child index
            if (LeftNode < Size, LessThan?[Self.Heap[LeftNode], SmallestElement]):
                set Smallest = LeftNode
            # If the element at the index of the right child is smaller than the index of the smaller 
            # of ElementIndex and the left child update the index of the smallest element to the right child index
            if (RightNode < Size, LessThan?[Self.Heap[RightNode], Self.Heap[Smallest]]):
                set Smallest = RightNode
            # If the smallest element index is not the element that we started with, swap the element with whichever
            # child was determined to be smaller, create a new heap after the swap, then heapfiy the
            # subtree rooted at the smaller of the two children
            if (Smallest <> ElementIndex, HeapArrTemp := Self.Heap.Swap[Smallest, ElementIndex]):
                set NewHeapArr = HeapArrTemp
                NewHeap := MinHeap(t):
                    MakeMinHeap<constructor>(Self)
                    Heap := NewHeapArr
                return NewHeap.Heapify[Smallest]
            else:
                return Self

    # Construct a heap from an array, ordering function, and equivalence function
    MakeMinHeap<public><constructor>(
        HeapIn:[]t,
        LessThan:type{_(:t,:t)<decides><transacts>:void},
        Equivalent:type{_(:t,:t)<decides><transacts>:void} where t:type
    )<transacts> := MinHeap(t):
        # Define variables for the block portion of the constructor
        let:
            var NewHeapArr: MinHeap(t) = MinHeap(t):
                Heap := HeapIn
                Size := HeapIn.Length
                LessThan := option{LessThan}
                Equivalent := option{Equivalent}
            var Start:int = 0
        # Heapify the array starting at the bottom and working up the tree to the root
        block:
            if (StartTemp := Floor(HeapIn.Length / 2), set Start = StartTemp):
                for (Index := 0..Start):
                    if (HeapArrTemp := NewHeapArr.Heapify[Start - Index]):
                        set NewHeapArr = HeapArrTemp
        Heap := NewHeapArr.GetHeap()
        Size := HeapIn.Length
        LessThan := option{LessThan}
        Equivalent := option{Equivalent}

    # Construct a copy of a heap from an existing heap
    MakeMinHeap<public><constructor>(HeapIn: MinHeap(t) where t:type)<transacts> := MinHeap(t):
        Heap := HeapIn.Heap
        Size := HeapIn.Size
        LessThan := HeapIn.LessThan
        Equivalent := HeapIn.Equivalent

    # Heapsort array of any type
    Heapsort<public>(
        ArrayIn:[]t,
        LessThan:type{_(:t,:t)<decides><transacts>:void},
        Equivalent:type{_(:t,:t)<decides><transacts>:void} where t:type
    )<transacts>:[]t =
        # Construct a min heap from the input array
        var NewHeapArr:MinHeap(t) = MakeMinHeap(ArrayIn, LessThan, Equivalent)
        var ReturnArray:[]t = array{}
        # Extract the minimum of the array until the array is empty
        for (Element : NewHeapArr.GetHeap()):
            if (HeapMinTuple := NewHeapArr.ExtractMin[]):
                set NewHeapArr = HeapMinTuple(0)
                set ReturnArray += array{HeapMinTuple(1)}
        ReturnArray