Velog Velog

힙(Heap) 이란? : 최댓값과 최솟값을 빠르게 찾기 위해 고안된 자료구조 - 각 노드의 key값이 해당 노드의 자식노드의 key값보다 작지 않거나 크지 않은 완전 이진트리 - 키 값의 대소관계는 부모-자식 노드 사이 간에만 성립하며 형제 노드 사이에는 영향을 미치지 않음 - 자식노드의 최대 개수는 힙의 종류에 따라 다르지만 이진트리에서는 최대 2개 (완전이진트리를 사용한다고 가정하자.) - i번째 노드의 자식노드가 2개인데 왼쪽 자식노드는 2i, 오른쪽 자식노드는 2i+1이고, 부모노드는 i/2가 된다. * 최대 힙 (max heap) : 각 노드의 키 값이 그 자식노드의 키 값보다 작지 않은 힙 key(T.parent(v)) > key(v) * 최소 힙 (min heap) : 각 노드의 키 값이 그..