Heap | 악어새62

개요

이전에 정리했던 것처럼 어떤 값을 꺼내올 때 효율적으로 꺼내와야하는 경우가 있다.
예를 들어 다익스트라 알고리즘에서 가장 비용이 저렴한 노드를 가져오는 코드를 일반 리스트로 구현할 때 시간복잡도가 O(N)이던 것을 특정한 구조를 이용하여 가져오도록 하면 LogN까지 줄어든다.

힙에 대해 알아보자.

설명

힙(쌓아 올린 더미) 자료구조는 위에서 말한 것 처럼 우선순위 큐를 구현하기 위해 사용하는 자료구조중에 하나로 큐는 가장 먼저 삽입된 데이터를 가장 먼저 처리하게 되는 자료구조다. 앞에 우선순위라는 말이 붙었으니 우선순위가 가장 높은 데이터를 가장 먼저 처리하게되는 자료구조라고 이해할 수 있다.

힙은 완전 이진트리 기반의 자료구조로 최대 힙과 최소 힙이 있다.

최대 힙은 부모 노드의 값이 항상 자식 노드보다 크거나 같아야하고 루트 노드가 가장 큰 값을 가진다.
최소 힙은 부모 노드의 값이 항상 자식 노드보다 작거나 같아야하고 루트 노드가 가장 작을 값을 가진다.

힙의 주요 연산은 삽입과 삭제로 삽입은 새로운 노드를 트리의 가장 마지막에 추가하고 부모 노드와 비교하며 위로 올라간다.
삭제는 일반적으로 루트 노드를 제거하며 트리의 가장 마지막 노드를 루트로 옮긴 뒤 아래로 내려가며 자식 노드와 비교한다.
힙은 내부적으로 리스트 혹은 배열로 구현하는데 인덱스를 이용하여 부모 자식관계를 표현한다.

예를 들어 부모 노드의 인덱스를 i라고 했을 때 왼쪽 자식 인덱스는 2i+1, 오른쪽 자식 인덱스는 2i+2 그리고 부모 인덱스는 (i-1) // 2로 표현한다.

생각해보면 내부적으로 데이터의 순서를 정하여 삽입하는데 이진 탐색으로 삽입 위치를 찾고 삽입하면 되는 것 아닌가 싶기도 하다. 혹은 데이터를 넣을 때마다 정렬하는 방법을 사용한다던지.
이러면 삽입 연산의 시간복잡도가 O(N)이 된다.

왜냐하면 이진탐색으로 적절한 위치를 찾은 뒤 그 인덱스에 요소를 편입시키려면 그 위치 이후의 원소들을 오른쪽으로 한 칸씩 이동시켜야하기 때문에 최악의 경우(첫 번째 위치에 삽입해야할 경우) O(N)이 된다.

힙은 삽입할 때 일단 가장 마지막 위치에 삽입한 뒤 부모 노드와 비교하며 올라가면서 자리를 교환한다. 이를 Heapify-Up이라고 부른다.

힙은 완전 이진 트리 구조임으로 예를 들어 10개의 데이터가 있다고 했을 때 이진 트리 구조의 depth는 최대 O(logN)이 된다.

왜냐하면 depth당 이진 트리의 최대 노드의 개수는 1+2+4+…과 같이 증가하는데 이를 등비수열의 합 공식으로 정리하면 N 은 약 2^(D+1) - 1이 된다. 만약 최대 노드의 개수가 주어졌을 때 depth를 구해보면 양변에 로그를 취해볼 수 있다. 그렇다면 depth는 log2(N+1) - 1로 표현된다.

따라서 힙에 값을 삽입할 때 맨 끝에 삽입하니 O(1), 최악의 경우 새로운 요소가 루트까지 올라가야하니 최약의 경우 O(logN)번의 연산이 필요하다.

힙에서 값을 삭제하는 경우는 가장 중요한 값(최댓값 혹은 최솟값)이 루트에 위치하고 있다. 따라서 값을 삭제할 때는 루트가 삭제되고 힙의 가장 마지막 원소를 루트로 이동시켜 빈 자리를 채운다.
그런 다음 힙의 특성을 유지하기 위해 새로운 루트 노드를 적절한 위치로 내려보낸다. 마찬가지로 최악의 경우 루트 노드가 트리의 가장 마지막 위치까지 내려가게되느 트리의 높이만큼 이동해야한다. -> O(logN)번의 연산 필요.

코드 구현

heappush

heappush는 데이터를 마지막에 추가한다.
자신의 부모요소인 (current-1) // 2인덱스의 값과 자신을 비교하여 변경한다.
2번을 자신보다 부모 요소가 클 때까지 반복한다.

def heappush(num, heap):
    heap.append(num)
    current = len(heap) - 1
    parent = (current-1) // 2
        
    while current > 0 and heap[current] < heap[parent]:
        heap[current], heap[parent] = heap[parent], heap[current]
        current = parent
        parent = (current-1) // 2    

[3, 1, 9, 7, 5, 6, 8]

[1, 3, 5, 7, 9, 6, 8]

실제 코딩테스트에서 사용할 때는 다음과 같이 사용한다.

import heapq

arr = []
heapq.heappush(arr, 1)

이런식으로 heapq는 기본 list를 대상으로 위에서 작성한 것처럼 함수를 제공한다.

개요

설명

코드 구현

heappush

heappop