[Python] - heap

힙(heap)

힙은 힙 속성을 충족하는 특수 트리 기반 데이터 구조이고 완전한 이진 트리다 즉, 왼쪽에서 오른쪽으로 채워지는 마지막 수준을 제외하고 트리의 각 수준이 완전히 채워진다. 힙에서 각 노드의 키는 자식 키보다 크거나 같거나(max-heap) 작거나 같다(min-heap).

 

힙에는 두가지 유형이 있다.

• 최대 힙(Max-heap)
  • 최대 힙에서 부모 노드는 자식 키보다 크거나 같은 키를 가진다. 가장 큰 키는 루트 노드에 있다.
• 최소 힙(Min-heap)
  • 최소 힙에서 부모 노드는 자식 키보다 작거나 같은 키를 가진다. 가장 작은 키는 루트 노드에 있다.

힙은 일반적으로 우선 순위 큐를 구현하는데 사용되며 우선 순위가 가장 높거나 낮은 요소에 효율적으로 엑세스 할 수 있다. 힙의 가장 일반적인 응용 프로그램은 힙 데이터 구조를 사용하여 요소를 정렬하는 힙 정렬 알고리즘 이다.

 

힙과 관련된 몇가지 일반적인 작업은 다음과 같다.

• 삽입(Insert): 힙 속성을 유지하면서 요소를 힙에 추가한다.
• 추출(Extract): 힙에서 루트 요소(최대 또는 최소)를 제거하고 반환한 다음 힙 속성을 유지하도록 힙을 재구성한다.
• Peek: 루트 요소(최대 또는 최소)를 제거하지 않고 반환한다.

Python에서 heapq 모듈은 최소 힙이 있는 힙 데이터 구조의 구현을 제공한다. 다음은 heapq 모듈을 사용하여 최소 힙을 만드는 예제다.

import heapq

heap = []
heapq.heappush(heap,3)
heapq.heappush(heap,1)
heapq.heappush(heap,2)

print(heap) #Output:[1,3,2]

smallest_element = heapq.heappop(heap)
print(smallest_element) # Output:1
print(heap) # Output: [2,3]

# Peek at the smallest element without removing it
smallest_element = heap[0]
print(smallest_element) # Output:2

 

 

이 예제에서는 heapq 모듈을 사용하여 최소 힙을 만든다. heappush 함수를 사용하여 요소를 힙에 삽입하고 heappop 함수를 사용하여 가장 작은 요소를 제거한다. 제거하지 않고 가장 작은 요소를 살펴보려면 목록의 첫번째 요소(인덱스 O)에 엑세스 하면 된다.

heapq 모듈은 최대 힙 구현을 제공하지 않지만 값을 삽입하기 전과 추출한 후에 값을 부정하여 최대 힙을 생성할수 있다.