[개념] 힙(Heap)

링크텍스트

힙 : 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리

• 완전 이진트리 : 노드를 삽입할 때 최하단 왼쪽노드부터 차례대로 삽입
• 힙의 시간복잡도 : O(logn)
• 우선순위 큐와 같이 최댓값, 최소값을 빠르게 찾아야 하는 알고리즘에 사용

힙과 이진트리의 차이점

공통점 : 힙과 이진트리 모두 이진트리임.
차이점 :

• 이진 탐색 트리는 왼쪽 자식노드의 값이 가장 작고, 그 다음 부모노드, 그 다음 오른쪽 자식 노드의 값이 가장 큼
• 힙은 조건이 없음 즉 자식노드의 값이 오른쪽이 클수도, 왼쪽이 클수도 있음
• 이진 탐색 트리는 탐색을 위한 구조,
  힙은 최대/최소값 검색을 위한 구조 중 하나로 이해하면 됨

활용

• 일반적으로 힙 구현시 배열 자료구조를 활용함.
• 힙 구현의 편리성을 위해 root 노드 인덱스 번호를 1로 지정하면, 수월함
  1) 부모 노드 인덱스 번호 = 자식 노드 인덱스 번호 // 2
  2) 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 2
  3) 오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 2 + 1

class Heap

def __inif__(self, data):
	self.heap_array = list()
    self.heap.append(None)
    self.heap.append(data)

def insert(self, data):
	if len(self.heap_array) == 0:
    self.heap.append(None)
    self.heap.append(data)
    return True

힙 생성 & 원소 추가

heapq 모듈은 리스트를 최소 힙처럼 다룰 수 있도록 하기 때문에, 빈 리스트를 생성한 후 heapq의 함수를 호출할 때마다 리스트를 인자에 넘겨야 한다.

아래 코드는 heap이라는 빈 리스트를 생성하고 50, 10, 20을 각각 추가하는 예시이다

import heapq

heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)

print(heap)

힙에서 원소 삭제

heappop 함수는 가장 작은 원소를 힙에서 제거함과 동시에 그를 결괏값으로 리턴한다.

result = heapq.heappop(heap)

print(result)
print(heap)

최대 힙 만들기

파이썬의 heapq 모듈은 최소 힙으로 구현되어 있기 때문에 최대 힙 구현을 위해서는 트릭이 필요하다.

IDEA: y = -x 변환을 하면 최솟값 정렬이 최댓값 정렬로 바뀐다.

힙에 원소를 추가할 때 (-item, item)의 튜플 형태로 넣어주면 튜플의 첫 번째 원소를 우선순위로 힙을 구성하게 된다. 이때 원소 값의 부호를 바꿨기 때문에, 최소 힙으로 구현된 heapq 모듈을 최대 힙 구현에 활용하게 되는 것이다.

아래의 예시는 리스트 heap_items에 있는 원소들을 max_heap이라는 최대 힙 자료구조로 만드는 코드이다.

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

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

print(max_heap)