JUINTINATION

힙이란? 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 다음과 같은 규칙을 갖는 완전이진트리를 기본으로 한 자료구조 A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다. 힙에는 두가지 종류가 있다. 최대 힙: 부모노드의 키 값이 자식노드의 키 값보다 항상 큰 힙 최소 힙: 부모노드의 키 값이 자식노드의 키 값보다 항상 작은 힙 대부분의 경우는 자식노드의 개수가 최대 2개인 이진 힙(binary heap)을 사용 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 루트 노드에 오게 되는 특징이 있음 이를 응용하여 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다. 힙의 주요 연산 최소 힙을 기준으로 힙의 주요 연산은 다음과 같다. ..