히프1 [자료구조] Binary Heap(히프)와 Priority Queue(우선순위 큐) - CS면접 대비 이번 글에서는 우선순위 큐(Priority Queue) 구현을 위해 사용되는 이진 히프(Binary Heap)에 관한 내용을 정리해보고자 한다. 일반적인 배열로 우선순위 큐를 구현하는 경우 삽입에 O(N) 정렬에 O(log N) 시간이 소요되는 반면, 히프로 구현하는 경우 enqueue와 dequeue 연산을 O(log N) 시간에 가능하게 해준다. 이진 히프(Binary Heap) [1] 최대/최소 히프의 정의 최대 히프(max heap)는 최대 트리(max tree)*이면서 완전 이진 트리(complete binary tree)이다. 최소 히프(min heap)는 최소 트리(min tree)*이면서 완전 이진 트리(complete binary tree)이다. * 최대(최소) 트리 : 각 노드의 키 값.. 2021. 11. 30. 이전 1 다음 반응형
