Heap Sort

Heap이란 완전 Binary트리를 형성하는 자료구조의 일종입니다.

teus-kiwiee.tistory.com/29

Heap

이때, Heap의 형성 후 Top Node의 값이 Max Or Min 값을 갖게 됩니다.

 

이때 Top Node의 값을 활용해서 Data를 정렬하는 방법을 Heap Sort 알고리즘 이라고합니다.

알고리즘은

1. Random Array에 Max heap 형성

2. 0번 Node의 값 추출

3. 마지막 Node의 값을 0번 Node로 이동

4. Heap 재구축(이때 자식 Node중 값이 큰쪽으로만 진행)

5. Heap에 원소가 없을때까지 2~4반복

 

Heap 정렬은 n번의 Heap의 생성이 각 n, (n-1), (n-2)..... ,1개의 원소를 가진 Array에서 발생합니다.

 

따라서 최초 Heap 생성 과정에서 n번의 비교, 이후 Heap 재정렬 과정에서 logn의 시간복잡도가 발생하여

 

최종적으로 O(nlogn)의 시간복잡도를 갖는 알고리즘이 되겠습니다.

#Heap 정렬이 완료된 Heap을 Input으로 받습니다.
#해당 알고리즘의 Input은 Max Heap을 받았습니다.
def heap_sort(DT_list):    
    Max = len(DT_list)    
    n=0
    #check depth of heap
    #변수 n에 Heap의 Max Depth를 저장합니다.
    while True:
        Max = Max-pow(2,n)
        if Max<=0:
            break
        n = n+1    
    element_num = len(DT_list)         
    #변수 fin_result에 정렬된 Element를 순서대로 저장합니다.
    fin_result = []          
    i = 0
    while True:                               
        #Heap의 성분이 없으면 알고리즘 종료
        if element_num ==0:            
            break
        #비교할 자식 Node가 없을 경우 Max Heap이 다시 완성된 것을 의미합니다.
        if ((2*i+2 >= len(DT_list))):            
            #마지막 Leaf Node와 값을 교환 후
            temp = DT_list[0]
            DT_list[0] = DT_list[-1]
            DT_list[-1] = temp
            #Top Node(Heap의 Max값)정렬 List에 넣어줍니다.
            fin_result.append(DT_list.pop())
            element_num = element_num-1
            i=0
        #왼쪽으로 이동하여 자식Node와 값을 비교후, 부모노드(Max값과 Swap된 마지막 Leaf Node값)
        #가 자식Node보다 작을 경우, Swap을 진행합니다.
        elif (DT_list[2*i+1] < DT_list[2*i+2]) and DT_list[i]<DT_list[2*i+2]:            
            temp = DT_list[i]
            DT_list[i] = DT_list[2*i+2]
            DT_list[2*i+2] = temp
            i = 2*i +2
        #오른쪽에서 동일한 과정을 진행합니다.
        elif (DT_list[2*i+1] >= DT_list[2*i+2]) and DT_list[i]<DT_list[2*i+1]:
            temp = DT_list[i]                
            DT_list[i] = DT_list[2*i+1]
            DT_list[2*i+1] = temp
            i = 2*i +1           
        else:
            temp = DT_list[0]
            DT_list[0] = DT_list[-1]
            DT_list[-1] = temp
            fin_result.append(DT_list.pop())
            element_num = element_num-1
            i=0            
    return fin_result

heap_sort(Data)