목록2025/03/12 (1)
나만의 작은 도서관
[Data Structure] 최대 / 최소 힙
최대 / 최소 힙이란?최대 / 최소 힙은 이진 트리(Binary Tree, BST)의 한 종류로, 우선순위가 높은 값에 빠르게 접근하기 위해 고안된 방법이다. 각 노드는 2가지 규칙을 따라야 하며, 규칙은 아래와 같다.조건 #1. 완전 이진 트리여야 한다.조건 #2. 모든 노드의 키 값은 자식 노드의 키 값보다 우선순위가 높거나 같아야한다. 조건 2에서 큰 값이 우선 순위가 높다면 최대 힙, 작은 값이 우선 순위가 높다면 최소 힙이 된다. 최대 / 최소 힙의 특징완전 이진 트리이다. 왼쪽 서브 트리와 오른쪽 서브트리는 서로 관련이 없다. 오로지 부모 노드랑만 관련있다.중복값을 허용한다.완전 이진 트리(Complet Binary Tree)란? 이진 트리에 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 ..
Common/CS-일반
2025. 3. 12. 00:43