[자료구조] 힙(Heap)

힙(Heap)

힙은 완전 이진 트리의 일종으로, 부모 노드와 자식 노드 간에 특정한 조건을 만족하는 자료구조를 말한다.

완전 이진 트리란 부모 노드 밑에 자식 노드가 최대 2개까지 있을 수 있고, 마지막 레벨을 제외한 모든 레벨에 노드가 완전히 채워져 있는 트리 구조를 말한다.

 

힙의 종류

작은 값이 부모가 되는 힙 형태를 min-heap(최소 힙), 큰 값이 부모가 되는 트리 구조를 max-heap(최대 힙)이라고 한다. 최소 힙은 맨 위의 Node의 값이 가장 작고, 최대 힙은 맨 위의 Node의 값이 가장 크다.

 

힙의 특징

• 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)의 시간 복잡도가 소요되지만, heap에서 최대값과 최소값을 찾을 때 시간복잡도는 O(logN)이다.
• 힙에서 부모는 최대 두 개의 자식 노드를 갖는다.
• 이진 힙은 언제나 가능한 가장 적은 공간을 차지한다. 즉, 다음 레벨로 내려가기 전에 모든 왼쪽/오른쪽 노드가 다 채워진다.
• 같은 레벨에서는 왼쪽 자식이 먼저 채워진다.
• 형제 노드 사이에는 어떠한 관계도 존재하지 않는다.

 

이진 탐색 트리와 힙의 차이

• 힙
  • 왼쪽과 오른쪽에 순서가 존재하지 않는다.
  • 최대/최소값 검색을 위한 구조이다.

• 이진 탐색 트리
  • 왼쪽은 부모 노드보다 작고 오른쪽은 부모 노드보다 크다.
  • 탐색을 위한 구조이다.

 

힙의 인덱스

일반적으로 힙 구현 시 배열을 활용한다. 이때 구현의 편의를 위해 Root Node의 인덱스 번호를 1로 지정하면 구현이 수월하다. (0번 인덱스를 비운다.)

• 부모 노드의 인덱스: 자식 노드 인덱스 // 2
• 왼쪽 자식 노드의 인덱스: 부모 노드 인덱스 * 2 + 1
• 오른쪽 자식 노드의 인덱스: 부모 노드 인덱스 * 2 + 2

 

힙에 데이터 삽입 과정

1. 힙은 완전 이진 트리이다. 따라서 첫 데이터가 삽입되면 Root Node가 된다.
2. 추가로 데이터가 삽입되면 왼쪽 Node가 있는지 판단하고, 없으면 왼쪽 Node에 데이터를 넣는다. 만약 왼쪽 Node가 이미 있다면 오른쪽 Node를 탐색하여 없으면 데이터를 넣는다.
3. 오른쪽 Node까지 있다면, 다시 왼쪽 Node의 자식들이 존재하는지 확인하고 왼쪽부터 삽입한다.

 

swap 방법
1. 삽입한 Node의 값과 부모 Node의 값을 비교하여 삽입한다.
2. 삽입한 Node의 값이 부모 Node의 값보다 크지 않을 때까지 swap을 수행한다. (Max Heap의 경우)

 

힙에 데이터 삭제 과정

1. 일반적으로 Heap에서의 삭제는 Root Node를 삭제한다. Heap의 용도는 최대값 또는 최소값을 Root에 놓고 바로 꺼내 쓸 수 있도록 하는 데 목적이 있기 때문이다.
2. Root Node를 삭제하고 가장 마지막에 추가한 Node를 Root Node로 이동시킨다.
3. Root Node의 자식 Node 2개를 비교하여 더 큰 값과 Swap한다. 이를 자식 Node가 없거나, 부모 Node가 자식 Node보다 클 때까지 반복한다.

 

파이썬에서의 힙

파이썬에서는 힙 기능을 위해 heapq라는 표준 라이브러리를 지원한다.

heapq는 다양한 알고리즘에서 우선순위 큐 기능을 구현하고자 할 때 사용된다. 비슷한 라이브러리로 PriorityQueue가 있지만, 보통 heapq가 더 빠르므로 heapq를 주로 사용한다.

 

heapq 모듈은 이진 트리(binary tree) 기반의 최소 힙(Min Heap, 부모 노드가 자식 노드보다 항상 작은 값을 가짐) 자료구조만을 제공한다. 이를 이용하면 단순히 원소를 힙에 전부 넣었다가 빼는 것만으로도 시간 복잡도 O(NlogN)에 오름차순 정렬이 완료된다.

 

힙에 원소를 삽입할 때는 heapq.heappush() 메서드를 이용하고, 힙에서 원소를 꺼내고자 할 때는 heapq.heappop() 메서드를 이용한다.

 

예제 1 - 오름차순 정렬

import heapq

def heapsort(iterable):
	h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
    	heapq.heappush(h, value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
    	result.append(heapq.heappop(h))
    return result
    
result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

 

예제 2 - 내림차순 정렬

파이썬에서는 최대 힙(Max Heap, 부모 노드가 자식 노드보다 항상 큰 값을 가짐)을 제공하지 않는다.

따라서 최대 힙을 구현할 때는 최소 힙을 이용하는 방식과 비슷하게 작성하되, 원소의 부호를 임시로 변경하는 방식을 사용한다. 힙에 원소를 삽입할 때 부호를 반대로 바꾸었다가, 힙에서 원소를 꺼낼 때 다시 원소의 부호를 바꾸면 된다.

import heapq

def heapsort(iterable):
	h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
    	heapq.heappush(h, -value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
    	result.append(-heapq.heappop(h))
    return result
    
result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

 

예제 3 - 기존 리스트를 힙으로 변환

heapify() 함수에 리스트를 인자로 넘기면 리스트 내부의 원소들이 힙 구조에 맞게 재배치되며 최소값이 0번째 index에 위치하게 된다.

결과적으로는 비어있는 리스트를 생성하고 heappush()로 원소를 하나씩 넣어준 효과와 같다.

시간복잡도는 리스트의 원소수인 n에 비례하며 O(n)이다.

from heapq import heapify

li = [9, 0, 4, 2, 3, 8]
heapify(li)
print(li)

 

예제 4 - n번째 최소값/최대값

• 직접 구현

from heapq import heapify, heappop
def nth_smallest(nums, n):
    heapify(nums)

    nth_min = None
    for _ in range(n):
        nth_min = heappop(nums)

    return nth_min

• 라이브러리 이용

from heapq import nsmallest

nsmallest(3, [4, 1, 7, 3, 8, 5])[-1]
#-------------------------------------#
from heapq import nlargest

nlargest(3, [4, 1, 7, 3, 8, 5])[-1]

nlargest()함수도 위와 마찬가지로 가장 큰 n개의 값을 담은 리스트를 반환하므로, 마지막 인덱스 값이 n 번째 큰 값이 된다.
nsmallest() 함수는 주어진 리스트에서 가장 작은 n개의 값을 담은 리스트를 반환한다. 따라서 함수 결과의 마지막 인덱스가 n 번째 작은 값이 된다.

 

 

🔗 Reference

자료구조 개념 이해하기 ‘힙과 힙 정렬 알고리즘’ | 요즘IT

[알고리즘] 힙(Heap)