이진트리의 일종으로, 효율적인 탐색을 위한 저장 방법이다.
1) 항상 왼쪽의 노드가 오른쪽의 노드의 값보다 작다.
주의할 점은, 힙과 달리 상/하에서의 값은 절대적이지 않다는 것이다. 따라서 가장 오른쪽 아래의 수가 항상 트리에서 가장 큰 수임이 보장된다.
이러한 특징은 균형 잡힌 트리가 아닐 경우, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 되어 탐색 시간이 O(N)
으로 증가한다.
항상 크기 순대로 정렬이 되어있으므로, 탐색시 유리하다(O(LogN)
)
하지만 삽입, 삭제의 경우에도 O(LogN)
의 성능을 가지므로 BST가 아닌 힙을 사용하는것이 좋다.
1) 상/하위 관계(depth 별로)가 보장된다.
max-heap은 상위에 있는 노드가 하위에 있는 노드보다 크면 되며, 같은 level을 가진 좌우 노드끼리는 아무런 관계가 존재하지 않는다.
2) 반드시 완전 이진 트리이어야 한다.
3) 최대 힙 내의 임의의 노드를 루트로 하는 서브트리 또한 힙 구조여야 한다.
🔖 힙에서의 노드별 공식
노드 번호가 m이라고 가정
1. 부모 노드의 번호 :m//2
2. 왼쪽 자식의 번호 :2*m
3. 오른쪽 자식의 번호 :2*m + 1
삽입/삭제 연산시 사용한다. 항상 배열의 끝에서 삽입과 삭제연산이 일어나므로 O(1)
의 성능을 가지며, 이는 BST의 OlogN
시간보다 빠르기 때문이다.
특히, Root노드가 가장 우선순위가 높기 때문에 빠른 속도로 가장 작은 값을 추출하거나 가장 큰 값을 추출해야 하는 경우 사용한다.
class Maxheap:
def __init__(self):
self.data = []
def insert(self, item):
self.data.append(item) # 맨 끝에 원소 추가
i = len(self.data) - 1 # 0번 인덱스 제외
while i > 1: # 각 원소를 부모 노드와 비교 하면서 최대 힙의 성질에 맞도록 교환
if self.data[i] > self.data[i//2]: # 자신의 부모 노드 보다 크다면 부모 노드와 교환
self.data[i], self.data[i//2] = self.data[i//2], self.data[i]
i //= 2 # 현재 위치를 부모 위치로 변경
else:
break # 자신의 부모 노드 보다 작다면 교환할 필요가 없음
def remove_max(self): # pop 연산
if len(self.data) > 1: # 힙에 루트 제외 원소가 남아 있다면
self.data[1], self.data[-1] = self.data[-1], self.data[1] # 루트와 맨 끝에 있는 노드 끼리 자리 교환
data = self.data.pop(-1) # 힙에서 가장 큰 원소를 빼내기 + 제거
self.max_heapify(1) # root 노드에 위치한 값을 아래로 내리 면서 적절한 위치로 이동 시킴
else:
data = None
return data
def max_heapify(self, i): # 힙 정렬
left = i * 2
right = (i * 2) + 1
smallest = i # 이후 교환할 위치
if left < len(self.data) and self.data[i] < self.data[left]:
smallest = left # 왼쪽 자식의 위치와 교환 위해 임시 저장
if right < len(self.data) and self.data[i] > self.data[right]:
smallest = right # 오른쪽 자식의 위치와 교환 위해 임시 저장
if smallest != i:
self.data[i], self.data[smallest] = self.data[smallest], self.data[i]
self.max_heapify(smallest) # 재귀적 호출을 이용해 최대 힙의 성질을 만족할 때까지 트리를 정리
참고자료
https://hyoeun-log.tistory.com/entry/자료구조-Heap과-BST의-차이점
https://m.blog.naver.com/leeinje66/221622360256