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

Dragony·2019년 12월 17일
1

자료구조

목록 보기
3/10
post-custom-banner

[들어가기 전]

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

data-structure-heap-priorityqueue.png

자료구조 '힙' 이란?

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

힙(heap)의 종류

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

types-of-heap.png

힙(heap) 의 구현

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

heap-index-parent-child.png

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

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

HeapType heap1;

힙(heap)의 삽입

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

maxheap-insertion.png

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. 힙을 재구성한다.

maxheap-delete.png

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;
}
 
profile
안녕하세요 :) 제 개인 공부 정리 블로그입니다. 틀린 내용 수정, 피드백 환영합니다.
post-custom-banner

1개의 댓글

comment-user-thumbnail
2023년 9월 21일

잘 읽었습니다! 출처 남기고 제 벨로그에 참고해서 정리해도 괜찮을까요??

답글 달기