[자료구조] 힙 (Heap)

힙 (Heap)

힙은 일종의 트리로 수의 집합에서 가장 작은 수 혹은 가장 큰 수와 같이 우선순위가 높은 데이터를 쉽게 꺼내기 위한 우선순위 큐를 구현한 자료구조 입니다.

 

간단한 예를 들자면 아래와 같은 배열이 있다고 합니다.

[ 20, 40, 24, 5, 92 ]

이 배열에서 가장 작은 값 혹은 가장 큰 값(Min, Max)를 찾는 다고 한다면 가장 쉽게 생각할 수 있는 방식은 아래와 같은 방식입니다.

arr = [ 20, 40, 24, 5, 92 ]

min = arr[0]
for item in arr:
    if item < min:
        min = item

print(min)

편의 상 쉽게 작성한 코드입니다. 위와 같이 for문으로 배열의 요소를 하나하나 확인하는 방법입니다. 이 경우 시간복잡도는 O(n)입니다. 즉, 모든 값을 다 확인해 봐야 알 수 있습니다.

 

하지만 힙 자료구조를 사용한다면 O(log N)의 시간복잡도로 가능합니다.

 

힙은 완전 이진 트리의 구조를 가지고 있습니다. 트리에 관한 글은 아래 링크에서 확인할 수 있습니다.

[자료구조] 트리 (Tree)

 

최소힙

최소힙이란 아래와 같이 부모노드의 데이터가 자식노드의 데이터 보다 더 작은 우선순위를 가지고 있으면 됩니다.

아래의 경우 배열에 [ 1, 2, 4, 3, 5 ] 와 같이 저장됩니다.

최대힙

최대힙은 부모노드의 데이터가 자식노드의 데이터 보다 더 큰 우선순위를 가지고 있으면 됩니다.

아래의 경우 배열에 [ 5, 4, 1, 2, 3 ] 와 같이 저장됩니다.

 

 

---

삽입, 삭제, 구현은 모두 최소힙으로 설명하도록 하겠습니다.

 

삽입

먼저 삽입의 과정을 알아보도록 하겠습니다.

 

 

위와 같은 트리에서 값 4를 넣는 과정입니다.

가장 마지막 인덱스에 값을 넣습니다. 그리고 부모노드의 값인 5와 비교합니다. 만약 5가 더 크다면 5와 4의 자리를 바꿉니다.

위와 같은 방식으로 3과 4를 비교하여 4가 더 작다면 바꾸지만 그렇지 않기에 이 상태가 최종 삽입된 힙의 구조입니다.

 

---

삭제

삭제도 위와 비슷한 방식으로 진행합니다.

위에서 삽입된 트리(위 그림)에서 삭제를 진행해 보도록 하겠습니다.

 

먼저 루트노드를 제거한 후 가장 마지막 인덱스에 있는 값을 루트노드로 옮깁니다.

그 후 자식 노드 중 자신보다 작은 값이 있다면 자신과 값을 바꿉니다. 왼쪽, 오른쪽 노드 모드가 작다면 더 작은 값과 바꿉니다. 자신의 자식 노드가 없거나 모두 자신보다 큰 값일 경우 변경을 종료합니다.

---

구현

직접 최소힙을 구현해 보겠습니다. 

heap = []


# 최소 힙
def insert(data):
    heap.append(data)
    idx = len(heap)

    while True:
        if idx <= 1:
            break

        parent_idx = idx // 2

        if heap[parent_idx - 1] < heap[idx - 1]:
            break

        heap[idx - 1], heap[parent_idx - 1] = heap[parent_idx - 1], heap[idx - 1]
        idx = parent_idx


def delete():
    last_data = heap.pop()
    heap[0] = last_data

    idx = 1
    while True:
        l_child_idx = idx * 2
        r_child_idx = idx * 2 + 1

        if l_child_idx - 1 > len(heap) - 1:
            break

        if r_child_idx - 1 > len(heap) - 1:
            if heap[l_child_idx - 1] < heap[idx - 1]:
                heap[idx - 1], heap[l_child_idx - 1] = heap[l_child_idx - 1], heap[idx - 1]
            break

        if heap[l_child_idx - 1] < heap[r_child_idx - 1]:
            heap[idx - 1], heap[l_child_idx - 1] = heap[l_child_idx - 1], heap[idx - 1]
            idx = l_child_idx
        else:
            heap[idx - 1], heap[r_child_idx - 1] = heap[r_child_idx - 1], heap[idx - 1]
            idx = r_child_idx


insert(18)
insert(13)
insert(5)
insert(3)
insert(4)

delete()

print(heap)

 

---

참고자료

reakwon.tistory.com/42