/*
 * C Program sorts the numbers in ascending order using heap sort (heap_sort.c)
 */
/*
#include <stdio.h>
#define MAXSIZE 1000

void heap_print(char *s, int heap[], int no) {
    printf("%s ", s);
    for (int i = 0; i < no; i++)
        printf("%d ", heap[i]);
    printf("\n");
}

void swap (int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heap_creation(int heap[], int size) {            // ref to the fig of heap creation
    int i, node, parent;                              // at this point, heap is just an array
    for (i = 1; i < size; i++) {                      // for each node in heap array
        node = i;                                     // current node
        do {                                          // the node find a position in the path going to root
            parent = (node - 1) / 2;                  // parent of the node
            if (heap[parent] < heap[node]) {          // create max heap
                swap(&heap[parent], &heap[node]);     // just like the bubble sort
            }                                         // the length of the path is at most log(n)
            node = parent;                            // go one layer up along  with the path
        } while (node > 0);                           // until its parent is the root
    }                                                 // therefore, it is a O(n*log(n)) algorithm
}

void heap_sort(int heap[], int size) {                // ref to the fig of heap sort
    int i, node, parent;                              // now, heap is a max heap
    for (i = size-1; i > 0; i--) {                    // downto, from rightmost position
        swap(&heap[0], &heap[i]);                     // put max in rightmost of (i+1)-node array
        parent = 0;                                   // re-arrange max heap, start from root to a leaf (path length <= log(n))
        do {                                          // except heap[0], all others form a max heap, going down to put heap[0]
            node = 2 * parent + 1;                    // node = left child of parent (may no child, needs confirm)
            if (node < i-1) {                         // node has a brother, the right child of parent
                if (heap[node] < heap[node+1]) {      // keys: left < right
                    node++;                           // node = right child of parent
                }                                     // i.e., select an elder brother
            }                                         // now, node has the max value, or an index that is out of bound
            if (node < i) {                           // the parent has a child (left or right, elder)
                if (heap[parent] < heap[node]) {      // re-arrange max heap
                    swap(&heap[parent], &heap[node]); // by swap
                }                                     // like an insertion sort
            }                                         // put heap[0] in a proper position
            parent = node;                            // go one layer down
        } while (node < i);                           // position i was already sorted
    }                                                 // the while goes one way from root to a leaf by checking brothers
}                                                     // this is also a O(n*log(n)) algorithm

int main() {
    int heap[MAXSIZE];
    int i, num;

    printf("enter the number of elements n = ");
    scanf("%d", &num);
    printf("enter %d elements one by one\n", num);
    for (i = 0; i < num; i++) {
        scanf("%d", &heap[i]);
    }                         heap_print("\nthe original array is", heap, num);
    heap_creation(heap, num); heap_print("the  created heap  is", heap, num);
    heap_sort(heap, num);     heap_print("the  sorted  array is", heap, num);
    return 0;
}
 */
.text
heap_print:
    addi  sp,sp,-48
    sw    ra,44(sp)
    sw    s0,40(sp)
    addi  s0,sp,48
    sw    a0,-36(s0)
    sw    a1,-40(s0)
    sw    a2,-44(s0)
    lw    a1,-36(s0)
    lui   a5,%hi(.LC0)
    addi  a0,a5,%lo(.LC0)
    call  printf
    sw    zero,-20(s0)
    j    .L2
.L3:
    lw    a5,-20(s0)
    slli  a5,a5,2
    lw    a4,-40(s0)
    add   a5,a4,a5
    lw    a5,0(a5)
    mv    a1,a5
    lui   a5,%hi(.LC1)
    addi  a0,a5,%lo(.LC1)
    call  printf
    lw    a5,-20(s0)
    addi  a5,a5,1
    sw    a5,-20(s0)
.L2:
    lw    a4,-20(s0)
    lw    a5,-44(s0)
    blt   a4,a5,.L3
    li    a0,10
    call  putchar
    nop
    lw    ra,44(sp)
    lw    s0,40(sp)
    addi  sp,sp,48
    jr    ra
