Heap Sort

class Solution:
    # @param A: Given an integer array
    # @return: void
    def heapify(self, A):
        for i in range(len(A) / 2 - 1, -1, -1):
            self.shiftdown(A, i)
        # write your code here
    def shiftdown(self, A, k):
        while k < len(A):
            smallest = k
            if 2 * k + 1 < len(A) and A[2 * k + 1] < A[smallest]:
                smallest = 2 * k + 1
            if 2 * k + 2 < len(A) and A[2 * k + 2] < A[smallest]:
                smallest = 2 * k + 2
            if smallest == k:
                break
            A[k], A[smallest] = A[smallest], A[k]
            k = smallest