[Algorithm] Heap Sort(힙 정렬)

Code

def create_heap(a):
    hsize=len(a)-1
    for i in reversed(range(1, hsize)):
        downheap(i, hsize)

def downheap(i, size):
    while(2*i<size):
        k=2*i
        if(k<size and a[k+1]>a[k]): k+=1
        if(a[i]>=a[k]): break
        a[i], a[k] = a[k], a[i]
        i=k

def heapsort(a):
    N=len(a)-1
    for i in range(N):
        a[1], a[N] = a[N], a[1]
        downheap(1,N-1)
        N-=1

a = [-1, 10, 4, 5, 1, 8, 6, 2, 7, 9, 3]
create_heap(a)
print(a)
heapsort(a)
print(a)

 

정리

이진 트리 사용

1. max heap 만들기

2. 첫번째 노드와 마지막 노드의 위치를 바꾸고 downheap

3. 마지막 노드의 위치는 위치를 바꾼 후 하나씩 줄어듦

2,3 반복

 

시간복잡도

O(nlogn)

 

특징

stable sort X

in-place sort