데이터구조 힙(Heap) python

Heap

힙은 특정한 규칙을 갖는 자료구조로, 최대값과 최소값을 찾는 연산을 빠르게 하기 위해 고안된 완전 이진 트리를 기본으로 한다.

언젠가 수업 들으면서 이중 트리에 대해 배운 것 같은데 기억이 휘발되었다…. 아마 가지치기 형태로 데이터를 구성한 다음 두 개씩 값을 비교하여 순서를 바꾸는 거였나….

• Heap의 좋은 점은 따로 정렬하지 않아도 가장 큰 값과 작은 값을 알아서 찾아준다는 것이다.
• 자식 노드의 최대 개수는 힙의 종류에 따라 다르지만 이진트리에서는 최대 2개로 한정한다.

1. 최대 힙 (max heap)key(T.parent(v))≥key(v)
2. 각 노드의 키 값이 그 자식 노드의 키 값보다 작지 않은 힙
3. 최소 힙 (min heap)ket(T.parent(v))≤key(v)
4. 각 노드의 키 값이 그 자식노드의 키 값보다 크지 않은 힙
5. 시간 복잡도
6. O(logN)

Heap의 연산

insert

• 삽입하고자 하는 값을 트리의 가장 마지막 원소에 추가
• 부모노드-자식노드 간의 대소관계를 비교하며 만족할 때까지 자리 교환 반복

delete

• 힙에서는 루트 노드만 삭제 가능 → 루트 노드 제거
• 가장 마지막 노드를 루트로 이동시킴
• 부모노드-자식노드 간의 대소관계를 비교하며 만족할 때까지 자리 교환 반복

구현 방법

파이썬에서 제공하는 힙큐 모듈을 사용한다. (min heap이 기본적이다)

module import

import heapq

node insert

heap = []
heapq.heappush(heap, value)

node delete

heapq.heappop(heap) # heap의 최소값 반환

값을 없애지 않고 접근만 하고 싶다면 기존 리스트와 같이 인덱스를 사용한다.

기존 리스트를 heap으로 만들고 싶다면

heapq.heapify(list_name)