자료구조 (9), Priority Queue

Heap 1. Heap 1) Heap이란? - Heap은 Priority Queue와 밀접한 관계가 있다. Priority Queue 내부에 Heap을 사용하는 경우가 많다. 힙은 노드에는 우선순위에 관한 자료를 추가적으로 가지고 있다. - 힙은 이진트리이지만 BST는 아니다. BST는 크기의 대소 관계에 따라 데이터를 삽입한다. - 이진트리는 자식이 최대 두개까지 있는 것을 의미한다. 또한 가장 깊은 노드에 있는 것을 제외한 노드는 모두 2개의 자식이 있고, 가장 하단에 있는 노드는 좌하단부터 노드를 채워간다. 최대힙은 모든 노드는 자기의 자식보다 더 크거나 같은 트리를 가지게 된다. 따라서 루트에 있는 값만 확인하면 된다. - 왼쪽의 예시는 힙은 아니지만 오른쪽은 최대힙이다. 2) Heap의 특징 -..

2022.06.21