#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL arr(100) AS LONG
    LOCAL n AS LONG
    LOCAL i AS LONG
    LOCAL j AS LONG
    LOCAL parent AS LONG
    LOCAL child AS LONG
    LOCAL temp_val AS LONG
    LOCAL temp_str AS STRING
    LOCAL heap_end AS LONG
    LOCAL largest AS LONG

    ' Heap sort with max-heapify

    n = 15
    arr(0) = 4
    arr(1) = 10
    arr(2) = 3
    arr(3) = 5
    arr(4) = 1
    arr(5) = 8
    arr(6) = 7
    arr(7) = 2
    arr(8) = 9
    arr(9) = 6
    arr(10) = 12
    arr(11) = 15
    arr(12) = 11
    arr(13) = 14
    arr(14) = 13

    PRINT "Heap Sort"
    PRINT "========="
    PRINT ""

    temp_str = ""
    i = 0
    WHILE i < n
        temp_str = temp_str + STR$(arr(i))
        IF i < n - 1 THEN temp_str = temp_str + " "
        i = i + 1
    WEND
    PRINT "Before: " + temp_str

    ' Build max heap (bottom-up)
    i = n / 2 - 1
    WHILE i >= 0
        ' Sift down
        parent = i
        WHILE parent * 2 + 1 < n
            child = parent * 2 + 1
            IF child + 1 < n AND arr(child + 1) > arr(child) THEN
                child = child + 1
            END IF
            IF arr(parent) < arr(child) THEN
                temp_val = arr(parent)
                arr(parent) = arr(child)
                arr(child) = temp_val
                parent = child
            ELSE
                parent = n
            END IF
        WEND
        i = i - 1
    WEND

    heap_end = n - 1
    WHILE heap_end > 0
        temp_val = arr(0)
        arr(0) = arr(heap_end)
        arr(heap_end) = temp_val
        heap_end = heap_end - 1

        parent = 0
        WHILE parent * 2 + 1 <= heap_end
            child = parent * 2 + 1
            IF child + 1 <= heap_end AND arr(child + 1) > arr(child) THEN
                child = child + 1
            END IF
            IF arr(parent) < arr(child) THEN
                temp_val = arr(parent)
                arr(parent) = arr(child)
                arr(child) = temp_val
                parent = child
            ELSE
                parent = heap_end
            END IF
        WEND
    WEND

    temp_str = ""
    i = 0
    WHILE i < n
        temp_str = temp_str + STR$(arr(i))
        IF i < n - 1 THEN temp_str = temp_str + " "
        i = i + 1
    WEND
    PRINT "After:  " + temp_str

    ' Verify
    i = 0
    j = 1
    WHILE i < n - 1
        IF arr(i) > arr(i + 1) THEN
            j = 0
        END IF
        i = i + 1
    WEND
    IF j = 1 THEN
        PRINT "Sorted correctly"
    ELSE
        PRINT "NOT sorted"
    END IF

    ' Test with larger set
    n = 20
    arr(0) = 99
    arr(1) = 23
    arr(2) = 45
    arr(3) = 67
    arr(4) = 12
    arr(5) = 34
    arr(6) = 56
    arr(7) = 78
    arr(8) = 89
    arr(9) = 11
    arr(10) = 43
    arr(11) = 65
    arr(12) = 87
    arr(13) = 98
    arr(14) = 21
    arr(15) = 32
    arr(16) = 54
    arr(17) = 76
    arr(18) = 88
    arr(19) = 90

    PRINT ""
    PRINT "Set 2 (20 elements):"

    i = n / 2 - 1
    WHILE i >= 0
        parent = i
        WHILE parent * 2 + 1 < n
            child = parent * 2 + 1
            IF child + 1 < n AND arr(child + 1) > arr(child) THEN
                child = child + 1
            END IF
            IF arr(parent) < arr(child) THEN
                temp_val = arr(parent)
                arr(parent) = arr(child)
                arr(child) = temp_val
                parent = child
            ELSE
                parent = n
            END IF
        WEND
        i = i - 1
    WEND

    heap_end = n - 1
    WHILE heap_end > 0
        temp_val = arr(0)
        arr(0) = arr(heap_end)
        arr(heap_end) = temp_val
        heap_end = heap_end - 1

        parent = 0
        WHILE parent * 2 + 1 <= heap_end
            child = parent * 2 + 1
            IF child + 1 <= heap_end AND arr(child + 1) > arr(child) THEN
                child = child + 1
            END IF
            IF arr(parent) < arr(child) THEN
                temp_val = arr(parent)
                arr(parent) = arr(child)
                arr(child) = temp_val
                parent = child
            ELSE
                parent = heap_end
            END IF
        WEND
    WEND

    temp_str = ""
    i = 0
    WHILE i < n
        temp_str = temp_str + STR$(arr(i))
        IF i < n - 1 THEN temp_str = temp_str + " "
        i = i + 1
    WEND
    PRINT "After:  " + temp_str

    PRINT ""
    PRINT "Heap sort complete."

    FUNCTION = 0
END FUNCTION
