priority_queue1 힙 구조, 우선순위 큐 다익스트라 알고리즘을 공부하다가 학교에선 안 배웠던 우선순위 큐를 사용하여 성능 개선을 한 경우를 많이 사용하길래 저번 학기에 배웠던 힙 구조를 복습해보았다. 힙 구조란? 힙은 트리 구조에서의 완전 이진 트리로 부모 노드의 자식이 최대 2개가 가능하며 모든 노드가 2개의 자식을 가지고 있다면 포화 이진 트리 1개의 자식을 가진 부모 노드나 같은 레벨에 자식이 없는 노드가 존재한다면 완전 이진 트리라고 한다. 힙이 되기 위한 조건은 1. 완전 이진 트리 2. Heap Property : 모든 노드는 값을 갖고, 부모 노드의 값은 자식 노드의 값보다 크거나 같다. 반대로 최소 힙은 가장 작은 노드가 상위에 있는 것이다. c++ 은 STL에 내장되어 있는 priority_queue 를 사용한다. #includ.. 2024. 1. 7. 이전 1 다음