Python으로 작성한 Min-Heapify

파이썬으로 작성한 Max-Heapify의 코드다. 의사코드는 Introduction to Algorithms라는 MIT Press에서 나온 교재에서 참조했다.

#!/usr/bin/python
# -*- coding: UTF-8 -*-

def MinHeapify(A, i):
	i = i-1		# List start from 0

	if i == 0:
		l = 1
		r = 2
	else:
		l = (i*2)+1

	if len(A) > (i*2)+1: # If a node has left children
		if A[l] <= len(A) and A[l] < A[i]:
			smallest = l
		else:
			smallest = i
		
		if len(A) > (i*2)+2: # If a node has a right child
			r = (i*2)+2
			
			if A[r] <= len(A) and A[r] < A[smallest]:
				smallest = r

		if not smallest == i:
			A[i], A[smallest] = A[smallest], A[i]
			MinHeapify(A, (smallest+1)) # Because i = i-1

	return A

A = [27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0]

print MinHeapify(A, 1) # Let a heap start from 1