힙
힙(heap) 자료구조는 우선순위 큐를 구현하기 위해 사용하는 자료구조중 하나다!
우선순위 큐는 우선순위에 따라 처리하고 싶을 때 사용
예를들어 여러개의 데이터 중 자료구조에 넣었다가 우선적으로 꺼내고 싶은 데이터부터 꺼내서 체크할 때 우선순위 큐를 사용하면 효과적이다.
- PriorityQueue
- heapq
파이썬에서는 위 라이브러리로 구현할 수 있다.
최소힙, 최대힙을 이용하는데
최소힙을 사용할 경우 가장 낮은 데이터가 우선적으로 삭제되고 최대힙을 사용할 땐 가장 높은 데이터가 우선적으로 삭제됨
다익스트라 최단 경로 알고리즘에서는 비용이 적은 노드를 우선으로 방문하므로 최소힙을 사용하는 것이 적합!
| 우선순위 큐 구현 방식 | 삽입시간 | 삭제시간 |
| 리스트 | O(1) | O(N) |
| 힙 | O(logN) | O(logN) |
※해당 포스팅은 <이것이 취업을 위한 코딩테스트다 (나동빈 저)>를 참고하여 작성되었습니다.