[Python] 자료구조 - 최소힙, 최대힙 정리 및 백준 1715번

안녕하세요
알고리즘 공부를 하다가
힙 문제가 나와서 정리를 해서 블로그에 정리를 해보려고 하는데요
다들 참고하고 부족하신건 댓글로 달아주세요

---

힙 자료구조

힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전 이진트리 기본으로 한다.

• 각 노드의 key 값이 해당 노드의 자식 노드의 key 값보다 작지 않거나 크지 않은 완전 이진트리
• 키 값의 대소 관계는 부모-자식 노드 사이 간에만 성립하며 형제 노드 사이에는 영향을 미치지 않음
• 자식 노드의 최대 개수는 힙의 종류에 따라 다르지만 이진트리에서는 최대 2개(완전 이진트리를 사용한다고 가정)
• i번째 노드의 자식 노드가 2개인데 왼쪽 자식 노드는 2i, 오른쪽 자식 노드는 2i+1이고, 부모노드는 i/2가 됩니다.

 

최소 힙(Min Heap)  부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙 최소 힙은 최소 트리이면서 이진트리이다.

 

최대 힙(Max Heap) 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙 최소 힙은 최소 트리이면서 이진트리이다.

 

<https://www.geeksforgeeks.org/heap-data-structure/>

heapq - 힙 큐 알고리즘

파이썬에서는 heapq 모듈을 사용해서 최소 힙과 최대 힙을 구현할 수 있다.

힙을 만들려면, []로 초기화된 리스트를 사용하거나, 함수 heapify()를 통해 값이 들어 있는 리스트를 힙으로 변환할 수 있습니다.
다음과 같은 함수가 제공됩니다.

● heapq.heappush(heap, item)

힙 불변성을 유지하면서, item 값을 heap으로 푸시합니다.

from heapq import heappush, heappop

heap = []

heappush(heap, 4)
heappush(heap, 1)
heappush(heap, 7)
heappush(heap, 3)
heappush(heap, 2)

print(heap)

heap이라는 리스트를 정의를 하고 heappush(heap, item) 함수를 이용을 하여서 힙에다가 값을 넣어서 출력을 하면 최소 힙으로 정의가 됩니다. 내부적으로 이진 트리에 원소를 추가하는 heappush() 함수는 O(log(n))의 시간 복잡도를 가집니다.

●  heapq.heappop(heap)

힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝 하고 반환합니다. 힙이 비어 있다면, IndexError 가 발생합니다. 팝 하지 않고 가장 작은 항목에 액세스 하려면, heap[0]을 사용하세요

print(heappop(heap))
print(heap)

가장 작았던 1이 삭제되어 리턴되었고, 그다음으로 작았던 2가 인덱스 0으로 올라왔습니다.

● heapq.heappushpop(heap, item)

힙에 item을 푸시한 다음, heap에서 가장 작은 항목을 팝하고 반환합니다. 결합한 액션은 heappush()한 다음 heappop()을 별도로 호출하는 것보다 더 효율적으로 실행합니다.

from heapq import heappushpop


print(heappushpop(heap, 5))
print(heap)

● heapq.heapify(x)

리스트 x를 선형 시간으로 제자리에서 힙으로 변환합니다.

from heapq import heapify

heap = [4,1,7,3,8,5]

heapify(heap)

print(heap)

 

heapify() 함수에 리스트를 인자로 넘기면 리스트 내부의 원소들의 위에서 다룬 힙 구조에 맞게 재배치되며 최소값이 0번째 인덱스에 위치됩니다. 즉, 비어있는 리스트를 생성한 후 heappush() 함수로 원소를 하나씩 추가한 효과가 납니다. heapify() 함수의 성능은 인자로 넘기는 리스트의 원소수에 비례합니다. 즉 O(n)의 시간 복잡도를 가집니다.

