[Python] Heap(힙) / heapq 모듈

1. 힙(Heap) 이란?

• 힙 : 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
  • 완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리
   

<출처: 패스트 캠퍼스>

• 힙을 사용하는 이유
  • 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림
  • 이에 반해, 힙에 데이터를 넣고 최대값과 최소값을 찾으면 O(logn)이 걸림
  • 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨.

 

2. 힙(Heap) 구조

• 힙 property : A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소 관계를 성립한다.
• 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 항상 크거나/작거나 같다 
  • 최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
  • 최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙
   

<출처: https://www.geeksforgee ks.org/heap-data-structure/minheapandmaxheap/>

 

3. 이진 탐색 트리와 힙의 공통점과 차이점

• 공통점 : 힙과 이진 탐색 트리는 모두 이진 트리임
• 차이점:
  • 힙은 각 노드의 값이 자식 노드보다 크거나 같음(Max Heap의 경우)
  • 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 노드의 값이 가장 큼
  • 힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없음
    • 힙은 왼쪽 및 오른쪽 자식 노드의 값은 오른쪽이 클 수도 있고, 왼쪽이 클 수도 있음.
• 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조 중 하나로 이해하면 됨

<출처: 패스트 캠퍼스>

 

4. 힙(Heap) 동작

 

데이터 삽입하기

• 힙은 완전 이진 트리이므로, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워지는 형태로 삽입

삽입할 데이터가 힙의 처음으로 들어가는 경우

* 삽입된 데이터는 바로 root가 된다.

 

삽입할 데이터가 힙의 데이터보다 클 경우(Max Heap의 예)

• 삽입된 데이터는 완전 이진 트리 구조에 맞추어, 최하단부 왼쪽 노드부터 채워짐
• 채워진 노드 위치에서, 부모 노드보다 값이 클 경우, 부모 노드와 위치를 바꿔주는 작업을 반복

[15,10,8,5,4] -> 20 데이터 추가 -> [15,10,8,5,4,20]

20의 부모노드 20의 인덱스 // 2를 하면 부모노드 8을 찾을 수 있음

값이 작기 때문에 8과 20 swap

[15,10,8,5,4,20] -> [15,10,20,5,4,8]

20은 또 다시 부모노드인 15와 값을 비교해서 20이 더 크기 때문에 자리를 swap 한다.

[15,10,20,5,4,8] -> [20,10,15,5,4,8]

 

데이터 삭제하기(Max Heap 의 예)

• 삭제는 최상단 노드(root 노드)를 삭제하는 것이 일반적
  • 힙의 용도는 최대값 또는 최소값을 root 노드에 넣어서, 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것
• 상단의 데이터 삭제 시 : 가장 최하단 노드와 root 노드의 값을 swap 해준뒤 최하단 노드(root 노드)를 pop 한다.
• root노드(현재 최하단 노드의 값)의 값이 child node와 비교하며 값이 작으면 left child node, right child node 를 비교하여 가장 큰 값과 swap 해준다 이 작업을 반복함

[20,10,15,5,4,8] -> [8,10,15,5,4,20] 20 pop

8은 왼쪽, 오른쪽 자식 노드와 비교하면서 자리를 바꿔준다.

8의 왼쪽 자식노드(10) 오른쪽 자식노드(15)

• 10 < 15 : 오른쪽 자식노드가 더 크다.
• 15 > 8 : 루트노드보다 오른쪽 자식노드가 더 크기 때문에 15가 루트로 와야한다.

[8,10,15,5,4,20] -> [15,10,8,5,4,20]

8은 다시 왼쪽 노드(5) 오른쪽 노드(4)와 비교한다.

8이 더 크기 때문에 종료한다.

 

 

5. 힙(Heap) 시간 복잡도

• depth(트리의 높이)를 h라고 표기한다면,
• n개의 노드를 가지는 heap 에 데이터 삽입 또는 삭제시, 최악의 경우 root 노드에서 leaf 노드까지 비교해야 하므로 h = logN에 가까우므로 시간 복잡도는 O(logn)

 

---

heapq 모듈

• 파이썬 heapq 모듈은 heapq (priority queue) 알고리즘을 제공한다.
• 파이썬에서 힙은 최소 힙(min heap)을 디폴트값으로 제공한다.
• heapq는 내장 모듈로 별도 설치 없이 바로 사용할 수 있다.

heappush(heap, item)	힙 불변성을 유지하면서 값 항목을 힙에 추가한다.
heappop(heap)	힙에서 가장 작은 항목을 꺼내고 반환다. 힙이 비어 있으면 IndexError 발생
heappushpop(heap, item)	힙에 항목을 푸시한 다음 힙에서 가장 작은 항목을 꺼내고 반환한다. heappush()/heappop() 에 대한 개별 호출하는 것보다 더 효율적으로 작용
heapify(x)	리스트 x를 즉각적으로 heap으로 변환함
heapreplace(heap, item)	힙에서 가장 작은 항목(root)을 팝하고 반환하여 새 항목도 푸시한다. 힙의 크기는 변경되지 않으며 힙이 비어 있으면 IndexError 발생 heappushpop() 대신 사용하는 것이 좋다.
merge(*iterables, key, reverse)	여러 입력을 단일 출력으로 합친다.
nlargest(n, iterable, key=None)	iterable로 정의된 데이터세트에서 가장 큰 n개의 요소가 포함된 목록을 반환
nsmallest(n, iterable, key=None)	iterable로 정의된 데이터세트에서 가장 작은 n개의 요소가 포함된 목록을 반환