[자료구조/java] 힙 (Heap) - 배열 구현

* 힙 (Heap)

"완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해서 만든 자료구조"

- 최대 힙 (Max Heap) 키값이 가장 큰 노드를 찾기 위한 힙 (부모노드의 키값 >= 자식노드의 키값)

- 최소 힙 (Min Heap) 키값이 가장 작은 노드를 찾기 위한 힙 (부모노드의 키값 <= 자식노드의 키값)

   

  힙(Heap)구조 에서는 삽입, 삭제연산이 일반 트리구조의 삽입, 삭제 연산과는 조금 다르기 때문에 유의깊게 살펴볼 필요가 있다!

간단히 말하자면 삽입 연산은 아래에서 위로 비교 작업을 수행하고, 삭제연산은 루트노드를 삭제하고 마지막노드를 루트노드의 자리롤 올려 위에서 부터 아래로 비교 연산을 수행한다.

  따라서, 힙(Heap)구조에서는 각 키값의 인덱스를 확실히 알고 있는 것이 일의 효율을 높일 수 있기 때문에 순차 자료 구조 즉, 배열을 이용하여 구현하는 것이 좋다.

  일반적으로 힙(Heap) 자료구조를 이용해서 정렬에 이용하는 힙(Heap)정렬이 있는데, 힙 정렬은 삭제 연산을 이용해서 수행하게 되는데 이 부분에 대해서는 이후에 정렬에 대한 이야기를 하면서 살펴보도록 하자.

[ 이진 탐색 트리 삽입 연산 ]

힙(Heap)에서의 삽입 연산은 완전 이진 트리의 형태를 유지하기 위해서 현재의 마지막 노드의 다음 자리를 확장하여 만든 자리에 삽입할 노드를 임시로 저장한다. 이후 키값의 관계가 최대 힙이 될 수 있도록 재구성하기 위해 삽입한 노드의 키값과 부모 노드의 키값을 비교하면서 아래에서 위로 자리를 찾아가는 비교작업을 수행한다.

[ 이진 탐색 트리 삭제 연산 ]

힙(Heap)에서의 삭제 연산은 항상 루트 노드에 있는 원소를 삭제하여 반환한다. 그러므로 최대 힙에서의 삭제 연산은 키값이 가장 큰 원소를 삭제하여 반환하고, 최소 힙에서의 삭제 연산은 키값이 가장 작은 원소를 삭제하여 반환하게된다. 

삭제연산 역시 삽입 연산과 마찬가지로 완전 이진 트리의 형태를 유지하기 위해서 완전 이진 트리의 가장 마지막 노드를 삭제한 루트노드의 자리에 임시로 삽입하여, 자식노드와 비교작업을 수행하면서 제 위치를 찾을 수 있도록 한다.