heapify() 함수를 사용할 때 주의할 점은 새로운 리스트를 반환하는 것이 아니라 인자로 넘긴 리스트에 직접 변경한다는 것입니다. 따라서 원본 리스트의 형태를 보존해야되는 경우에는 반드시 해당 리스트를 복제한 후에 인자로 넘겨야 하겠습니다.

 

※  [응용] 최대 힙

heapq에서는 최대 힙을 제공하지 않는다. 따라서 다음과 같이 부호를 변경하는 방법을 사용해서 최대 힙을 구현한다. 부호를 바꿔서 최소 힙에 넣어준 뒤에 최솟값부터 pop 해줄 대 다시 부호를 바꿔주면 최대 힙과 동일하다

import heapq

heap = []
values = [1,5,3,2,4]

# 아래 for문을 실행시키고 나면 heap은 [-5,-4,-3,-1,-2]가 된다.
for value in values:
	heapq.heappush(heap, -value)

# 아래 for문을 실행시키면 5,4,3,2,1이 출력된다. 즉, 큰 숫자부터 출력이 된다.
for i in range(5):
	print(-heapq.heappop(heap))

●  [응용] n 번째 최소값/ 최대값

최소 힙이나 최대 힙을 사용하면 n 번째로 작은 값이나 n번째로 큰 값을 효과적으로 구할 수 있습니다.
n 번째 최소값을 구하기 위해서는 주어진 배열로 힙을 만든 후, heappop() 함수를 n번 호출을 하면 됩니다.

from heapq import heappush, heappop, heapify

values = [1,5,3,2,4]


def nth_smallest(nums, n):
    # heap = []
    # for num in nums:
    #     heappush(heap, num)
    heap =  nums[:]
    heapify(heap)
    nth_min = None
    for _ in range(n):
        nth_min = heappop(heap)
        
    return nth_min
print(nth_smallest(values, 3))

from heapq import nsmallest

values = [1,5,3,2,4]

print(nsmallest(3, values)[-1])

heapq 내장 모듈 안에 'nsmallest(key, values)' 함수가 있어서 최소값 몇개를 구해서 힙에 마지막 쪽에 있는 값을 구할 수가 있습니다.

from heapq import nlargest

values = [1,5,3,2,4]

print(nlargest(2, values)[-1])

최대값도 마찬가지로 heapq 내장 모듈 안에 'nlargest(key, value)' 함수가 있어서 최대값 몇 개를 구해서 힙에서 마지막쪽에 값을 구할 수 있습니다.

---

※백준 문제※

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

내가 heapq 모듈을 공부하게된 계기가 된 문제이다.
처음에는 그리디 알고리즘 문제로 분류가 되어있어서 풀려고했는데 안되었죠...
그래서 공부를 하다가 heapq라는 모듈을 사용해서 힙 알고리즘을 사용하니까 풀렸던 문제입니다.

import heapq as hq
import sys
input = sys.stdin.readline

n = int(input())
num = [int(input()) for _ in range(n)]

hq.heapify(num)

if n == 1:
    print(0)
else:
    answer = 0
    while len(num) > 1:
        a = hq.heappop(num)
        b = hq.heappop(num)
        hq.heappush(num, a+b)
        answer += a+b
    print(answer)

먼저 n으로 입력 받은 카드 묶음의 수를 입력을 해서 리스트에 넣어줍니다.
그런다음에 heapify 함수를을 이용하여서 리스트에 있는 값을 힙알고리즘으로 정의 시켜줍니다.

num의 길이가 1이상 일때까지 while 반복문을 돌려서 a,b 값에다가 힙의 최소원소 두개를 정의해줍니다.
a+b의 더한 값을 다시 힙 알고리즘에다가 heappush 함수를 이용을 하여서 다시 push해줍니다.
결과값에다가 a+b값을 더해줍니다.
마지막으로 결과값을 출력을하면 최소한 몇 번의 비교가 가능한 횟수를 구할 수가 있습니다.

 

참고

https://www.daleseo.com/python-heapq/

파이썬의 heapq 모듈로 힙 자료구조 사용하기