/*
 * 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) {
    int i;
    printf("%s ", s);
    for (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:
	addiu	$sp,$sp,-32
	sw	$31,28($sp)
	sw	$fp,24($sp)
	move	$fp,$sp
	sw	$4,32($fp)
	sw	$5,36($fp)
	sw	$6,40($fp)
	lui	$2,%hi($LC0)
	addiu	$4,$2,%lo($LC0)
	lw	$5,32($fp)
	jal	printf
	nop
	sw	$0,16($fp)
	j	$L2
	nop
$L3:
	lw	$2,16($fp)
	nop
	sll	$2,$2,2
	lw	$3,36($fp)
	nop
	addu	$2,$3,$2
	lw	$3,0($2)
	lui	$2,%hi($LC1)
	addiu	$4,$2,%lo($LC1)
	move	$5,$3
	jal	printf
	nop
	lw	$2,16($fp)
	nop
	addiu	$2,$2,1
	sw	$2,16($fp)
$L2:
	lw	$3,16($fp)
	lw	$2,40($fp)
	nop
	slt	$2,$3,$2
	bne	$2,$0,$L3
	nop
	li	$4,10
	jal	putchar
	nop
	move	$sp,$fp
	lw	$31,28($sp)
	lw	$fp,24($sp)
	addiu	$sp,$sp,32
	j	$31
	nop
swap:
	addiu	$sp,$sp,-16
	sw	$fp,12($sp)
	move	$fp,$sp
	sw	$4,16($fp)
	sw	$5,20($fp)
	lw	$2,16($fp)
	nop
	lw	$2,0($2)
	nop
	sw	$2,0($fp)
	lw	$2,20($fp)
	nop
	lw	$3,0($2)
	lw	$2,16($fp)
	nop
	sw	$3,0($2)
	lw	$2,20($fp)
	lw	$3,0($fp)
	nop
	sw	$3,0($2)
	move	$sp,$fp
	lw	$fp,12($sp)
	addiu	$sp,$sp,16
	j	$31
	nop
heap_creation:
	addiu	$sp,$sp,-40
	sw	$31,36($sp)
	sw	$fp,32($sp)
	move	$fp,$sp
	sw	$4,40($fp)
	sw	$5,44($fp)
	li	$2,1
	sw	$2,16($fp)
	j	$L6
	nop
$L9:
	lw	$2,16($fp)
	nop
	sw	$2,20($fp)
$L8:
	lw	$2,20($fp)
	nop
	addiu	$2,$2,-1
	srl	$3,$2,31
	addu	$2,$3,$2
	sra	$2,$2,1
	sw	$2,24($fp)
	lw	$2,24($fp)
	nop
	sll	$2,$2,2
	lw	$3,40($fp)
	nop
	addu	$2,$3,$2
	lw	$3,0($2)
	lw	$2,20($fp)
	nop
	sll	$2,$2,2
	lw	$4,40($fp)
	nop
	addu	$2,$4,$2
	lw	$2,0($2)
	nop
	slt	$2,$3,$2
	beq	$2,$0,$L7
	nop
	lw	$2,24($fp)
	nop
	sll	$2,$2,2
	lw	$3,40($fp)
	nop
	addu	$4,$3,$2
	lw	$2,20($fp)
	nop
	sll	$2,$2,2
	lw	$3,40($fp)
	nop
	addu	$2,$3,$2
	move	$5,$2
	jal	swap
	nop
$L7:
	lw	$2,24($fp)
	nop
	sw	$2,20($fp)
	lw	$2,20($fp)
	nop
	bgtz	$2,$L8
	nop
	lw	$2,16($fp)
	nop
	addiu	$2,$2,1
	sw	$2,16($fp)
$L6:
	lw	$3,16($fp)
	lw	$2,44($fp)
	nop
	slt	$2,$3,$2
	bne	$2,$0,$L9
	nop
	move	$sp,$fp
	lw	$31,36($sp)
	lw	$fp,32($sp)
	addiu	$sp,$sp,40
	j	$31
	nop
heap_sort:
	addiu	$sp,$sp,-40
	sw	$31,36($sp)
	sw	$fp,32($sp)
	move	$fp,$sp
	sw	$4,40($fp)
	sw	$5,44($fp)
	lw	$2,44($fp)
	nop
	addiu	$2,$2,-1
	sw	$2,16($fp)
	j	$L11
	nop
$L15:
	lw	$2,16($fp)
	nop
	sll	$2,$2,2
	lw	$3,40($fp)
	nop
	addu	$2,$3,$2
	lw	$4,40($fp)
	move	$5,$2
	jal	swap
	nop
	sw	$0,24($fp)
$L14:
	lw	$2,24($fp)
	nop
	sll	$2,$2,1
	addiu	$2,$2,1
	sw	$2,20($fp)
	lw	$2,16($fp)
	nop
	addiu	$3,$2,-1
	lw	$2,20($fp)
	nop
	slt	$2,$2,$3
	beq	$2,$0,$L12
	nop
	lw	$2,20($fp)
	nop
	sll	$2,$2,2
	lw	$3,40($fp)
	nop
	addu	$2,$3,$2
	lw	$3,0($2)
	lw	$2,20($fp)
	nop
	addiu	$2,$2,1
	sll	$2,$2,2
	lw	$4,40($fp)
	nop
	addu	$2,$4,$2
	lw	$2,0($2)
	nop
	slt	$2,$3,$2
	beq	$2,$0,$L12
	nop
	lw	$2,20($fp)
	nop
	addiu	$2,$2,1
	sw	$2,20($fp)
$L12:
	lw	$3,20($fp)
	lw	$2,16($fp)
	nop
	slt	$2,$3,$2
	beq	$2,$0,$L13
	nop
	lw	$2,24($fp)
	nop
	sll	$2,$2,2
	lw	$3,40($fp)
	nop
	addu	$2,$3,$2
	lw	$3,0($2)
	lw	$2,20($fp)
	nop
	sll	$2,$2,2
	lw	$4,40($fp)
	nop
	addu	$2,$4,$2
	lw	$2,0($2)
	nop
	slt	$2,$3,$2
	beq	$2,$0,$L13
	nop
	lw	$2,24($fp)
	nop
	sll	$2,$2,2
	lw	$3,40($fp)
	nop
	addu	$4,$3,$2
	lw	$2,20($fp)
	nop
	sll	$2,$2,2
	lw	$3,40($fp)
	nop
	addu	$2,$3,$2
	move	$5,$2
	jal	swap
	nop
$L13:
	lw	$2,20($fp)
	nop
	sw	$2,24($fp)
	lw	$3,20($fp)
	lw	$2,16($fp)
	nop
	slt	$2,$3,$2
	bne	$2,$0,$L14
	nop
	lw	$2,16($fp)
	nop
	addiu	$2,$2,-1
	sw	$2,16($fp)
$L11:
	lw	$2,16($fp)
	nop
	bgtz	$2,$L15
	nop
	move	$sp,$fp
	lw	$31,36($sp)
	lw	$fp,32($sp)
	addiu	$sp,$sp,40
	j	$31
	nop
main:
	addiu	$sp,$sp,-4032
	sw	$31,4028($sp)
	sw	$fp,4024($sp)
	move	$fp,$sp
	lui	$2,%hi($LC2)
	addiu	$4,$2,%lo($LC2)
	jal	printf
	nop
	addiu	$3,$fp,4020
	lui	$2,%hi($LC3)
	addiu	$4,$2,%lo($LC3)
	move	$5,$3
	jal	scanf
	nop
	lw	$3,4020($fp)
	lui	$2,%hi($LC4)
	addiu	$4,$2,%lo($LC4)
	move	$5,$3
	jal	printf
	nop
	sw	$0,16($fp)
	j	$L17
	nop
$L18:
	addiu	$3,$fp,20
	lw	$2,16($fp)
	nop
	sll	$2,$2,2
	addu	$3,$3,$2
	lui	$2,%hi($LC3)
	addiu	$4,$2,%lo($LC3)
	move	$5,$3
	jal	scanf
	nop
	lw	$2,16($fp)
	nop
	addiu	$2,$2,1
	sw	$2,16($fp)
$L17:
	lw	$2,4020($fp)
	lw	$3,16($fp)
	nop
	slt	$2,$3,$2
	bne	$2,$0,$L18
	nop
	lw	$3,4020($fp)
	addiu	$5,$fp,20
	lui	$2,%hi($LC5)
	addiu	$4,$2,%lo($LC5)
	move	$6,$3
	jal	heap_print
	nop
	lw	$2,4020($fp)
	addiu	$3,$fp,20
	move	$4,$3
	move	$5,$2
	jal	heap_creation
	nop
	lw	$3,4020($fp)
	addiu	$5,$fp,20
	lui	$2,%hi($LC6)
	addiu	$4,$2,%lo($LC6)
	move	$6,$3
	jal	heap_print
	nop
	lw	$2,4020($fp)
	addiu	$3,$fp,20
	move	$4,$3
	move	$5,$2
	jal	heap_sort
	nop
	lw	$3,4020($fp)
	addiu	$5,$fp,20
	lui	$2,%hi($LC7)
	addiu	$4,$2,%lo($LC7)
	move	$6,$3
	jal	heap_print
	nop
	move	$2,$0
	move	$sp,$fp
	lw	$31,4028($sp)
	lw	$fp,4024($sp)
	addiu	$sp,$sp,4032
	j	$31
	nop
.data
$LC0:	.ascii	"%s \000"
$LC1:	.ascii	"%d \000"
$LC2:	.ascii	"enter the number of elements n = \000"
$LC3:	.ascii	"%d\000"
$LC4:	.ascii	"enter %d elements one by one\012\000"
$LC5:	.ascii	"\012the original array is\000"
$LC6:	.ascii	"the  created heap  is\000"
$LC7:	.ascii	"the  sorted  array is\000"
.end