[자료구조] 우선순위 큐 - 힙

우선순위 큐 ?

우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조

우선순위 큐	구현 방식	삽입시간
리스트	O(1)	O(n)
힙(Heap)	O(nlogn)	O(nlogn)

힙 ?

완전 이진트리 기반의 자료구조이다.

• 최대값, 최소값을 빠르게 구하기 위해서 사용

• max heap(최상단 노드가 최대값), min heap(최상단 노드가 최소값) 두 종류가 존재
  

• 시간 복잡도

  동작	시간복잡도
  삽입	O(logn)
  삭제	O(logn)
  최소or최대값을 검색	O(1)

heapq (힙 라이브러리 in python)

이진트리 기반의 최소 힙(min heap) 자료구조를 다룰 수 있는 함수를 제공하는 파이썬 내장 라이브러리

• 파이썬의 보통 리스트를 마치 최소 힙처럼 다룰 수 있도록 도와준다. 별개의 자료구조를 제공하는 것이 아니라는 점에 유의하자.
• 따라서 특정 리스트를 힙 구조로 유지하기 위해서는 heapq 모듈의 함수를 호출할 때마다 리스트를 인자로 넘겨서 원소를 추가하거나 삭제해야한다.

모듈 임포트

import heapq

기존 리스트를 힙으로 변환

heapq.heapify(heap)

삽입

heapq.heappush(heap, value)

최소값 얻기(=최상단 노드 얻기)

• 삭제하고 얻기
  heapq.heappop(heap)
• 삭제없이 조회만 하기
  heap[0]

max heap 으로 사용하는 방법

삽입 : heapq.heappush(heap, -value)
제거 : -heapq.heappop(heap)

heapq를 사용하는 예시 (오름차순 힙 정렬)

import heapq

def heapsort(iterable):
	h = []
    result = []
    for value in iterable:
    	heapq.heappush(h, value)
    for i in range(len(h)):
    	result.append(heapq.heappop(h))
    return result
result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)

참고 링크
https://www.geeksforgeeks.org/difference-between-min-heap-and-max-heap/