swap:
    addi  sp,sp,-48
    sw    s0,44(sp)
    addi  s0,sp,48
    sw    a0,-36(s0)
    sw    a1,-40(s0)
    lw    a5,-36(s0)
    lw    a5,0(a5)
    sw    a5,-20(s0)
    lw    a5,-40(s0)
    lw    a4,0(a5)
    lw    a5,-36(s0)
    sw    a4,0(a5)
    lw    a5,-40(s0)
    lw    a4,-20(s0)
    sw    a4,0(a5)
    nop
    lw    s0,44(sp)
    addi  sp,sp,48
    jr    ra
heap_creation:
    addi  sp,sp,-48
    sw    ra,44(sp)
    sw    s0,40(sp)
    addi  s0,sp,48
    sw    a0,-36(s0)
    sw    a1,-40(s0)
    li    a5,1
    sw    a5,-20(s0)
    j    .L6
.L9:
    lw    a5,-20(s0)
    sw    a5,-24(s0)
.L8:
    lw    a5,-24(s0)
    addi  a5,a5,-1
    srli  a4,a5,31
    add   a5,a4,a5
    srai  a5,a5,1
    sw    a5,-28(s0)
    lw    a5,-28(s0)
    slli  a5,a5,2
    lw    a4,-36(s0)
    add   a5,a4,a5
    lw    a4,0(a5)
    lw    a5,-24(s0)
    slli  a5,a5,2
    lw    a3,-36(s0)
    add   a5,a3,a5
    lw    a5,0(a5)
    bge   a4,a5,.L7
    lw    a5,-28(s0)
    slli  a5,a5,2
    lw    a4,-36(s0)
    add   a3,a4,a5
    lw    a5,-24(s0)
    slli  a5,a5,2
    lw    a4,-36(s0)
    add   a5,a4,a5
    mv    a1,a5
    mv    a0,a3
    call  swap
.L7:
    lw    a5,-28(s0)
    sw    a5,-24(s0)
    lw    a5,-24(s0)
    bgtz  a5,.L8
    lw    a5,-20(s0)
    addi  a5,a5,1
    sw    a5,-20(s0)
.L6:
    lw    a4,-20(s0)
    lw    a5,-40(s0)
    blt   a4,a5,.L9
    nop
    lw    ra,44(sp)
    lw    s0,40(sp)
    addi  sp,sp,48
    jr    ra
heap_sort:
    addi  sp,sp,-48
    sw    ra,44(sp)
    sw    s0,40(sp)
    addi  s0,sp,48
    sw    a0,-36(s0)
    sw    a1,-40(s0)
    lw    a5,-40(s0)
    addi  a5,a5,-1
    sw    a5,-20(s0)
    j    .L11
.L15:
    lw    a5,-20(s0)
    slli  a5,a5,2
    lw    a4,-36(s0)
    add   a5,a4,a5
    mv    a1,a5
    lw    a0,-36(s0)
    call  swap
    sw    zero,-28(s0)
.L14:
    lw    a5,-28(s0)
    slli  a5,a5,1
    addi  a5,a5,1
    sw    a5,-24(s0)
    lw    a5,-20(s0)
    addi  a5,a5,-1
    lw    a4,-24(s0)
    bge   a4,a5,.L12
    lw    a5,-24(s0)
    slli  a5,a5,2
    lw    a4,-36(s0)
    add   a5,a4,a5
    lw    a4,0(a5)
    lw    a5,-24(s0)
    addi  a5,a5,1
    slli  a5,a5,2
    lw    a3,-36(s0)
    add   a5,a3,a5
    lw    a5,0(a5)
    bge   a4,a5,.L12
    lw    a5,-24(s0)
    addi  a5,a5,1
    sw    a5,-24(s0)
.L12:
    lw    a4,-24(s0)
    lw    a5,-20(s0)
    bge   a4,a5,.L13
    lw    a5,-28(s0)
    slli  a5,a5,2
    lw    a4,-36(s0)
    add   a5,a4,a5
    lw    a4,0(a5)
    lw    a5,-24(s0)
    slli  a5,a5,2
    lw    a3,-36(s0)
    add   a5,a3,a5
    lw    a5,0(a5)
    bge   a4,a5,.L13
    lw    a5,-28(s0)
    slli  a5,a5,2
    lw    a4,-36(s0)
    add   a3,a4,a5
    lw    a5,-24(s0)
    slli  a5,a5,2
    lw    a4,-36(s0)
    add   a5,a4,a5
    mv    a1,a5
    mv    a0,a3
    call  swap
