알고리즘5 [최소 힙] c++ 구현 및 설명 이미지 출처:https://namu.wiki/w/%ED%9E%99%20%ED%8A%B8%EB%A6%AC 힙의 정의 우선 순위 큐를 이해하기 위해서는 힙이라는 것을 알아야 한다. 완전 이진트리의 일종으로 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안되었다. 힙의 특징키 값의 대소관계는 오로지 부모 노드와 자식노드 간에만 성립하여 형제 사이에는 대소 관계가 정해지지 않는다. (예를 들어 9와 14사이에는 우선순위가 있지만 14와 18사이에는 우선순위가 존재하지 않는다.) 힙의 시간 복잡도는 O(logn)이다. 힙의 종류최대 힙(Max Heap): (완전 이진 트리) + (부모 노드 > 자식 노드)최소 힙(Min Heap): (완전 이진 트리) + (부모 노드 < 자식 노드) 이미지 출처:http.. 2024. 2. 14. 이전 1 2 다음 728x90