#14. 힙(Heap)

힙(Heap)

• 완전 이진 트리의 일종으로, 우선순위 큐를 위하여 만들어진 자료구조
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조

 

우선순위 큐

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

---

힙의 종류

 

최대 힙(max heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• key(부모 노드) >= key(자식 노드)

 

 

최소 힙(min heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
• key(부모 노드) <= key(자식 노드)

---

힙의 구현

 

힙의 삽입

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

/* 현재 요소의 개수가 heap_size인 힙 h에 item을 삽입한다. */
// 최대 힙(max heap) 삽입 함수

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; // 새로운 노드를 삽입
}

 

 

힙의 삭제

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

// 최대 힙(max heap) 삭제 함수

element delete_max_heap(HeapType *h){
  int parent, child;
  element item, temp;

  item = 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[parent] = temp;
  // 최댓값(루트 노드 값)을 반환
  return item;
}

 

---

References

 

gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

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