. 힙(heap) 구조 만들기
본문 바로가기
프로그래밍 공부/파이떤

힙(heap) 구조 만들기

by 불냥이_ 2020. 12. 21.

11279번: 최대 힙 (acmicpc.net)

 

11279번: 최대 힙

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가

www.acmicpc.net

이번 또한 백준 문제이지만, 힙 정렬과 힙 배열에 삽입하는 코드를 구현해볼 것이기 때문에 파이썬 항목에 작성하겠다.

 

우선 배열을 힙 구조로 만드는 함수부터 구현해보자.

힙 정렬은 우선 제일 낮은 레벨의 leaf를 자식으로 하고, 윗 레벨의 node를 부모로 하는 최대 3개의 tree를 힙 배열로 만들고 점점 상향하는 bottom-up 방식으로 진행할 것이다.

 

그렇다면 힙 정렬의 함수는 최대 3인자, node-left child-right child(없을 수도 있음) 로 진행될 것이다.

이 함수는 이 tree의 left child의 위치(idx)를 가져와서 실행될 것이다. (right child가 없을 수도 있고, tree 안의 3 요소는 left child의 idx로 표시 가능하다.)

 

또한, 완전 이진 트리의 왼쪽  인자는 항상 짝수이다. 그래서 

 

def heap_array(arr, child):
    parent = ( child - 1 ) // 2
    if child % 2 == 1: # child가 홀수라면 (오른쪽 자식이 있다면)
        left = child - 1
        right = child
    else: # child가 짝수라면 (왼쪽 자식 밖에 없다면)
        left = child

 

힙 정렬은 부모 인자가 항상 자식 인자보다 커야된다는 것이다. 

 

그렇다면 최초 선택은 배열의 가장 마지막 leaf a[-1]와 그 요소의 부모가 될 것이다.

    # 왼쪽 자식과 부모 비교
    if arr[left] > arr[parent]:
        arr[left], arr[parent] = arr[parent], arr[left]

    # 오른쪽 자식과 부모 비교
    if arr[right] and arr[right] > arr[parent]:
        arr[right], arr[parent] = arr[parent], arr[right]  

 

아름답지는 않지만, 일단 원시적인 방법으로 3개 요소의 tree에서의 힙정렬을 구현해보았다.

 

다음은 레벨이 3개 이상일 때, 힙 정렬을 구현해보는 것이다.

이 때, 문제가 발생한다. 

 

위의 함수에서는 시작 인자를 child로 했기 때문에 레벨이 많아지면 어디까지 힙 정렬을 수행할 tree가 되는지 지시하기 힘들어진다는 것이다. 이 때문에 힙 정렬 함수의 시작인자는 child가 아니라 부모가 되어야한다.

 

그러면 다시 함수를 재구성해보자. 

 

 

그런데 잠깐. 재구성 하기 전에 여기서 의문이 하나 드는데, 2레벨 tree인 경우에는 상기의 비교방식을 쓸 수 있겠지만, 3레벨 이상의 tree인 경우에는 어떻게 다레벨에서 비교를 하고 힙정렬을 할 수 있겠는가?

 

여기서는 원시적인 방법이 아닌 좀 더 고차원의 방법으로 풀어야 한다.

1. 우선 맨 처음 부모 자리의 idx와 값을 따로 저장한다.

 

2. 그 다음 부모값과 자식값을 비교한다. (우선, 자식 둘을 비교하고, 큰 숫자의 위치와 값을 받아온 뒤, 부모와 비교한다.)

 

3. 재귀 함수의 꼴이므로, 이미 하위 단계에서는 힙 정렬이 완료된 상태이다. 그렇기 때문에 3번째 단계에서 부모값이 자식값보다 크다면, 이 단계에서도 힙 정렬이 완료된 상태이기 때문에 더 진행할 필요가 없다.

 

