힙 정렬을 구현해보자

일단 이거 어제 부트캠프에서 한거고 깃헙에는 코드가 올라가있음. 근데 왜 글은 오늘 올리느냐...

 

두 가지 이유가 있는데 일단 요즘 레전자 DLC 미느냐고 바쁘고, 미디움은 하루에 글 세개인가 제한이 있습니다… 목욜에 제한 넘겨서 하나 금욜에 올렸는데 이것도 금욜에 올렸다간 제때 못올라감…

---

힙 정렬을 하기 위해서는 힙 트리에 대해 먼저 알아야 하는데, 이거는 트리는 트리인데 일단 완전 이진 트리(자식이 최대 두 개인 트리)이다. 그리고 항상 루트에 최댓값(최대 힙) 혹은 최솟값(최소 힙)이 들어가있어서 최댓값 찾기는 개빨리끝남.

 

여기서는 어떻게 구현했냐면

1. 트리 뼈대를 만든 다음(리스트를 주면 리스트 길이에 따라서 완전 이진 트리가 생성됨)

2. 그 트리 안에 있는 리스트를 힙 트리로 만들건데(최대 힙), 이건 되게 간단하다. 부모 노드랑 자식 노드를 비교해서 더 큰 값이 계속해서 위로 올라가기만 하면 된다.

3. 그리고 가장 중요한 과정! 루트로 올라온 최댓값과 트리의 가장 오른쪽 아래에 있는 잎을 바꾼 다음 잎을 뗄 거다.

4. 2~3을 반복

 

2번하고 3번이 키포인트가 되어서 힙 정렬은 일단 개같이 빠른 속도를 자랑하지만 구현하는 것도 어렵고 코드도 보자마자 뇌 커널패닉 올 정도로 아스트랄하다. 그런데 왜 루트에 있는 걸 잎이랑 바꾸나요? 일단 뿌리 없는 나무는 근본 없는 나무… 루트는 트리의 근간이라 함부로 삭제할 수 없다. 쌉고수 분들은 잘 아시겠지만, 혹시나 개초보라면 대충 이렇게만 이해해두십셔. 그리고 루트랑 잎을 바꿔서 작은 값이 올라오면 또 다음 단계에서 최대 힙을 구성하면서 값들이 섞이게 돼서 끊임없이 올라오게 된다. 힙 정렬의 근간은 트리를 유지하면서 끊임없이 뒤섞어서 최댓값/최솟값을 끌어올려 힙을 만드는 것이다.

---

이진 트리 만들기

# 데이터를 이진 트리화하는 함수
def binary_tree(data):
    # 부모 노드의 개수. 데이터 / 2다. 
    number_of_parent = len(data) // 2 # 소수점따원 필요없다네
    # 완전 이진 트리이기때문에 무조건 자식은 두 개다. 
    # 딕셔너리에는 값의 '순서'를 담는다. ㅇㅋ? ㅇㅇㅋ 
    tree_node = {}
    child_node_idx = 1 # 자식 노드는 1부터 시작 (0은 루트)
    child_node_last = len(data) - 1 # 루트 빼면 전체 길이에서 하나 빠짐
    for i in range(number_of_parent):
        # 자 생성 드가자
        tree_node[i] = []
        # 자식은 최대가 두개(사유: 완전 이진 트리)
        for _ in range(2):
            tree_node[i].append(child_node_idx)
            child_node_idx += 1
            if child_node_idx > child_node_last:
                break
    return tree_node

아 혹시 보자마자 커널패닉이 오셨나요? 당신이 코딩 쌉고수가 아닌 이상 지극히 정상이다. 내가 위에서 힙 트리는 완전 이진 트리라고 했죠? 그래서 최대 자식이 두 개인거다. 그럼 왜 딕셔너리로 만든건가요?

 

딕셔너리의 키값이 부모 노드고, 밸류가 자식 노드(리스트)다. 그래서 키값을 호출하면 자식이 나오게 되는 구조인데, 일단 저기에 들어가는 건 리스트에 들어있는 실제 값이 아니라 리스트 길이에 따른 인덱스... 그니까 주소다. 그래서 길이가 15인 리스트를 넣으면 0부터 14까지 나오게 된다.

 

number_of_parent = len(data) // 2 # 소수점따원 필요없다네

그림을 잘 보면 유자식, 무자식 따로 표시가 되어있는 걸 볼 수 있는데, 이게 무슨 소리냐... 여러분들 솔직히 힙 정렬이 힙 트리 만들고 위아래 바꿔서 빼는걸 반복한다고 했을 때 무슨 생각 하셨어요? 그죠. 이걸 계속 반복하는데 이게 빠르다고? 라고 생각하셨을 분들도 계실 것이다. 근데 트리에서 저 노드들을 다 보는 게 아니라 자식이 있는 노드들만 본다. 자식이 있는 노드들을 확인해서 부모랑 비교하고 힙을 구축하는거지, 번거롭게 전체를 다 보지 않는다. 그리고 자식이 있는 부모 노드의 개수는 리스트 길이를 2로 나눈 정수값(소수점 버림)이다.

 

