목록힙 (1)

늘 겸손하게

CS - Data Structure - Heap (힙)

Heap(힙)은 최댓값 및 최솟값을 빠르게 찾아내기 위한 자료구조로 우선순위 큐(Priority Queue)를 구현하는데 사용됩니다. Heap은 완전 이진 트리로 최대 두 개의 자식 노드를 가질 수 있습니다. [ 완전 이진 트리 ] 완전 이진 트리는 이진 트리의 한 종류로 단말 노드(leaf node)를 제외한 모든 노드는 2개의 자식을 가지거나 왼쪽 자식만을 가져야만 합니다. 예로 값 40, 50, 30을 가지는 단말 노드 (leaf node)를 제외한 모든 노드는 2개의 자식 노드를 가지고 있으므로 위 트리는 완전 이진 트리 입니다. 반면에 위와 같은 트리에서 값 30을 가지는 노드는 오른쪽 자식 노드 밖에 없으므로 위 트리는 완전 이진 트리가 아닙니다. 힙에는 두 가지 종류가 있습니다. 1. Min..
Computer Science/Data Structure 2022. 9. 15. 17:31
이전 Prev 1 Next 다음