Last updated
Was this helpful?
Last updated
Was this helpful?
힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 **완전이진트리(Complete binary tree)**를 기본으로 한 자료구조(tree-based structure)이다. (위키백과 )
그리고 다양한 문제를 푸는데에서 사용된다.
부모노드의 키값이 자식노드의 키값보다 항상 작거나 같다. key(부모노드) < key(자식노드)
부모노드의 키값이 자식노드의 키값보다 항상 크거나 같다. key(부모노드) > key(자식노드)
따라서 루트노드에는 항상 가장 큰 값이나 가장 작은 값이 저장되어 있기때문에 최대값 또는 최솟값을 O(1)만에 찾을 수 있다. 여기서 키값은 오로지 부모 자식노드간에만 성립한다.
n개의 노드를 가지고 있는 heap의 높이는 O(logn)이다. 힙은 완전이진트리이므로 노드의 개수로 깊이와 높이를 계산할 수 있다.
마지막 level을 제외하고는 각 레벨 i에 2^i개의 노드가 존재한다.
힙은 완전이진트리이므로 각 노드에 번호를 붙일 수 있다. 배열은 완전이진트리를 표현하기에 매우 효율적이다.
배열로 표현함으로써 부모노드와 자식노드를 찾기가 쉬워진다.
왼쪽 자식노드 인덱스 : 2*(부모노드 인덱스)
오른쪽 자식노드 2*(부모노드 인덱스)+1
노드 x의 부모 노드 인덱스는 (자식노드 인덱스)/2
로 알 수 있다.
주의사항 **index는 1부터 시작!**한다는 점을 주의해야한다.
가장 끝의 자리에 노드를 삽입한다.
그 노드와 부모 노드를 서로 비교한다.
규칙(최소힙, 최대힙)에 맞으면 그대로 두고, 그렇지 않으면 부모와 교환한다.
규칙에 맞을 때까지 1~3번 과정을 반복한다.
O(logn)
최댓값 혹은 최솟값이 저장된 루트 노드만 제거할 수 있다.
루트 노드를 제거한다.
루트 자리에 가장 마지막 노드를 삽입한다.
올라간 노드와 그의 자식 노드(들)와 비교한다.
조건에 만족하면 그대로 두고, 그렇지 않으면 자식과 교환한다.
최대 힙
부모보다 더 큰 자식이 없으면 교환하지 않고 끝낸다.
부모보다 더 큰 자식이 하나만 있으면 그 자식하고 교환하면 된다.
부모보다 더 큰 자식이 둘 있으면 자식들 중 큰 값과 교환한다.
최소 힙
부모보다 더 작은 자식이 없으면 교환하지 않고 끝낸다.
부모보다 더 작은 자식이 하나만 있으면 그 자식하고 교환하면 된다.
부모보다 더 작은 자식이 둘 있으면 자식들 중 작은 값과 교환한다.
조건을 만족할 때까지 4의 과정을 반복한다.
O(logn)
Graph Algorithm : , Prim's Minimum Spanning Tree(프림 최소 신장 트리)