이진 힙

이진 힙(Heap)이란?

완전 이진 트리의 일종을 우선순위 큐를 위하여 만들어진 자료구조입니다.

여기서, 우선순위 큐를 위해서 만들어졌다고 했는데, 우선순위 큐가 무엇인지 간단히 소개하고 넘어가겠습니다.

우선순위 큐(Priority Queue)

우선순위의 개념을 큐에 도입한 자료 구조라고 생각하면 됩니다.

기존의 큐(Queue)같은 경우에는 가장 먼저 들어온 데이터가 먼저 나가는 형태인 FIFO방식을 사용한는데 우선순위 큐(Priority Queue)의 경우에는 가장 우선순위가 높은 데이터가 먼저 나간다고 보면 됩니다.

우선순위 큐의 이용사례

• 시물레이션 시스템
• 네트워크 트래픽 제어
• 운영 체제에서의 작업 스케쥴링
• 수치 해석적인 계산

우선 순위 큐는 배열, 연결리스트, 힙으로 구현이 가능합니다. 이 중에서 힙(Heap)으로 구현하는 것이 가장 효율적입니다.

특징

1. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조

2. 일종의 반정렬 상태(느슨한 정렬 상태)를 유지
   ⇒ 큰 값이 상위 레벨에 잇고 작은 값이 하위 레벨에 있다는 정도
   ⇒ 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리

3. 중복된 값을 허용 (이진 탐색 트리에서는 중복된 값을 허용 X)

종류

1. 최대 힙(max heap)
   a. 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
   b. key(부모 노드) ≥ key(자식 노드)
2. 최소 힙(min heap)
   a. 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
   b. key(부모 노드) ≤ key(자식 노드)

구현 방식

• 힙을 저장하는 표준적인 자료구조는 배열입니다.

• 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용 X

• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.

  • 예를 들어 루트 노드의 오른쪽 노드의번호는 항상 3

• 힙에서의 부모 노드와 자식 노드의 관계

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

  

  힙(Heap)의 삽입

1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
2. 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.

• 아래의 최대 힙(max heap)에 새로운 요소 8을 삽입해보자.

코드는 다음과 같다.

/* 최대힙 삽입 */
void insert_max_heap(int x){
maxHeap[++heapSize] = x; // 힙 크기를 하나 증가하고 마지막 노드에 x를 넣는다.

for (int i=heapSize; i>1; i/=2) {
  // 마지막 노드가 자신의 부모 노드보다 크면 swap
  if (maxHeap[i/2] < maxHeap[i]) {
    swap(i/2, i);
  } else {
    break;
  }
}

힙(Heap)의 삭제

1. 최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제된다.
   1. 최대 힙(max heap)에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다.
2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.
3. 힙을 재구성한다.

• 아래의 최대 힙(max heap)에서 최댓값을 삭제해보자.

/* 최대힙 삭제 */
int delete_max_heap(){
if (heapSize == 0) // 배열이 빈 경우
  return 0;

int item = maxHeap[1]; // 루트 노드의 값을 저장한다.
maxHeap[1] = maxHeap[heapSize]; // 마지막 노드의 값을 루트 노드에 둔다.
maxHeap[heapSize--] = 0; // 힙 크기를 하나 줄이고 마지막 노드를 0으로 초기화한다.

for (int i=1; i*2<=heapSize;) {
  // 마지막 노드가 왼쪽 노드와 오른쪽 노드보다 크면 반복문을 나간다.
  if (maxHeap[i] > maxHeap[i*2] && maxHeap[i] > maxHeap[i*2+1]) {
    break;
  }
  // 왼쪽 노드가 더 큰 경우, 왼쪽 노드와 마지막 노드를 swap
  else if (maxHeap[i*2] > maxHeap[i*2+1]) {
    swap(i, i*2);
    i = i*2;
  }
  // 오른쪽 노드가 더 큰 경우, 오른쪽 노드와 마지막 노드를 swap
  else {
    swap(i, i*2+1);
    i = i*2+1;
  }
}
return item;

---

Reference

• [자료구조] 힙(heap)이란 - Heee's Development Blog