[CS/알고리즘] Binary Heap(max-heap, min-heap) 이진힙트리

Binary Heap (이진 힙)

• 이진 힙은 이진 트리형태로 만들어진 min-heap, max-heap 을 말한다.
• 완전 이진 트리라는 조건을 만족해야한다 --> 마지막 레벨은 왼쪽부터 생성.
• 값의 대소관계는 오직 부모관계에만 성립 --> 같은 레벨일 경우엔 상관이 없다.
• 힙의 삽입, 삭제 시간복잡도는 O(logN), 특정값(최대,최소) 탐색은 O(1)

이진 힙(Binary heap) 배열 구조 / 출처 : <파이썬 알고리즘 인터뷰> p.407, 책만, 2020

삽입

1. 최하층 리프노드에 입력값을 삽입한다.
2. 부모와 값을 비교 후, 조건에 맞으면 그대로 두고 아니면 부모와 교환한다.
3. 조건에 맞을 때 까지 위 과정을 반복한다. 

 

 

 

그림에서 (7)이 새로운 입력값으로 힙에 들어왔다.

부모 노드에 있는 (18) 과 값을 비교,

 

 

 

자녀에 위치한 (7)이 더 작기 때문에 부모위치와 교환한다.

다시한번 부모노드인 (9) 와 값을 비교,

 

 

 

(7)이 부모 보다 더 작기 때문에 부모위치와 교환.

다시한번 부모노드인 (5) 와 값을 비교,

이번에는 (7)이 부모 보다 더 크기 때문에 교환이 일어나지 않고 삽입이 완료.

 

 

 

삭제

1. 루트 노드를 제거한다. --> 최소값 or 최댓값만 삭제 가능
2. 루트노드에 가장 마지막 리프노드를 삽입한다.
3. 올라간 노드와 자식 노드들을 비교한다.
4. 조건에 만족하면 그대로 두고, 그렇지 않으면 자식위치와 교환한다.

 

 

 

그림에서, 최소값인 (5)를 제거한 뒤,

가장 마지막 위치인 (27)을 루트노드위치로 가져온다. 

 

 

 

 

자녀노드인 (9) 가 더 작기 때문에 자녀위치와 루트노드를 교환한다.

 

 

 

 

자녀노드인 (14)가 더 작기 때문에 다시한번 자녀위치로 교환한다.

 

 

 

 

마지막으로 다시한번 자녀노드와 값을 비교하여 (17)이 더 작기 때문에 위치교환이 이루어진 후, 삭제가 완료된다.

 

 

 

 

 

그림출처 : 파이썬 알고리즘 인터뷰