CS/자료구조
[자료구조] 힙(Heap): 우선순위 큐(Priority Queue)
0. 힙(Heap)완전 이진 트리에 있는 노드에서 가장 큰 키 값이나 가장 작은 키 값을 찾기 위해서 만든 자료구조이다.중복 값도 가능하다.힙의 특징으로는 노드의 삽입 혹은 삭제 연산이 발생할 때만, 해당 노드가 옳바른 자리를 찾아간다.0-1. 최대 힙(Max Heap) 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리부모 노드의 키 값 >= 자식 노드의 키 값루트 노드: 키 값이 가장 큰 노드0-2. 최소 힙(Min Heap) 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리부모 노드의 키 값 루트 노드: 키 값이 가장 작은 노드1. 힙 연산최대 힙을 기준으로 설명을 할 예정이며, 최소 힙의 경우도 동일하게 동작한다.노드 하나의 삽입 / 삭제 연산은 시간 복잡도가 O(lonN)이고 최대값/최소값을..
