힙(Heap)

데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)

• 힙은 최대힙과 최소힙으로 나뉘어진다. 최대힙은 자식 노드보다 부모 노드의 값이 크고, 최소힙은 자식 노드보다 부모 노드의 값이 작다.
• 노드가 왼쪽부터 채워지는 완전 이진 트리 형태를 가진다.
• 중복을 허용한다.

<aside> 💡 완전 이진 트리 (Complete Binary Tree)란?

</aside>

이진 트리에 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리이다.

힙 vs 이진 탐색 트리

<aside> 💡 이진 탐색 트리(Binary Search Tree)란?

</aside>

이진 탐색과 연결리스트(linked-list)를 결합한 자료구조의 일종이다.이진 탐색의 효율적인 탐색 능력을 유지하면서 빈번한 자료의 입력과 삭제를 가능하도록 한다.각 노드에서 왼쪽의 자식 노드는 해당 노드보다 작은 값으로, 오른쪽의 자식 노드는 해당 노드보다 큰 값으로 이루어져 있다.

공통점

• 모두 완전 이진 트리이다.

차이점

• (최대힙의 경우) 힙은 각 노드의 값이 자식 노드보다 크거나 같다.
• 이진 탐색 트리는 각 노드의 왼쪽 자식은 더 작은 값으로, 오른쪽 자식은 더 큰 값으로 이루어져있다.왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
• 힙은 왼쪽 노드의 값이 크든 오른쪽 노드의 값이 크든 상관 없다.
• 힙은 최대/최소 검색을, 이진 탐색 트리는 탐색을 위한 구조이다.

힙의 동작