Heap
정의
- 힙은 ‘이진트리’ 이되 ’완전 이진 트리’이다. 그리고 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다. 즉 루트 노드에 저장된 값(또는 우선순위)이 가장 커야 한다.
- 루트로 올라갈수록 저장된 값이 커지는 완전 이진 트리는 최대 힙. 작아지는 완전 이진트리는 최소 힙
- 영단어 heap은 ’무엇인가를 차곡차곡 쌓아 올린더미’라는 뜻.
데이터 저장과정
- 자식 노드 데이터의 우선순위 <= 부모 노드 데이터의 우선순위
- 새로운 데이터는 우선순위가 제일 낮다는 가정하에서 ’마지막 위치’에 저장. 그리고는 부모 노드와 우선순위를 비교해서 위치가 바뀌어야 한다면 바꿔준다. 제대로 된 위치를 찾을 때까지 반복.
데이터 삭제과정
- 힙에서 루트 노드를 삭제한 다음에 이 부분을 어떻게 채울 것인가?
- 마지막 노드를 루트 노드의 자리로 옮긴 다음에, 자식 노드와의 비교를 통해서 제 자리를 찾아가게 한다.
- 두 개의 자식노드중 우선순위가 높은 노드와 교환해 나간다.
힙의 구현에 어울리는 자료구조
- 배열을 기반으로 구현하는 것이 원칙
- 연결리스트를 기반으로 힙을 구현하면, 새로운 노드를 힙의 ’마지막 위치’에 추가하는 것이 쉽지 않다.
출처
- 윤성우의 열혈 자료구조 (오렌지미디어, 2012)
