Table of Contents
  1. Heap
    1. Heap의 종류
    2. Heap의 특징
    3. Heap sort
    4. Heap 구현
  2. Heapq
    1. Methods
      1. heappush(heap, item)
      2. heappop(heap)
      3. heappushpop(heap, item)
      4. heapify(x)
      5. heapreplace(heap, item)
      6. merge(*iterables, key=None, reverse=False)
      7. nlargest(n, iterable, key=None)
      8. nsmallest(n, iterable, key=None)
    2. Max Heap
  3. References
  4. 마치며

Python의 Heqpq에 대해 알아보도록 하겠습니다.

Heap

Heapq를 알기 위해선 자료구조 Heap을 알아야합니다. 위키백과에서 정의하는 Heap은 다음과 같습니다.

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다. A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.

Heap의 종류

  • Max Heap (최대 힙)

    • key(부모) >= key(자식)
    • Root에 최댓값이 위치

  • Min Heap (최소 힙)

    • key(부모) <= key(자식)
    • Root에 최솟값이 위치

Heap의 특징

Heap은 최댓값과 최솟값을 쉽게 구하기 위한 자료구조로, 배열을 Heap의 형태로 정렬 하는 과정을 heapify라 부르며 완전 이진트리 구조이기 때문에 O(log(n))의 시간 복잡도를 가집니다.

heapify는 상향식과 하향식 두 가지 방법이 존재하며 자세한 방법은 Binary Heap Tree implementation in Python 영상을 참고해주세요.

Heap sort

이러한 Heap의 특징을 이용한 정렬이 바로 Heap Sort(힙정렬)인데, 전체 n개의 노드 중 절반의 노드에 대해서만 heapify를 반복하면 되기 때문에 (n/2) * log(n)의 시간복잡도를 가지나 log(n)이 n/2보다 작기 때문에 사실상 O(n)의 속도를 가집니다. (공식적으로는 O(nlog(n))의 시간복잡도를 가진다고 표현합니다.)

✔︎ heap sort의 특징

  • Quick Sort보다 안정적이게 O(nlog(n))의 시간복잡도를 보장함
  • 메모리상으로 병합 정렬보다 효율적임

Heap 구현

Python을 이용하여 Heap을 구현해보도록 하겠습니다. Heap은 바로 다음과 같은 규칙을 이용하면 배열을 이용하여 쉽게 구현할 수 있습니다.

배열은 index가 0부터 시작하는 것을 고려해서 봐주세요.
1
2
3
index(left child) = 2 * index(parent) + 1
index(right child) = 2 * index(parent) + 2
index(parent) = (index(child) - 1)//2

위와 같은 규칙을 이용하여 최대힙(max heap)을 구현해보도록 하겠습니다. 자세한 설명은 Binary Heap Tree implementation in Python를 참고해주세요.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class MaxHeap:
    def __init__(self):
        self.heap = []

    def print_heap(self):
        print(self.heap)

    def get_parent(self, i):
        return i-1)//2

    def get_left_child(self, i):
        return 2*i+1

    def get_right_child(self, i):
        return 2*i+2

    def has_parent(self, i):
        return self.get_parent(i) >= 0

    def has_left_child(self, i):
        return self.get_left_child(i) < len(self.heap)

    def has_right_child(self, i):
        return self.get_right_child(i) < len(self.heap)

    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def insert_key(self, key):
        self.heap.append(key)
        self.heapify_up(len(self.heap)-1)

    def heapify_up(self, i):
        while self.has_parent(i) and self.heap[i] > self.heap[self.get_parent(i)]:
            self.swap(i, self.get_parent(i))
            i = self.get_parent(i)

    def delete_root(self):
        if len(self.heap) == 0:
            return -1
        last_index = len(self.heap)-1
        self.swap(0, last_index)
        root = self.heap.pop()
        self.heapify_down(0)
        return root

    def heapify_down(self, i):
        while self.has_left_child(i):
            max_child_index = self.get_max_child_index(i)
            if max_child_index == -1:
                break
            if self.heap[i] < self.heap[max_child_index]:
                self.swap(i, max_child_index)
                i = max_child_index
            else:
                break

    def get_max_child_index(self, i):
        if self.has_left_child(i):
            left_c = self.get_left_child(i)
            if self.has_right_child(i):
                right_c = self.get_right_child(i)
                if self.heap[left_c] > self.heap[right_c]:
                    return left_c
                else:
                    return right_c
        else:
            return -1
1
2
3
4
5
6
7
8
9
10
11
max_heap = MaxHeap()

array = [45, 99, 63, 27, 29, 57, 42, 35, 12, 24]

# build max heap
for i in array:
    max_heap.insert_key(i)

max_heap.print_heap() # [99, 45, 63, 35, 29, 57, 42, 27, 12, 24]
max_heap.insert_key(50) # [99, 50, 63, 35, 45, 57, 42, 27, 12, 24, 29]
max_heap.delete_root() # [63, 50, 57, 35, 45, 29, 42, 27, 12, 24]

Heapq

Python에 내장된 heapq라는 heap queue algorithm 모듈을 이용하면 손쉽게 heap을 사용할 수 있습니다. 아래와같이 import를 하여 사용하시면 됩니다.

1
from heapq import *

Methods

다음으로 heapq의 내장 함수들에 대해서 설명하도록 하겠습니다.

heappush(heap, item)

heappush는 heap에 요소를 추가합니다. 첫 번째 인자로 heap을 넣는 것에 주의해야합니다.

1
2
3
4
from heapq import *
nums = [2, 4, 1, 7, 3, 8, 5, 4, 4, 4]
heapify(nums)     # [1, 3, 2, 4, 4, 8, 5, 4, 7, 4]
heappush(nums, 6) # [1, 3, 2, 4, 4, 8, 5, 4, 7, 4, 6]

