[C++] 힙 코드 구현 방법 heap

heap에 대해 배우기 전에 우선순위 큐 개념부터 잡고 가야한다.

 

▣ 우선순위 큐 priority queue

 ●  큐

• 먼저 들어간 데이터가 먼저 삭제되는 자료구조 형태다.
• 먼저 줄을 선 사람이 먼저 서비스를 받는 구조다.

 ● 우선순위 큐

• 대기 리스트에서 항상 우선순위가 높은 사람이 먼저 서비스를 받는 구조다.
• 삭제할 때만 우선순위를 고려해서 삭제한다. 먼저 들어온 순서 상관없이.
• 예를 들어서, 버스를 타려고 줄 서 있는데, 다리가 불편한 아이에게 양보해서 먼저 탈 수 있게 하는 방법이다.

 ● 우선순위 큐 배열 구현

  ▶ 작동방식

1. 삭제 명령이 실행되면 큐의 대기열(저장된 데이터) 중 우선순위가 가장 높은 데이터가 삭제된다.
2. 나머지 데이터들이 어떤 순서로 저장되는 지는 문제가 되지 않는다.

  ▶ 데이터 삭제(Delete_q()), 데이터 삽입(Add_q(3))

• Delete_q()에 의해 큐의 front에 있던 값이 우선순위가 가장 높으면 바로 삭제하고, 아니면 나머지 데이터 중 가장 우선순위가 높은 값을 front 위치의 값과 자리를 바꾸고 front 값을 삭제한다.

---> 이 방식은 삭제할 때마다 큐 대기열의 모든 데이터의 우선순위를 확인해야 하기 때문에 데이터 수가 많아질수록 계산량이 많아진다는 단점이 있다.

---> 힙이 우선순위 큐를 구현하기 가장 좋은 자료구조라고 알려져있다. 왜 그런지 한 번 알아보자.

 

▣ 힙 heap

 ●  힙

• 피라미드 모양으로 쌓아 올린 더미 형태의 자료구조다.
• 쌓아놓은 더미에서 항상 가장 위에 있는 값을 우선 꺼내는 구조다.
• 부모-자식 노드 사이에서 정렬된 완전이진트리로 부모노드는 자식노드보다 우선순위가 높다.
• 우선순위 큐 구현 시 가장 성능이 좋은 자료구조다.

 

 ●  힙의 종류

  ▶ 최소 힙 min-heap

• 루트노드가 가장 작은 값을 가지는 heap을 말한다.
• tree의 모든노드가 자식 노드보다 작은 값을 가지는 tree 구조다.
• tree의 레벨에 따라 데이터가 순서를 갖지는 않는다.
• 탐색 tree처럼 왼쪽 노드와 오른쪽 노드 사이에 크기 제한이 없다.
  
      2                2 
  4     5          5     4    노상관
  
  
• 루트가 가장 작은 값을 갖고 부모는 자식보다 항상 작은 값을 가진다. 

  ▶ 최대 힙 max-heap

 

• 루트노드가 가장 큰 값을 가지는 heap을 말한다.
• tree의 모든노드가 자식 노드보다 큰 값을 가지는 tree 구조다.
• tree의 레벨에 따라 데이터가 순서를 갖지는 않는다.
• 탐색 tree처럼 왼쪽 노드와 오른쪽 노드 사이에 크기 제한이 없다.
• 루트가 가장 큰 값을 갖고 부모는 자식보다 항상 큰 값을 가진다. 

 

 

 

 

 ●  힙의 추상자료형

우선순위 큐를 구현할 때 힙을 이용하니까 훨씬 좋다~ 방법을 알아보자.

  ▶ 힙 객체

• 부분적으로 정렬된 완전이진트리로 부모노드는 자식노드보다 우선순위가 높다.

  ▶ 연산 방법

1. insert(element) ::= 힙에 데이터 삽입
2. remove() ::= 힙(루트)에서 데이터 삭제
3. peek() ::= 힙(루트)에서 데이터 읽기
4. isEmpty() ::= 힙이 비었는지 확인
5. size() ::= 힙에 저장한 데이터 개수 확인

 

 ●  힙 구현 방법

1. 배열 이용 -> '완전이진트리'라서 배열로 구현해도 기억장소 낭비는 없다.
   
   ++) 연결 리스트보다 실행 속도 면에서 효율적이고 기억장소 측면에서 장점을 가진다.
         연결 리스트는 노드에 링크(포인터) 공간까지 필요하므로...
   
   

 ● 힙 노드 삭제

• 힙에서 삭제 = front가 가리키는 노드 삭제하기 = 루트노드 삭제!
• 코드 구현

 

1. 루트노드 삭제

typedef struct{
  int heap[MAX_Data];
  int heap_size;
};

int deleteHeap(HeapType *h){
  int parent, child;
  int item, temp;
  
  item = h->heap[1];
  temp = h->heap[(h->heap_size)];
  parent = 1;
  child = 2;

 

2. 마지막 노드를 루트로 이동

while(child <= h->heap_size){
  if((child < h->heap_size) && (h->heap[child] > h->heap[child+1]))
     child++;
  if(temp <= h->heap[child])
     break;
  h->heap[parent] = h->heap[child];
  parent = child;
  child *= 2;
}

 

마지막 노드를 루트노드로 위치했을 때 아래 노드와 크기관계가 맞지 않으면, 루트 노드의 자식 노드 중 더 작은(큰) 노드를 루트노드와 위치 바꾼다.

23이 자식노드보다 크기 때문에 다시 또 자식노드와 위치를 바꿔준다... (이 과정 반복스)

 

 ● 힙 노드 삽입

• 마지막 노드에 노드 삽입
• 완전이진트리가 되도록 삽입 후 힙이 되도록 상하관계를 따져서 위치를 조정해야 한다.

while((i != 1) && (item < h->heap[i/2]) {
   h->heap[i] = h->heap[i/2];
   i /= 2;
}

• 크기관계가 모두 정렬되고 나면 비로소 힙이 된다.

♠ 선형자료구조로 우선순위 큐를 구현했으면 삽입/제거 연산에서 일일이 다 비교해서 최솟값/최댓값을 찾아내야 하는데, 힙으로 구현하면 몇 번만 비교하면 되니까 연산량이 확 준다.