4. 하지만, 3번째 단계에서 부모값과 자식값이 바뀐다면, 바뀐 자식값이 더 하위 레벨의 값보다 더 크다는 보장은 없다. 그렇기때문에 다시 비교를 해줘야한다. 여기에서 우리는 단계 2로 되돌아가야한다. 

 

5. 그렇다면 어디까지 내려갈 것인가? 이는 마지막 부모값의 위치를 받아와서, 이 마지막 부모값의 위치와 비교하면 된다.

 

6. 반복문은 while을 사용하고, 3번째 단계에서 부모값과 자식값이 바뀌었을 때, idx값도 같이 바꿔주면 된다.

 

7. 그리고 가장 마지막으로 바뀐 자식 위치에 맨 처음 부모 값을 넣는다.

 

이를 코드로 구현하면 다음과 같다.

# 힙 정렬 하는 과정
def heap_array(arr, first_parent_idx, last_leaf):
    # 임시 부모 위치에 처음 부모 idx 저장
    cur_parent_idx = first_parent_idx 
    # 제일 마지막으로 바뀔 자식 위치에 넣을 최초의 부모 값
    first_parent_value = arr[first_parent_idx]
    # 전체 tree의 마지막 idx를 받아와서, 마지막 부모 idx 생성
    last_parent_idx = (last_leaf - 1) // 2

    # 임시 부모 위치가 마지막 부모 idx보다 작을 때만 실행
    while cur_parent_idx <= last_parent_idx:
        # 임시 부모의 좌우 자식 idx 생성
        left_child_idx = cur_parent_idx * 2 + 1
        right_child_idx = left_child_idx + 1

        # 자식 간의 값 비교
        if right_child_idx < last_leaf and arr[right_child_idx] > arr[left_child_idx]:
            # 바꿀 자식 값 지정
            child_changed_idx = right_child_idx
        else: 
            child_changed_idx = left_child_idx


        # 부모 자식 값 비교
        if arr[cur_parent_idx] > arr[child_changed_idx]:
            # 부모가 크면 break
            break
        
        # 아니라면
        else:
            # 현재 부모 값에 자식 값 삽입
            arr[cur_parent_idx] = arr[child_changed_idx]
            # 다음 탐색을 위해서 바뀐 자식 위치를 현재 부모 위치로 지정
            cur_parent_idx = child_changed_idx
            
        # 최초의 부모 값은 마지막으로 바뀐 자식 위치에 넣는다.
        arr[cur_parent_idx] = first_parent_value

 

변수 명이 길지만, 내가 코드를 짜면서 헷갈리는 곳이 많아서 이런 식으로 했다. 양해바란다.

 

그 다음, 이 함수를 어떤 for문으로 돌릴 것이냐가 중요하다.

부모 인자에 대해서 실행할 것이기 때문에 for 문은 다음과 같다. 

n = len(arr)
for i in range( (n - 1)//2 , -1, -1):
    heap_array(arr, i, n-1)

이제 실행해보자. 

 

arr = [101542863790] 을 넣어서

[10, 9, 8, 7, 2, 5, 6, 3, 4, 1, 0] 가 출력 되었다.

알아보긴 힘들긴 하지만, 10은 9,8 을 가지고, 9 는 7과2, 8은 5와 6, 7은 3과 4를 가지고 2는 1과 0 을 가지는 힙정렬로 되었음을 확인할 수 있다.

 

(이 코드를 가지고 힙 정렬은 구현되었지만, 백준 문제를 풀면 시간초과뜬다. 힙 관련 메소드를 쓰자 ㅡ.ㅡ

그래도 시간나면 시간초과 안뜨는 힙 정렬을 구현해보도록 하겠다. 오늘은 여기까지)

 

 

 

 

 

 

 

 

'프로그래밍 공부 > 파이떤' 카테고리의 다른 글

파일을 열고 읽어보자  (0) 2021.04.19
Stack 만들기 (Class에 관하여)  (0) 2020.12.19

댓글