[이론] 힙(Heap)

힙(Heap)란?

---

여러개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조로  최대 힙(max heap)와, 최소 힙 (min heap)두 가지 종류로 나뉘게 된다

• 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

최대 힙의 예

• 최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

최소 힙의 예

 

최대 힙과 최소 힙은 항상 아래의 조건이 성립하게 된다

• 최대 힙 : $key(부모노드) >= Key(자식노드)$
• 최소 힙 : $key(부모노드) <= Key(자식노드)$

 

힙의 특징

1. 힙의 목적은 삭제 연산이 수행될 때마다 가장 큰/작은 값을 찾아내기만 하면 된다(가장 큰/작은 값은 루트 노드에 있음) 따라서 힙 안에서 데이터들은 느슨한 정렬 상태를 유지한다 즉, 전체 데이터를 정렬할 필요는 없다
2. 힙은 완전 이진 트리(complete binary tree)이며, 그 역은 성립하지 않는다

 

힙의 구현

---

구현에 사용되는 기본 개념

힙은 완전 이진 트리이므로, 각각의 노드에 아래처럼 차례대로 번호를 붙일 수 있다

이 번호를 배열의 인덱스로 생각하면 배열에 힙의 노드들을 저장할 수 있다. 따라서 힙을 저장하는 표준적인 자료구조는 배열이다

구현을 쉽게 하기 위해 배열의 첫 번째 인덱스 0은 사용하지 않으며, 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지않음을 유의하면서 배열을 이용하여 힙을 구현해보자 아래와 같이 완전 이진 트리에서와 마찬가지로 자식 노드와 부모 노드를 쉽게 알 수 있다

이는 아래와 같이 수식화 할 수 있다

• 왼쪽 자식의 인덱스 = (부모 인덱스) * 2
• 오른쪽 자식의 인덱스 = (부모 인덱스) * 2 + 1
• 부모의 인덱스 = (자식의 인덱스) / 2

 

삽입 연산

1. 새로운 노드를 힙의 마지막 노드로 삽입
2. 부모 노드와 비교하여 새로운 노드가 더 클 경우, 부모 노드와 위치 교환
   • 2의 과정을 더 큰 값을 가지는 부모 노드를 만날 때까지 반복
3. 더 큰 값을 가지는 부모 노드를 가지면 더 이상 교환하지 않고 종료 -> 새로운 노드가 적절한 위치에 있게 됨

삽입 연산 단계별 예시

삭제 연산

1. 우선순위가 가장 높은 노드, 즉 루트 노드 삭제
2. 빈 루트 노드 자리에 힙의 마지막 노드를 가져옴
3. 새로운 루트 노드를 자식 노드와 비교하여 자식 노드가 더 클 경우, 위치 교환
   • 3의 과정을 더 작은 자식 노드를 만날 때까지 반복
4. 더 작은 값을 가지는 자식 노드를 가지면 더 이상 교환하지 않고 종료 -> 새로운 루트 노드(원래의 힙의 마지막 노드)가 적절한 위치에 있게 됨

삭제 연산 단계별 예시

 

힙의 복잡도 분석

---

1. 삽입 연산의 시간 복잡도: $O(logn)$
   • 새로운 요소가 힙의 트리를 타고 올라가면서 부모 노드들과 교환하게 되는데, 최악의 경우 루트 노드까지 올라가야 함
   • 즉, 최악의 경우 트리의 높이에 해당하는 비교 연산 및 이동 연산이 필요 
   • 힙은 완전 이진 트리이므로, n개의 노드를 가진 힙의 높이는 $logn$, 즉 삽입 시 시간 복잡도는 $O(logn)$이다
2. 삭제 연산의 시간 복잡도: $O(logn)$ 
   • 삭제도 삽입과 마찬가지로, 최악의 경우 마지막 노드까지 비교하며 내려가므로 시간 복잡도는 $O(logn)$이다