[자료구조] 힙

힙

힙(heap) 자료구조는 우선순위 큐를 구현하기 위해 사용하는 자료구조중 하나다!

우선순위 큐는 우선순위에 따라 처리하고 싶을 때 사용

 

예를들어 여러개의 데이터 중 자료구조에 넣었다가 우선적으로 꺼내고 싶은 데이터부터 꺼내서 체크할 때 우선순위 큐를 사용하면 효과적이다.

• PriorityQueue
• heapq

파이썬에서는 위 라이브러리로 구현할 수 있다.

최소힙, 최대힙을 이용하는데 

최소힙을 사용할 경우 가장 낮은 데이터가 우선적으로 삭제되고 최대힙을 사용할 땐 가장 높은 데이터가 우선적으로 삭제됨

다익스트라 최단 경로 알고리즘에서는 비용이 적은 노드를 우선으로 방문하므로 최소힙을 사용하는 것이 적합!

 

우선순위 큐 구현 방식	삽입시간	삭제시간
리스트	O(1)	O(N)
힙	O(logN)	O(logN)

 

※해당 포스팅은 <이것이 취업을 위한 코딩테스트다 (나동빈 저)>를 참고하여 작성되었습니다.