힙 정렬 하기

# 정렬 이즈 히얼 
def heap_sort(data):
    # 정렬 결과
    result_list = []

    # 우리 이거 뻉이쳐야돼요
    while len(data) > 0:
        # 순순히 트리를 넘긴다면 유혈사태는 일어나지 않을 것입니다. 
        tree = binary_tree(data)
        # 키
        keys = tree.keys()
        # 이름내놔
        key_list = list(keys)
        key_list.sort(reverse=True)
        # 본론 드가자...
        for parent in key_list:
            # 자식의 위치
            child_position = tree[parent]
            # 자식의 개수만큼 반복한다 
            for idx in child_position:
                # 부모의 값이 자식의 값보다 작은가?
                if data[parent] < data[idx]:
                    # 작으면 바꿔
                    data[parent], data[idx] = data[idx], data[parent]

        # 제일 큰 값(루트)과 잎을 바꿉니다. 
        data[0], data[-1] = data[-1], data[0]
        # 결과 리스트에 담는다. 
        max_list = data.pop()
        result_list.append(max_list)
    
    # 다 됐음? 
    result_list.reverse()
    data.extend(result_list)
# 위 방식은 최대 힙입니다. (최소 힙으로 쓰려면 부등호 반대로 달아야됨)

여기서 2차 패닉 오신 분들은 일단 진정하시고 심호흡 한번 하십쇼. 이 코드가 트리 뼈대를 기반으로 트리를 만들고, 힙 정렬을 진행하는 코드다.

 

# 순순히 트리를 넘긴다면 유혈사태는 일어나지 않을 것입니다. 
tree = binary_tree(data)
# 키
keys = tree.keys()
# 이름내놔
key_list = list(keys)
key_list.sort(reverse=True)

우리 그 위에서 짰던 트리 뼈대 만드는 함수 있죠? 그걸로 리스트 입력받아서 트리를 만드는거다. 그리고 키(부모 노드)를 입력받은 다음 뒤집는 건 트리를 루트부터가 아니라 밑에서부터 보기 위해서다. 위에서 설명했던 힙 만드는 과정이 밑에서부터 진행된다는 것.

 

# 본론 드가자...
for parent in key_list:
    # 자식의 위치
    child_position = tree[parent]
    # 자식의 개수만큼 반복한다 
    for idx in child_position:
        # 부모의 값이 자식의 값보다 작은가?
        if data[parent] < data[idx]:
            # 작으면 바꿔
            data[parent], data[idx] = data[idx], data[parent]

# 제일 큰 값(루트)과 잎을 바꿉니다. 
data[0], data[-1] = data[-1], data[0]
# 결과 리스트에 담는다. 
max_list = data.pop()
result_list.append(max_list)

여기가 본론이다. 루트부터 시작해서 왼쪽->오른쪽 순서로 채워나간 다음, 밑에서부터 부모보다 큰 자식(둘 다 크면 둘중 더 큰 값을 올림)을 올리고 올리고 올려서 최대 힙을 만든다. 그리고 힙을 다 만든 다음 루트와 오른쪽 아래 잎을 바꿔주고, 그 잎을 뺀다. 그걸 반복문 돌리면 되는거다. 쉽죠?

 

# 다 됐음? 
result_list.reverse()
data.extend(result_list)

그럼 이걸 왜 뒤집었는지에 대한 설명을 해주겠음… 쟤가 최대 힙이라 저대로 정렬하게 되면 내림차순 정렬이 된다. 왜죠? 큰 값이 첫빠따로 들어가잖아요. 그래서 오름차순으로 정렬하려면 최소 힙으로 해야 한다.

 

근데 왜 최대 힙으로 한건가요? 일단 우리 부트캠프는 뉴비들을 강사님이 멱살캐리 해가면서 데이터 분석이 가능한 인력으로 만드는 과정이다. 그래서 강사님이 OT때도 모르는 거 있으면 거리낌없이 물어봐라, 몇 번이고 설명해주겠다고 말씀하셨음... 아무튼 여기서 자료구조도 처음 보는 사람들한테 힙이 뭔지, 힙 정렬이 뭔지를 같이 설명해줘야 하는데 거기다가 최소힙, 최대힙까지 설명해야된다? 우리 이거 구현도 해야되는데? 뇌 커널패닉 1스택 추가됩니다. 저 최소힙 최대힙도 제미나이랑 쉬는시간에 티키타카 하다가 알게 된 거임...

 

if data[parent] < data[idx]:

리스트 안 뒤집고 오름차순으로 정렬하고 싶으시면 저 부등호 >로 하십시오. 그러면 부모가 자식보다 클 때 바뀌는 최소 힙이 완성된다. 저 부등호는 부모가 자식보다 작으면 바꾸라는 얘기.