힙 (Heaps)

힙 (Heaps)

 

트리, 그 중에서도 이진트리의 한 종류

1. 루트 노드가 언제나 최대값 또는 최소값을 가지는데

대개 파이썬의 경우는 최소힙 heapq에 마이너스 - 를 붙여 최대힙으로 구현한다.

 

2. 완전 이진 트리여야 한다.

완전 이진 트리 (Complete Binary Tree)

높이가 k인 완전 이진 트리는

 

레벨 k-2까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리면서

레벨 k-1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리를 말한다.

 

 

조건을 지키며 정상적으로 구현된 힙이라면 어떤 노드를 루트로 하는 서브트리라도 모두 최대힙이 보장된다.

 

 

이진 탐색 트리와의 비교

이진 탐색 트리는 왼쪽 자식은 루트 노드보다 작고 오른쪽 자식은 루트 노드보다 크기 때문에

왼쪽과 오른쪽의 관계가 정의되어 있지만 힙은 그렇지 않다.

 

키 값을 이용해 빠른 데이터 검색이 되지 않는다.

왼쪽과 오른쪽의 관계가 정의되어 있지 않기 때문이다.

 

힙은 완전 이진 트리여야만 하는 제약 조건이 존재한다.

 

 

노드 인덱스에 접근하는 방법

 

루트 노드의 인덱스x2 = 루트 노드의 왼쪽 노드

루트 노드의 인덱스x2+1 = 루트 노드의 오른쪽 노드

어떤 특정 노드 A의 인덱스//2 = A의 부모 노드

 

(최대)힙의 원소 삽입

 

1. 트리의 가장 마지막 자리(비어있는 자리 중 가장 앞의 자리)에 원소를 넣는다.

2. 집어 넣은 원소와 부모 노드의 원소를 대소비교해 더 크다면 계속 부모 노드와 자리를 바꿔준다.

 

완전 이진 트리이므로 최악의 경우에도 시간 복잡도는 O(log n)

 

 

힙의 원소 삭제

최대힙에서 원소는 최대값인 루트 노드만 제거할 수 있으므로 매우 간단하다.

여기까지는 간단하지만 문제는 그 다음부터인데..

 

완전 이진 트리 형태를 늘 지켜야하므로

 

1. 트리의 마지막 자리 노드를 임시로 루트 노드의 자리에 배치한다.

일단 완전 이진 트리 형태의 모양은 지켰다.

 

2. 그 다음 왼쪽, 오른쪽 모든 자식 노드들보다 값이 클 때까지 아래로 계속 이동 시킨다.

그렇다면 자식이 둘 있을 때는 왼쪽으로 이동할까, 오른쪽으로 이동할까?

정답은 자기보다 작은 부모 노드와 자리를 교체하고 부모 노드의 자리에서 왼쪽과 오른쪽 자식 노드 둘 보다

큰 경우를 만족하는 쪽의 자식 노드와 자리를 바꿔준다.

 

한줄로 요약하자면 왼쪽과 오른쪽 자식 노드 중에서 더 큰쪽

 

시간 복잡도는 원소가 n개인 최대 힙에서 최대값을 삭제하는 경우를 가정하면

자식 노드들과의 대소 비교의 최대 횟수는 2 x log n이지만 계수는 빅O표기법에서 의미가 없으므로

최악의 경우에도 시간복잡도는 log n이다. (당연히 밑은 2이다.)

 

완전 이진 트리이므로 높이가 n일 때 밑이 2인 log n 시간 복잡도이다.