Heap 개념 및 구현 (c++)

🌿개념

heap은 부모와 자식간의 대소관계가 명확한 이진완전트리 다.

• maxheap의 경우 항상 부모가 자식보다 크다.
• minheap의 경우 항상 부모가 자식보다 작다.

이러한 heap을 통해 우선순위 큐(priority_queue) 구현이 가능하다.

또한 이진완전트리기 때문에 선형 배열의 인덱스로 부모 자식 관계의 표현 가능하다.

• root 는 1
• n의 parent는 n / 2
• n의 child는 n*2 와 n*2 + 1

heap 정적할당

#define HEAP_SIZE 1000

int heap[HEAP_SIZE];
int heapCnt;

STL의 priority_queue를 쓰지않고 heap을 직접구현하는 이유는 시간 복잡도를 줄이기 위해서이므로
보통 위와같이 정적할당으로 구현한다.

🌿연산

heap에서 필요한 필수 연산은 딱 두가지다.

push(data)

heap에 데이터를 집어넣는 연산이다.

heap에 데이터를 집어넣은 후에도 heap의 구조를 유지해야하기 때문에 다음과 같은 처리를 한다.

1. heap 배열의 맨 끝에 data를 추가
   (트리구조로 보면 추가된 노드는 최하단 최우측에 추가됨.)

2. 추가된 노드가 루트노드 (1) 이면 종료

3. 부모 노드보다 우선순위가 크면 부모 노드와 swap.

4. 2로 jump.

코드

void push(int data) {
  heap[++heapCnt] = data;
  int child = heapCnt, parent = heapCnt / 2;

  while(parent) {
    if(heap[parent] < heap[child]) break;
    swap(heap[parent], heap[child]);
    child = child / 2;
    parent = parent / 2;
  }
}

pop()

heap에서 데이터를 하나 빼내는 연산이다.

항상 root노드를 빼내며 root노드는 모든 노드의 조상노드이기 때문에
가장 우선순위가 높은 노드다.

데이터를 빼낸 후에도 heap의 구조를 유지해야하므로 다음과 같은 처리를 한다.

1. 루트노드(1)와 맨 끝 노드(heapCnt)를 swap한다. heapCnt--

(이러면 이제 루트노드만 heap구조에 맞게 이동시키면 된다.)

2. 현재의 root노드를 current로 잡고

3. current의 자식들 중 우선순위가 높은 애와 current를 비교.

4. current의 우선순위가 더 높다면 종료, 아니라면 swap.

5. 3번으로 점프

코드

int pop() {
  int data = heap[1];
  swap(heap[1], heap[heapCnt]);
  heapCnt--;

  int parent = 1;
  int child = parent * 2;
  if(heapCnt >= child + 1 && heap[child + 1] < heap[child]) 
    child += 1;
  
  while(child <= heapCnt) {
    if(heap[parent] > heap[child]) 
      swap(heap[parent], heap[child]);
    parent = child;
    child = parent * 2;
    if(heapCnt >= child + 1 && heap[child] > heap[child + 1]) 
      child += 1;
  }
  
  return data;
}

🌿추가 말.

heap은 이렇게 글로 보는게 아니라 그림으로 보면 너무 쉽게 이해된다.

손으로 직접 empty heap부터 시작하여 두가지 연산 pop과 push를 그려보면 좋을 것 같다.

heap을 이용하면 priority_queue뿐만아니라 heap sort를 구현할 수 도 있다.

빈 heap에 배열의 data를 하나씩 집어넣고 하나씩 빼면 정렬된 순서로 뽑을 수 있다. 근데 이 경우 추가 heap공간이 필요하다.

그래서 heapify 라는 또 다른 힙 연산을 이용하여 배열 그 자체를 힙으로써 사용할 수 있다. (추가공간 필요 X)

push 와pop 이 그렇듯이 heapify 도 아주 쉬운 연산이다. (걱정 ㄴㄴ)

🌿minheap 구현 전체 코드

#include <iostream>
#define HEAP_SIZE 1000

using namespace std;

int heap[HEAP_SIZE];
int heapCnt;

void swap(int & a, int & b) {
  int tmp = a;
  a = b;
  b = tmp;

  return;
}

void push(int data) {
  heap[++heapCnt] = data;
  int child = heapCnt, parent = heapCnt / 2;

  while(parent) {
    if(heap[parent] < heap[child]) break;
    swap(heap[parent], heap[child]);
    child = child / 2;
    parent = parent / 2;
  }
}

int pop() {
  int data = heap[1];
  swap(heap[1], heap[heapCnt]);
  heapCnt--;

  int parent = 1;
  int child = parent * 2;
  if(heapCnt >= child + 1 && heap[child + 1] < heap[child]) 
    child += 1;
  
  while(child <= heapCnt) {
    if(heap[parent] > heap[child]) 
      swap(heap[parent], heap[child]);
    parent = child;
    child = parent * 2;
    if(heapCnt >= child + 1 && heap[child] > heap[child + 1]) 
      child += 1;
  }
  
  return data;
}


int main() {

  push(10);
  push(2);
  push(8);
  push(7);
  push(100);
  push(20);
  push(5);
  push(3);
  push(1);
  push(500);
  push(400);

  while(heapCnt) {
    cout << pop() << endl;
  }

  return 0;
}

결과

$ ./a.out        
1
2
3
5
7
8
10
20
100
400
500