# 힙(heap)과 다익스트라(dijkstra) 알고리즘
Programming
2017. 11. 10. 13:43
다익스트라 알고리즘을 구현하기 위해 반드시 힙이 필요하지는 않다. 다만, 공부한 교재 ‘Inroduction to Algorithms’에서는 최소 우선 순위 큐를 이용하기 때문에 힙을 사용하였을 뿐이다.※ 힙(heap)힙은 이진 트리 기반이지만, 값이 입력될 때 정렬이 된다는 점이 이진 트리와 큰 차이점이다. 즉, 최소값 혹은 최대값을 출력할 때 트리나 다른 자료 구조에서는 정렬이나 탐색 과정을 거쳐야 하는 반면, 힙은 그런 과정이 생략되고 루트 노드만 반환한다면 원하는 값을 얻을 수 있다.따라서 힙은 다른 자료 구조에서는 수행하지 않는 ‘heapify’라는 작업을 수행하여 루트 노드에 최소값 혹은 최대값을 유지한다. 아래는 교재에서 소개된 최대값에 대한 heapify를 수행하는 알고리즘을 최소값에 대한..
