Heap sort 힙정렬

힙 정렬은 기본적으로 힙 자료구조를 기반으로 한다.

 

간단히 힙 자료구조에 대해 알아보면

 

힙은 '최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조'이다.

최솟값 or 최댓값을 빠르게 찾아내는 것이 힙의 핵심이다.

min heap & max heap tree

위 사진은 heap tree를 시각화한 것이다. 하지만 트리의 인덱싱을 아는 사람이라면 위 사진이 무엇인가 이상해 보일 거다.

바로 형제 노드 간의 정렬은 되어있지 않다는 점이다. 이를 weak heap, 반정렬 상태 등등이라 부른다.

"아니 그러면 어떻게 정렬을 하나요?"

위에서 힙의 핵심은 최솟값 or 최대값을 빠르게 찾아내는 것이라 했다.

힙의 root node는 항상 우선순위가 1등이다. 즉 최소값 또는 최댓값이란 것이다.

이를 이용해 root node를 삭제하고 다시 heap tree 생성(heapify),

다시 heap tree가 정렬되면 root node를 삭제 이런 식으로 정렬이 진행된다.

 

그럼 우리가 알아봐야 할 것은 힙에서 root node를 삭제한 이후에 tree를 생성하는 부분일 것이다.

위 사진을 순서대로 설명하면

1. 가장 마지막 인덱스의 부모의 서브트리부터 검사한다.

2. 두 자식노드 중 더 큰 값과 swap 한다.

3. 만약 자식 노드와 swap 됐을 경우 swap전의 자식 노드의 서브 트리가 있다면 해당 서브트리도 검사한다.

4. 검사하는 인덱스에 -1 한다.

 

위는 초기 heapify 하는 방법이고, 이후 root node를 제거하며 실제로 정렬하는 방식은 아래와 같다.



root node와 말단 노드를 교환 후 root node의 서브트리를 검사하면 root node에는 최솟값 또는 최솟값이 올라갈 거고 이후 말단 노드의 제자리를 찾아가는 방식이다.

 

 

위를 파이썬 코드로 구현하면

def heap_sort(order):
    lastIdx = len(order)-1
    if lastIdx < 1:
        return 

    parentIdx = get_parent(lastIdx)


    for i in range(parentIdx,-1,-1):
        heapify(order, i, lastIdx)

    for i in range(lastIdx, 0, -1):
        order[i], order[0] = order[0], order[i]
        heapify(order, 0, i-1)

def get_parent(child):
    return (child - 1) // 2

def heapify(order, parentIdx, lastIdx):
    while parentIdx * 2 + 1 <= lastIdx:
        leftChildIdx = 2 * parentIdx + 1
        rightChildIdx = 2 * parentIdx + 2
        flag = parentIdx
        
        if order[parentIdx] < order[leftChildIdx]:
            flag = leftChildIdx
            
        if rightChildIdx <= lastIdx and order[flag] < order[rightChildIdx]:
            flag = rightChildIdx
            

        if flag != parentIdx:
            order[parentIdx], order[flag] = order[flag], order[parentIdx]
            parentIdx = flag
        else:
            return

data = [213,5,125,126,2,123,1231,1,9999]
heap_sort(data)
print(data)