Heap

junsoo96·2021년 12월 16일
0

Heap 자료구조

Heap이란?

힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 구현된 자료 구조이다.
Heap의 Parent Node의 Key 값과 Child Node Key 값 사이에는 대소 관계가 성립하게 되는데 정렬 방식에 따라 Min Heap과 Max Heap으로 나뉜다.

  • 최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
  • 최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

위의 사진에 보이는 트리 구조가 Heap의 구조인데, Heap의 특성 상 항상 Root Node에는 가장 작은 (혹은 큰) 우선순위를 가지는 값이 위치하게 된다.
Min Heap에서는 가장 작은 우선순위를 가지는 값이 Root로, Max Heap에서는 가장 큰 우선순위를 가지는 값이 Root로 오게됨.


Python을 활용한 알고리즘 풀이

Heap Module

Python에서는 내장 모듈인 heapq 모듈을 사용하여 쉽게 Heap 구조를 구현할 수 있다. 기본적인 방식은 최소 힙(Min Heap) 구조이다.

heapq 모듈은 Python의 List를 최소 힙(Min Heap)처럼 다룰 수 있도록 하기 때문에, 베이스가 되는 List가 필요하다. 빈 List를 생성하거나 원래 있는 List를 Heap 구조로 변경할 수 있다.

원소 추가 및 삭제

import heapq

# 빈 list 생성
heap = []

# 원소를 추가할 때, list도 계속해서 인자로 넘겨줘야함
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)

print(heap)
# [10, 50, 20]
# **heap[0] 즉, root node에는 항상 우선순위가 낮은 값이 위치하게 됨**

# 원소 삭제 또한 마찬가지로 list를 인자로 넘겨줌
****result = heapq.heappop(heap)

print(result)
print(heap)

# 10
# [20, 50]
# 가장 낮은 우선순위인 10이 반환되고 **그 다음 낮은 우선순위인 20이 root node에 위치**

List를 Heap 구조로 변경하기

이미 생성해둔 리스트가 있다면 heapify 함수를 통해 즉각적으로 힙 자료형으로 변환할 수 있다.

heap2 = [50 ,10, 20]
heapq.heapify(heap2)

print(heap2)
# [10, 50, 20]

어떤 문제에 활용하는 게 좋을까?

Heap 구조는 항상 최솟값이 0번째 index에 위치하기 때문에 최소값을 활용하는 문제나 약간의 변형을 통해 Max Heap을 사용하여 최대값을 활용하여 푸는 문제에 적합하다.

ex) 주어진 리스트의 모든 값이 T 이상이 될 때까지 최솟값 두 개를 합치기

프로그래머스 Heap 문제


Appendix

1. Max Heap 구현하기

Max Heap은 간단하게 Tuple을 사용해서 구현할 수 있다. 방법으로는 Heap에
(-value, value) 형태로 실제 Value에 음수를 붙혀 Key로 사용하게 되면 최대 우선순위를 갇는 값이 최소 우선순위로 바뀌게 된다.

heap_items = [1,3,5,7,9]

max_heap = []
for item in heap_items:
  heapq.heappush(max_heap, (-item, item))

print(max_heap)
# [(-9, 9), (-7, 7), (-5, 5), (-3, 3), (-1, 1)]

heapq.heappop() 함수를 사용하여 Root Node의 값을 제거/반환하게 되면 Tuple형태의 값이 나오게 되는데, 해당 값에서 1번째 index에 접근하면 실제 Max Heap 형태로 구현 가능하다.

2. queue.PriorityQueue() 와 Heapq의 차이

queue.PriorityQueue()heapq를 기반으로 만들어진 자료구조로 Thread Safe 한 대신 heapq보다 속도가 느리기 때문에 정확성과 시간 복잡도를 보는 알고리즘 코딩 테스트에서는 heapq를 사용하자

profile
Beginner_of_AI_Engineer

0개의 댓글