Sorting(5) Heap Sort(힙 정렬 - min Heap)

파이썬 Heap Sort로 오름차순으로 정렬하는 방식입니다.

시간복잡도 : O(nlogn)

def heapify(A, n, k):

    while 2*k+1 < n:

        L = 2*k+1

        R = 2*k+2

        if A[k] < A[L]:

            m = L

        else:

            m = k

        if R < n and A[m] < A[R]:

            m = R

            

        if k != m:

            A[k], A[m] = A[m], A[k]

            k = m

        else:

            break

def make_heap(A):

    for k in range(len(A)/2, -1, -1):

        heapify(A, len(A), k)

def heapSort(A):

    make_heap(A)

    n = len(A)

    

    for k in range(n-1):

        A[0], A[n-1] = A[n-1], A[0]

        n -= 1

        heapify(A, n, 0)

if __name__ == '__main__':

    A = [3, 10, 7, 9, 8, 5, 12, 21, 4, 15]

    heapSort(A)

    print A