완전이진트리 - 힙

힙(이진힙)

---

힙은 완전이진트리의 한 종류로

최대값 기준으로 정렬된 최대힙과 최솟값 기준으로 정렬된 최소힙이 있다.

최대힙은 부모노드가 항상 자식노드 보다 값이 크며 루트 노드에 최대값이 매핑되어있다.

최소힙은 부모노드가 항상 자식노드 보다 값이 작으며 루트 노드에 최솟값이 매핑되어있다.

정렬기준에 따른 첫번째 값이 루트 노드에 존재하여 우선순위 조회 탐색시에 사용된다.

자바에서 우선순위 큐에 사용된 자료구조 또한 힙이다.

 

[힙의 특징]

• 완전 이진트리
• 부모노드의 키값과 자식노드의 키값 사이에는 대소관계 성립
  • 키값 대소관계는 오로지 부모자식 간에 성립되며 형제 사이에는 대소관계가 없음

 

heapify

---

힙이 규칙을 지키고 균형을 유지하기 위해 사용되는 연산이 heapify이다.

 

최대힙에서 heapify 연산이 어떻게 수행되는지 알아보자.

1.  두 자식노드와 비교하여 자식 노드 중 큰 값이 존재하면 가장 큰 노드를 부모노드와 교체한다.
2. 교체한 노드에 대해서도 위 규칙을 반복하여 적용한다.

* heapify는 부모노드에서 자식노드로 향하는 방향을 갖는다.

 

Build Heap

---

완전이진트리를 힙으로 전환하는 과정을 Build Heap이라고 한다.

마지막 레벨 전 단계 레벨부터 차례대로 heapify 과정을 수행하는 방식으로 완전이진트리는 힙으로 전환할 수 있다.

 

구체적인 구현 과정은

리프노드의 부모노드 중 마지막 부모노드부터 역순으로 탐색하며 heapify 과정을 수행한다.

완전이진트리에서 리프노드의 부모노드 중 마지막 부모노드의 인덱스는 항상 (n/2)+1이다.

따라서 (n/2)+1 부터 자식 노드와 대소 비교를 하여 heapify 수행 과정을 반복 진행하면 된다.

 

extract (루트노드 추출)

---

힙은 루트노드에 최댓값 또는 최솟값이 존재하므로

우선순위 큐와 같은 자료구조에서 많이 사용된다.

이때 루트 노드를 추출하는 과정을 알아보자.

 

 

1. 루트노드 삭제
2. 마지막 노드를 루트노드 자리로 교체
3. 루트노드부터 다시 heapify 과정 수행

 

삽입연산

---

Increase value

먼저 삽입연산에 사용되는 Increase value에 대해 알아보자.

Increase value는 최대힙의 삽입연산에서 사용되는 연산이다.

최소힙에서는 Decrease Value를 사용한다.

1. 특정 노드의 값을 증가시킨다.
2. 부모노드와 대소 관계를 비교하여 부모노드보다 크면 노드를 교체한다.
   * 최대힙은 이미 자식노드보다 크기가 크므로 자식노드와 비교하지 않는다.
3. 힙 규칙이 지켜질 때까지, 자식노드에서 부모노드 방향으로 해당 절차를 반복 적용한다.

* heapify와는 다르게 자식노드에서 부모노드의 방향으로 진행된다.

 

삽입연산

1. 리프노드의 마지막 위치에 최솟값으로 노드를 추가한다.
2. 추가하려던 값으로 노드의 값을 증가시켜 Increase Value 과정을 수행한다.

 

삭제연산

---

 

1. 삭제할 노드의 값을 최대값으로 증가시킨다.
2. Increase Value 연산이 실행되어 삭제할 노드가 루트노드에 위치하게 된다.
3. 루트노드를 제거하는 extract 연산을 수행

위와 같은 절차를 통해 최대힙의 속성을 유지할 수 있다.

 

정리

---

힙은 완전 이진 트리의 형태를 가지며, 부모 노드의 우선순위가 자식 노드의 우선순위보다 항상 높은 특징을 갖는다. 

이로인해 루트노드에는 항상 우선순위가 가장 높은 값이 존재하며 조회 시간복잡도 O(1)을 갖는다.

또한 위에서 알아본 삽입, 삭제 연산이 비교적 단순하여 균형을 이루기 좋은 구조를 갖추고 있다.