.L13:
    lw    a5,-24(s0)
    sw    a5,-28(s0)
    lw    a4,-24(s0)
    lw    a5,-20(s0)
    blt   a4,a5,.L14
    lw    a5,-20(s0)
    addi  a5,a5,-1
    sw    a5,-20(s0)
.L11:
    lw    a5,-20(s0)
    bgtz  a5,.L15
    nop
    lw    ra,44(sp)
    lw    s0,40(sp)
    addi  sp,sp,48
    jr    ra
main:
    addi  sp,sp,-2032
    sw    ra,2028(sp)
    sw    s0,2024(sp)
    addi  s0,sp,2032
    addi  sp,sp,-2000
    lui   a5,%hi(.LC2)
    addi  a0,a5,%lo(.LC2)
    call  printf
    li    a5,-4096
    addi  a5,a5,88
    addi  a4,s0,-16
    add   a5,a4,a5
    mv    a1,a5
    lui   a5,%hi(.LC3)
    addi  a0,a5,%lo(.LC3)
    call  scanf
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a5,88(a5)
    mv    a1,a5
    lui   a5,%hi(.LC4)
    addi  a0,a5,%lo(.LC4)
    call  printf
    sw    zero,-20(s0)
    j    .L17
.L18:
    li    a5,-4096
    addi  a5,a5,92
    addi  a4,s0,-16
    add   a4,a4,a5
    lw    a5,-20(s0)
    slli  a5,a5,2
    add   a5,a4,a5
    mv    a1,a5
    lui   a5,%hi(.LC3)
    addi  a0,a5,%lo(.LC3)
    call  scanf
    lw    a5,-20(s0)
    addi  a5,a5,1
    sw    a5,-20(s0)
.L17:
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a5,88(a5)
    lw    a4,-20(s0)
    blt   a4,a5,.L18
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a4,88(a5)
    li    a5,-4096
    addi  a5,a5,92
    addi  a3,s0,-16
    add   a5,a3,a5
    mv    a2,a4
    mv    a1,a5
    lui   a5,%hi(.LC5)
    addi  a0,a5,%lo(.LC5)
    call  heap_print
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a4,88(a5)
    li    a5,-4096
    addi  a5,a5,92
    addi  a3,s0,-16
    add   a5,a3,a5
    mv    a1,a4
    mv    a0,a5
    call  heap_creation
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a4,88(a5)
    li    a5,-4096
    addi  a5,a5,92
    addi  a3,s0,-16
    add   a5,a3,a5
    mv    a2,a4
    mv    a1,a5
    lui   a5,%hi(.LC6)
    addi  a0,a5,%lo(.LC6)
    call  heap_print
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a4,88(a5)
    li    a5,-4096
    addi  a5,a5,92
    addi  a3,s0,-16
    add   a5,a3,a5
    mv    a1,a4
    mv    a0,a5
    call  heap_sort
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a4,88(a5)
    li    a5,-4096
    addi  a5,a5,92
    addi  a3,s0,-16
    add   a5,a3,a5
    mv    a2,a4
    mv    a1,a5
    lui   a5,%hi(.LC7)
    addi  a0,a5,%lo(.LC7)
    call  heap_print
    li    a5,0
    mv    a0,a5
    addi  sp,sp,2000
    lw    ra,2028(sp)
    lw    s0,2024(sp)
    addi  sp,sp,2032
    jr    ra
.data
.LC0: .string "%s "
.LC1: .string "%d "
.LC2: .string "enter the number of elements n = "
.LC3: .string "%d"
.LC4: .string "enter %d elements one by one\n"
.LC5: .string "\nthe original array is"
.LC6: .string "the  created heap  is"
.LC7: .string "the  sorted  array is"
.end