힙(heap)

힙은 다음과 같은 시간 복잡도를 만족해야 한다.

 

O(1): 최대 원소에 즉각적으로 접근

O(log N): 원소 삽입에 대한 시간 복잡도

O(log N): 최대 원소 삭제에 대한 시간 복잡도

또한 이를 위해서는 완전 이진 트리(complete binary tree)를 사용해야 한다.

완전 이진 트리란 각 노드가 위쪽과 왼쪽부터 순서대로 채워진 이진 트리를 말한다.

완전 이진 트리를 벡터에 저장한 경우, 만약 부모 노드가 i번째 배열 원소로 저장되어 있다면 자식노드는 2*i+1또는 2*i+2번째 인덱스로 접근하면 된다.

 

최대 원소에 즉각적으로 접근 가능한 힙을 최대 힙(max heap)이라 하며 이를 위해 부모 노드를 두 자식 노드보다 크도록 한다.

반대로 최소 원소에 즉각적으로 접근 가능한 힙을 최소 힙(min heap)이라 하며 최대 힙과는 반대로 만들면 된다.