Heap

Heap 자료구조는 일종의 Tree의 형식을 하고 있으며, Tree 중에서도 배열에 기반한 Complete Binary Tree(완전 이진 트리)이다.

배열에 트리의 값을 넣어줄 때, 0번째는 건너뛰고 1부터 루트노드가 시작된다. 이는 노드의 고유번호 값과 배열의 index를 일치시켜 혼동을 줄이기 위함이다.

힙에는 최소 힙(min heap)과 최대 힙(max heap) 두 종류가 있다.

Max Heap이란, 각 노드의 값이 해당 children의 값보다 크거나 같은 Complete Binary Tree(완전 이진 트리)를 말한다.[Min Heap은 그 반대.]

Max Heap에서는 Root node에 있는 값이 제일 크므로 최대값을 찾는데 소요되는 연산의 시간 복잡도는 O(1)이다. 그리고 Complete Binary Tree이기 때문에 배열을 사용하여 효율적으로 관리할 수 있다.
(즉, 배열의 장점 중 하나인 Random Access가 가능하다)
Min Heap에서는 최소값을 찾는데 소요되는 연산의 시간 복잡도가 O(1)이다.

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

[Heap 구조를 유지시키는 더 자세한 내용을 추가 예정.]