[Algorithm] Heap 정렬 구현(python)

#Heap sort

heap = []
number = 0

def heapify(i):


    global number
    global heap

    #왼쪽 자식 노드
    c = 2 * i + 1


    #우측 노드가 왼쪽보다 클때 포인터 옴김
    if c < number and c+1<number:
        if heap[c]<heap[c+1]:
            c+=1
        # 부모보다 자식 노드가 클 경우
        if heap[i]<heap[c]:
            temp = heap[i]
            heap[i] = heap[c]
            heap[c] = temp

    # number /2 까지만 수행
    if c <= number//2:
        heapify(c)

def main():

    global number
    global heap

    number = int(input())
    heap = list(map(int,input().split()))


    #힙생성(하향식)
    for i in range(number//2,-1,-1):
        heapify(i)
    #print(heap)

    #힙정렬
    for i in range(number-1,-1,-1):

        for j in range(number):   #정렬 과정 출력
            print(heap[j],end = ' ')
        print()

        temp = heap[0]
        heap[0] = heap[i]
        heap[i] = temp

        root = 0
        c = 1

        # 최대 노드를 리스트의 맨뒤로 보내 바꿔치기하고 root 노드의 원소를 정렬을 통해 내림차순 구현
        while c < i:

            c = 2*root + 1
            #자식중 더 큰 값 찾기
            if(c<i-1 and heap[c]<heap[c+1]):
                c+=1

            # 루트보다 자식이 크면 교환
            if(c<i and heap[root]<heap[c]):

                temp = heap[root]
                heap[root] = heap[c]
                heap[c] = temp

            root = c

main()

---

[입력]

10
26 5 37 1 61 11 59 15 48 19

 

[출력]

# 각 노드별로 heapify를 통해 최대힙 구현(상향식)  
61 48 59 26 5 11 37 15 1 19

 

#루트 노드를 리스트의 맨뒤 노드와 바꿔치기하고 root 노드의 원소를 정렬을 통해 내림차순 구현

#맨 뒤 노드를 제외한 나머지 노드들을 동일한 방법으로 반복하여 준다.
59 48 37 26 5 11 19 15 1 61 
48 26 37 15 5 11 19 1 59 61 
37 26 19 15 5 11 1 48 59 61 
26 15 19 1 5 11 37 48 59 61 
19 15 11 1 5 26 37 48 59 61 
15 5 11 1 19 26 37 48 59 61 
11 5 1 15 19 26 37 48 59 61 
5 1 11 15 19 26 37 48 59 61 
1 5 11 15 19 26 37 48 59 61