힙(heap)의 삽입과 삭제

힙(heap)의 삽입과 삭제

최대 힙을 기준으로 설명한다.

힙의 삽입
힙은 배열로 구현된 완전 이진 트리이다. 배열의 끝 인덱스부터 시작하여, 그 부모 노드와 비교하며
해당 노드보다 키 값이 더 크면 부모 노드의 인덱스를 증가시키는(트리에서 밑으로 끌어내리는) 과정을
키 값이 더 큰 부모 노드를 만날 때까지만 반복한다.
반복이 끝나면 현재 인덱스의 원소에 삽입할 키 값을 대입하고 힙의 삽입 과정이 종료된다.

수도코드
insert_max_heap(heap h, int item){
  int i = ++(h.size);
  while(i > 0 && h[i/2] < item){ // h[i]가 루트 노드가 아니고, 부모 노드보다 클 것
    h[i] = h[i/2];
    i /= 2;
  }
  h[i] = item;
}

 

시간 복잡도 : 힙의 크기를 n이라고 할 때, 힙을 정렬할 때 힙을 탐색하는 횟수가 최악의 경우 힙의 높이와 같고,

힙의 높이는 ceiling(log n)이므로, 시간 복잡도는 O(log n)이다.

힙의 삭제
힙은 우선순위 큐를 구현하기 위한 것이다. 그러므로 루트 노드를 삭제한다.
루트 노드를 삭제하면 빈 노드가 생긴다. 빈 노드의 두 자식 노드 중 키 값이 더 큰 노드를 위로 끌어올리는 과정을 트리가 완전 이진 트리로 복구될 때까지 반복한다. 이 과정을 거치고 나면 부모 노드가 두 자식 노드보다 키 값이 더 큰 최대 힙의 구조가 유지된다.

수도코드
delete_max_heap(heap h){
  int i = 0;
  int ret = h[0];

  int child = 2;
  while(child < h.size){ // 이 조건은 일단 왼쪽 자식 노드의 존재만 담보한다.
    if(child+1 < h.size && h[i*2] < h[i*2+1]){ // 오른쪽 자식 노드가 존재하면서 왼쪽 자식보다 클 때
      child++;
    }
    h[i] = h[child];
    i = child;

    child = i*2;
  }
  h.size--;
  return ret;
}

 

시간 복잡도 : 힙의 크기를 n이라고 할 때, 삽입과 마찬가지로 힙을 정렬할 때 탐색하는 횟수가 최악의 경우 힙의 높이와 같고,

힙의 높이는 ceiling(log n)이므로, 시간 복잡도는 O(log n)이다.