#
# Copyright (c) 1999
#      Ali Onur Cinar &060;cinar&064;zdo.com&062;
#
# License:
#
#   Permission  to  use,  copy, modify, and  distribute  this software and its
#   documentation   for  educational   purposes  and  without  fee  is  hereby
#   granted,  provided  that the  above  copyright notice appear in all copies
#   and  that both  the  copyright  notice  and  this  permission  notice  and
#   warranty  disclaimer appear in supporting documentation, and that the name
#   of Ali Onur Cinar not be  used  in  advertising or publicity pertaining to
#   distribution of the software without specific, written prior permission.
#

	.data
size:	.word	11		# size(array) - 1
array:	.word	0,11,10,9,8,7,6,5,4,3,2,1

	.text
	.globl main

#
# @function: main
#	@parameters:	n/a
# 	@used_reg: 	$s0,$s1
#
main:
	sub	$sp,$sp,4	# save return address
	sw	$ra,0($sp)
	
	lw	$s0,size	# size of the array
	li	$s1,0		# init cursor
	
loop00:				# loop through each element
	add	$s1,$s1,1	# ++cursor
	bgt	$s1,$s0,end00	# cursor > size go to the end
	move 	$a0,$s1		# index -> $a0
	jal	itbuildheap	# call itbuildheap(index)	
	j	loop00		# loop again
	
end00:
	lw	$ra,0($sp)	# restore return address
	add	$sp,$sp,4
	jr	$ra		# return to kernel

itbuildheap:
	sub	$sp,$sp,36	# save $s and $ra 
	sw	$ra,0($sp)
	sw	$s0,4($sp)
	sw	$s1,8($sp)
	sw	$s2,12($sp)
	sw	$s3,16($sp)
	sw	$s4,20($sp)
	sw	$s5,24($sp)
	sw	$s6,28($sp)
	sw	$s7,32($sp)

	la	$s0,array	# get array's adr
	move	$s1,$a0		# get array's cursor
	
loop10:
	beq	$s1,1,end10	# cursor=1 go end10
	li	$t0,2		# t0 = 2
	div	$s1,$t0		# lo=cursor/2 hi=cursor%2
	mflo	$s2		# s2 = lo

	mul	$t0,$s1,4	# t0 = cursor * 1word	
	add	$t1,$s0,$t0	# t1 = array[cursor]
	mul	$t0,$s2,4	# t0 = cursor/2 * 1word
	add	$t2,$s0,$t0	# t2 = array[cursor/2]
	lw	$t3,($t1)	# t3 = (t1)
	lw	$t4,($t2)	# t4 = (t2)
		
	bge	$t3,$t4,end10	# t3 >= t4 go end10

	sw	$t4,($t1)	# array[cursor] = array[cursor/2]
	sw	$t3,($t2)	# array[cursor/2] = array[cursor]
	move	$s1,$s2		# cursor = cursor/2
	
	j	loop10

end10:
	lw	$ra,0($sp)	# restore registers
	lw	$s0,4($sp)
	lw	$s1,8($sp)
	lw	$s2,12($sp)
	lw	$s3,16($sp)
	lw	$s4,20($sp)
	lw	$s5,24($sp)
	lw	$s6,28($sp)
	lw	$s7,32($sp)
	add	$sp,$sp,36
	jr	$ra		# return back