힙 ( Heap )

우선 순위 큐를 위해 만들어진 자료구조, heap.

우선순위 큐

• 데이터들이 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나감

Heap

• 완전 이진트리의 일종, 우선순위 큐를 위해 만들어진 자료구조
• 여러 개의 값들 중, 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
• 힙은 일종의 반정렬 상태를 유지
• 힙 트리에서는 중복 된 값을 허용
• 종류
  • 최대 힙
    • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 이진 트리
    • key ( 부모 ) ≥ key ( 자식 )
  • 최소 힙
    • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 이진 트리
    • key ( 부모 ) ≤ key ( 자식 )
• 보통 배열로 구현
• 구현을 쉽게하기 위해 첫 번째 인덱스인 0은 사용되지 않음
• 특정 위치의 노드 번호는 새로운 노드가 추가 되어도 변하지 않음
• 힙에서의 부모 노드와 자식 노드의 관계
  • 왼쪽 자식의 인덱스 = (부모)*2
  • 오른쪽 자식의 인덱스 = (부모)*2+1
  • 부모의 인덱스 = (부모)//2

파이썬에서의 힙

from heapq import heappush, heappop

'''
파이썬에서 heap은 heapq 모듈에 있는 heappush와 heappop을 사용.
기본적으로 min heap(최소 힙)으로 구현 되어 있기 때문에,
max heap으로 사용하려면 아래와 같이 push 할 값에 -1을 곱해 줌.
'''

min_hq = []
heappush(min_hq,val)
heappop(min_hq)

max_hq = []
heappush(max_hq,(-val,val))
heappop(max_hq)