heappop(heap)

heappop은 root에 있는 요소를 꺼내어 반환합니다.

1
2
3
4
from heapq import *
nums = [1, 3, 2, 4, 4, 8, 5, 4, 7, 4, 6]
heappop(nums) # 1
print(nums)   # [2, 3, 5, 4, 4, 8, 6, 4, 7, 4]

heappushpop(heap, item)

heappushpop은 heap에 요소를 추가한 뒤 root에 있는 요소를 꺼내어 반환합니다.

1
2
3
4
5
from heapq import *
nums = [2, 4, 1, 7, 3, 8, 5, 4, 4, 4]
heapify(nums)                # [1, 3, 2, 4, 4, 8, 5, 4, 7, 4]
print(heappushpop(nums, 10)) # 1
print(nums)                  # [2, 3, 5, 4, 4, 8, 10, 4, 7, 4]

아래 코드는 0을 push하는 경우 root에 0이 들어가기 때문에 pop을 하는 경우 0이 그대로 나오는 것을 확인할 수 있습니다.

1
2
3
4
5
from heapq import *
nums = [2, 4, 1, 7, 3, 8, 5, 4, 4, 4]
heapify(nums)                # [1, 3, 2, 4, 4, 8, 5, 4, 7, 4]
print(heappushpop(nums, 0))  # 0
print(nums)                  # [1, 3, 2, 4, 4, 8, 5, 4, 7, 4]

heapify(x)

다음과 같이 배열을 heapify 함수에 전달하면 min heap(최소힙)을 변환합니다.

1
2
3
4
from heapq import *

nums = [2, 4, 1, 7, 3, 8, 5, 4, 4, 4]
heapify(nums) # [1, 3, 2, 4, 4, 8, 5, 4, 7, 4]

heapreplace(heap, item)

heapreplace는 heappushpop과 달리 pop을 먼저 수행한 뒤 push를 수행합니다. 따라서 0이 가장 작은 값 임에도 불구하고 pop먼저 수행하기 때문에 1이 나오고, 0이 push 됩니다.

1
2
3
4
5
from heapq import *
nums = [2, 4, 1, 7, 3, 8, 5, 4, 4, 4]
heapify(nums)                # [1, 3, 2, 4, 4, 8, 5, 4, 7, 4]
print(heapreplace(nums, 0))  # 1
print(nums)                  # [0, 3, 2, 4, 4, 8, 5, 4, 7, 4]

merge(*iterables, key=None, reverse=False)

merge는 정렬된 배열들을 합치는 함수입니다.

1
2
3
4
5
6
from heapq import *
nums1 = [2, 4, 1, 7]
nums2 = [3, 8, 5, 4]
nums1.sort()              # [1, 2, 4, 7]
nums2.sort()              # [3, 4, 5, 8]
list(merge(nums1, nums2)) # [1, 2, 3, 4, 4, 5, 7, 8]

nlargest(n, iterable, key=None)

n번 째로 큰 값은 max heap(최대힙)을 이용하여 아래와 같이 구현할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
from heapq import *

nums = [2, 4, 1, 7, 3, 8, 5, 4, 4, 4]
heap = []
for num in nums:
    heappush(heap, (-num, num))

n = 3
while n > 0:
    answer = heappop(heap)[1]
    n -= 1
answer # 5

하지만 heapq의 내장함수인 nlargest를 이용하면 다음과 같이 구현할 수 있습니다. nlargest는 배열을 반환하며, 결과값의 마지막 요소가 n번 째로 큰 값입니다.

1
2
3
4
from heapq import *
nums = [2, 4, 1, 7, 3, 8, 5, 4, 4, 4]
heapify(nums)
nlargest(3, nums) # [8, 7, 5]

nsmallest(n, iterable, key=None)

n번 째로 작은 값을 heapify와 heappop을 이용하여 아래와 같이 구현할 수 있습니다.

10개의 데이터 중 10번째로 작은 값은 8입니다.
1
2
3
4
5
6
7
8
9
10
from heapq import *

nums = [2, 4, 1, 7, 3, 8, 5, 4, 4, 4]
heapify(nums)

n = 10
while n > 0:
    answer = heappop(nums)
    n -= 1
answer # 8

하지만 heapq의 내장함수인 nsmallest를 이용하면 다음과 같이 구현할 수 있습니다. nsmallest는 배열을 반환하며, 결과값의 마지막 요소가 n번 째로 작은 값입니다.

1
2
3
4
from heapq import *
nums = [2, 4, 1, 7, 3, 8, 5, 4, 4, 4]
heapify(nums)
nsmallest(10, nums) # [1, 2, 3, 4, 4, 4, 4, 5, 7, 8]

Max Heap

기본적으로 heapq는 min heap(최소힙)을 지원하는데, 아래 예제와 같이 tuple안에 실제 값의 음수값과 실제 값을 넣어 max heap(최대힙)과 같이 구현할 수 있습니다.

1
2
3
4
5
6
7
8
from heapq import *

nums = [2, 4, 1, 7, 3, 8, 5, 4, 4, 4]
heap = []
for num in nums:
    heappush(heap, (-num, num))

print([v for i, v in heap]) # [8, 4, 7, 4, 4, 1, 5, 2, 4, 3]

References

마치며

heap에 대해 직접 구현 해보고, python 내장함수 heapq를 이용해보기도 하였습니다. push와 pop이 빈번하며 최솟값과 최댓값을 필요로 하는 경우 heap을 떠올려 유용하게 사용하면 좋을 것 같습니다.