[Non-Linear] Binary - heap

Binary -heap 구조는 트리구조에서 최대값과 최소값을 빠르게 찾기 위한 완전 이진트리(complete binary tree) 기본으로 한 자료구조임. 

 

1. 종류

  1) Min Heap : Root Node에 가장 작은 값이 오도록 하는 것. 부모노드는 자식노드보다 작은 값을 가지는 트리구조.

  2) Max Heap : Root Node에 가장 큰 값이 오도록 하는 것. 모든 부모노드는 자기 자식노드보다 큰 값을 가지는 트리구조.

  ※ 근본적으로 두개는 갖고 숫자만 반대로 하면 된다. 아래 설명은 최소힙만 보도록 하겠다.

 

2. 특징

  1) 삽입(insert)

     (1) 완전 이진트리의 구성을 잃지 않도록 마지막 Child Node의 왼쪽부터 채워나감.

        ※ 왼쪽 채워져있으면 오른쪽에 채우면 됨

     (2) 삽입된 원소가 제대로 된 자리를 찾을때 까지 부모노드와 교환해 나간다.

     (3) O(logN)의 시간 복잡도를 가짐.

1의 값을 가진 Node를 삽입

1의 부모노드인 3과 비교하여 위치를 바꿈.

1의 부모노드인 2와 비교를 하여 위치를 바꿈

 

2) 최소원소 뽑아내기(extract_min)

  (1) 최소원소는 항상 Root에 있어서 찾기는 쉽다. 하지만, 최소값을 어떻게 Heap에서 제거하느냐가 까다롭다.

  (2) 최소 원소를 제거한 후에 힙에 있는 가장 마지막 원소를 Root 위치로 교환한다.

  (3) 그리고 최소 힙의 조건을 만족하도록 정렬해 간다.

  (4) 최대 O(logN)의 시간 복잡도를 가짐.

 

최소 원소값이 제거된 후

마지막 원소를 Root자리로 교환

자신의 자식노드와 비교해서 위치를 교환