자료구조1 [자료구조] 우선순위 큐와 최대힙, 최소힙(Max Heap, Min Heap) Complete Binary Tree 완전 이진 트리란 각 노드가 최대 2개의 자식 노드를 갖는 트리 형태의 자료구조로서 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 한다. 또한 최하단 레벨의 노드는 좌측만 노드가 채워져 있거나 좌측과 우측 모두 채워져 있어야 하며, 노드를 삽입할 때에는 최하단 좌측 노드부터 차례대로 삽입해야 한다. Heap 힙이란 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리 자료구조를 갖으며 이러한 특성으로 여러개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾을 수 있다. 중복된 값을 허용하지 않는 이진 탐색 트리와는 달리 힙 트리에서는 중복 값을 허용한다는 특징이 있다. 최대 .. 2023. 5. 23. 이전 1 다음