Binary Heap

Binary Heap은 자료구조의 일종으로 Tree의 형식을 띄고 있다. Tree 중에서도 배열에 기반한 Complete Binary Tree이다. 배열에 트리의 값들을 넣어줄 때에 0번째는 건너 뛰고 index 1부터 루트 노드가 시작된다. 이는 노드의 고유번호 값과 배열의 index를 일치시킴으로써 혼동을 막기 위함이다. 힙(Heap)에는 최대힙(Max Heap), 최소힙(Min Heap)이 있다.

Max Heap

최대힙이란 각 노드의 값이 자신의 자식 노드의 값보다 크거나 같은 Complete Binary Tree를 말한다. 파이썬에서는 heapq로 구현 가능하고 값을 넣을 때에 - 부호를 붙여서 넣는다. (heapq는 오름차순 정렬이기 때문에 기본적으로는 최소힙을 제공)

최대힙에서는 루트 노드의 값이 가장 크기 때문에 최대값을 찾는데 소요되는 연산의 시간 복잡도가 O(1)이다. 그리고 Complete Binary Tree이기 때문에 배열을 사용하여 효율적으로 관리할 수 있다. 이는 random access가 가능하다는 것을 의미한다.

heap의 구조를 유지하기 위해서는 제거된 루트 노드를 대체할 다른 노드가 필요하다. 이때 heap은 맨 마지막 노드를 루트 노드로 대체시킨 후, heapify 과정을 거쳐 heap의 구조를 유지한다. 이런 경우에는 최대값에 접근하기 위해 O(log n)의 시간 복잡도가 발생한다.

Min Heap

최소힙이란 각 노드의 값이 자신의 자식 노드의 값보다 작거나 같은 Complete Binary Tree를 말한다. 파이썬에서는 heapq로 구현 가능하고 heapq는 기본적으로 오름차순 정렬을 제공하기 때문에 값을 넣기만 하면 최소힙으로 사용 가능하다.

최소힙에서는 루트 노드의 값이 가장 작기 때문에 최소값을 찾는데 소요되는 연산의 시간 복잡도가 O(1)이다. 그리고 Complete Binary Tree이기 때문에 배열을 사용하여 효율적으로 관리할 수 있다. 이는 random access가 가능하다는 것을 의미한다.

heap의 구조를 유지하기 위해서는 제거된 루트 노드를 대체할 다른 노드가 필요하다. 이때 heap은 맨 마지막 노드를 루트 노드로 대체시킨 후, heapify 과정을 거쳐 heap의 구조를 유지한다. 이런 경우에는 최소값에 접근하기 위해 O(log n)의 시간 복잡도가 발생한다.