heapify.py

# -*- coding: utf-8 -*-

class Solution:
    # @param A: Given an integer array
    # @return: void
    def heapify(self, A):
        # write your code here
        '''
        为什么从1/2的位置从后往前遍历？
        因为对于堆中下标为i的元素，子节点下标为i * 2 + 1和i * 2 + 2，
        对于下标大于1/2位置的元素一定是叶子节点，无须做向下调整。
        '''
        for i in xrange((len(A) - 1) / 2, -1, -1):
            while i < len(A):
                left, right = i * 2 + 1, i * 2 + 2
                min_pos = i
                if (left < len(A)) and (A[left] < A[min_pos]):
                    min_pos = left
                if (right < len(A)) and (A[right] < A[min_pos]):
                    min_pos = right
                if min_pos != i:    # 调整A[i]元素位置，继续向下调整。
                    A[i], A[min_pos] = A[min_pos], A[i]
                    i = min_pos
                else:   # min_pos没变，A[i]无须调整，结束循环。
                    break