[자료구조] 힙(heap) - 최대힙(max heap)의 삽입과 삭제

[들어가기 전]

• 우선순위 큐: 우선순위의 개념을 큐에 도입한 자료구조
  
  데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다.
  우선순위 큐의 이용사례
  a. 시뮬레이션 시스템
  b. 네트워크 트래픽 제어
  c. 운영 체제에서의 작업 스케쥴링
  d. 수치 해석적인 계산
  * 우선순위 큐는 배열, 연결리스트, 힙으로 구현 가능하다.
  

자료구조 '힙' 이란?

• 완전 이진 트리의 일종으로, 우선순위 큐를 위하여 만들어진 자료구조이다.
• 여러개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
• 우선순위가 가장 높은 데이터가 제일 앞(루트)에 위치한다.
• 부모는 자식보다 우선순위가 더 높은 데이터가 배치된다.
• 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다.
  • 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)

힙(heap)의 종류

• 최대 힙(max heap)
  * 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
  • key(부모노드 >= key(자식노드)
• 최소 힙(min heap)
  * 부모노드의 키 값이 자식노드의 키 값보다 작거나 같은 완전 이진 트리
  • key(부모노드) <= key(자식노드)

힙(heap) 의 구현

• 힙을 저장하는 표준적인 자료구조는 배열이다.
• 구현을 쉽게 하기 위하여 배열의 첫 인덱스인 0은 사용되지 않는다.
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
  * 예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.
  
• 힙에서 부모노드와 자식 노드의 관계
  왼쪽 자식의 인덱스 = (부모의 인덱스) 2
  • 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
  • 부모의 인덱스 = (자식의 인덱스) / 2

#define MAX_ELEMENT 200
typedef struct{
	int key;
} element;

typedef struct{
	element heap[MAX_ELEMENT];
    int heap_size;
} HeapType;

HeapType heap1;

힙(heap)의 삽입

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

void insert_max_heap(HeapType *h, element item){
	int i;
    i = ++(h->heap_size); //힙 크기를 하나 증가
    
    /* 트리를 거슬러 올라가면서 부모 노드와 비교하는 과정 */
    // i가 루트노드(index:1)이 아니고, 삽입할 item의 값이 i의 부모노(index:i/2) 보다 크면
    while((i!=1) && (item.key > h->heap[i/2].key)){
    	//i번째 노드와 부모 노드를 교환한다.
        h->heap[i] = h->heap[i/2];
        //한 레벨 위로 올라간다.
        i/=2;
       }
      h->heap[i] = item; //새로운 노드를 삽입
   }

힙(heap)의 삭제

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

element delete_max_heap(HeapType *h){
	int parent, child;
    element item, temp;
    
    itemp = h->heap[1]; // 루트 노드 값을 반환하기 위해 item에 할당
    temp = h->heap[(h->heap_size)--]; // 마지막 노드를 temp에 할당하고 힙 크기 감소
    parent = 1;
    child = 2;
    
    while(child <= h->heap_size) {
    //현재 노드의 자식 노드 중 더 큰 자식 노드를 찾는다. (루트 노드의 왼쪽 자식 노드(index: 2)부터 비교 시작)
     if( (child < h->heap_size) && ((h->heap[child].key) < h->heap[child+1].key) ){
      child++;
    }
    //더 큰 자식의 노드보다 마지막 노드가 크면, while 문 중지
    if ( temp.key >= h->heap[child].key ){
    	break;
     }
     
     //더 큰 자식 노드보다 마지막 노드가 작으면, 부모노드와 더 큰 자식노드를 교환
     h->heap[parent] = h->heap[child];
     parent = child;
     child *= 2;
  }
  
  //마지막 노드를 재구성한 위치에 삽입
  h->heap[parnet] = temp;
  // 최댓값(루트 노드 값)을 반환
  return itemp;
}