MIT - Introduction to Algorithms - Lecture 4 Heap Sort 만들어보기

MIT - Introduction to Algorithms 

- Lecture 4 Heap Sort 만들어보기

Heap Sort는 4강 pdf를 기준으로 만들어 보았습니다.
아래 URL pdf를 참조하길 바랍니다.

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-notes/

code, data, note pdf  : https://courses.csail.mit.edu/6.006/fall11/notes.shtml

a = [4,1,3,2,16,9,10,14,8,7]

def max_heapify(A,i):
    l = 2*i+1
    r = 2*(i+1)    
    if l< len(A) and A[l]>A[i]:
        largest = l
    else:
        largest = i
    if rA[largest]:
        largest = r
    if largest != i:
        tmp = A[i]
        A[i] = A[largest]
        A[largest] = tmp    
        max_heapify(A,largest)
        
    return A

def build_max_heap(A):
    for i in range(len(A)//2-1,-1,-1):
        max_heapify(A,i)
    return A

b=a.copy()
print('init : ',b)
def heap_sort(A):
    import time
    start = time.time()
    li = []
    for i in range(len(A)):
        build_max_heap(A)
        max_ = A[0]
        A[0] = A[len(A)-1]
        A[len(A)-1] = max_
        li.append(A.pop())
    end = time.time()
    print('%.10f sec' %(end-start))
    return li
print(heap_sort(b))