개념
특징
힙은 영어로 ‘더미’다. 컴퓨터공학에서 힙은 데이터 더미를 완전이진트리 구조로 표현하여 최대값 또는 최소값을 빠르게 찾을 수 있는 자료구조다. 우선순위큐를 구현하는 데 자주 사용된다. 힙은 최대힙과 최소힙이 있다.
최대힙
최대힙은 루트노드가 최대값이다. 부모노드의 값이 자식노드의 값보다 커야한다.
최소힙
최소힙은 루트노드가 최소값이다. 부모노드의 값이 자식노드의 값보다 작아야한다.
연산
힙 연산이 끝난 후에도 완전이진트리 구조를 유지해야한다. 최대힙 기준으로 삽입연산과 삭제연산을 설명하면 다음과 같다.
삽입연산
데이터 삽입은 힙의 맨 끝에서 이뤄진다. 부모노드와 우선순위를 비교해 부모보다 자식이 높으면 부모와 자식의 위치를 바꾸면서 루트노드까지 비교한다.
1. 이진트리의 맨 마지막 자리에 노드를 추가한다.
2. 부모노드와 우선순위를 비교 후 자식 노드가 우선순위가 높으면 부모노드와 자리를 교체한다.
3. 부모노드가 우선순위가 높을 때까지 2를 반복한다.삭제 연산
데이터 삭제는 힙의 루트노드에서 이뤄진다. 루트노드를 삭제한 후 가장 마지막에 추가한 노드를 루트노드의 위치로 이동한다. 이동한 노드와 자식노드의 우선순위를 비교해 힙을 재정렬한다.
1. 트리의 마지막 노드를 별도로 저장한 후에 트리에서 제거한다.
2. 루트노드에서 시작해서 저장한 노드와 루트노드의 자식노드의 우선순위를 비교 후 저장한 노드가 우선순위가 낮으면 자식노드와 자리를 교체한다.
3. 교체 된 자리의 자식노드와 저장한 노드의 우선순위를 비교한 후 저장노드의 우선순위가 더 낮으면 자리 교체한다.
4. 자리가 교체되지 않을 때까지 3을 반복한다.이진검색트리와의 차이점
힙은 형제노드의 좌우 순서가 구분이 없지만 이진검색트리는 구분이 있다. 힙은 느슨한 정렬을 유지하고 있기 때문이다.