힙
힙은 완전이진트리로 최대값 또는 최소값을 빠르게 찾을 수 있는 자료구조다. 우선순위큐를 구현하는 데 자주 사용된다.
힙은 삽입연산과 삭제연산이 있다.
삽입연산
데이터 삽입은 힙의 맨 끝에서 이뤄진다. 부모노드와 우선순위를 비교해 부모보다 자식이 높으면 부모와 자식의 위치를 바꾸면서 루트노드까지 비교한다.
삽입연산의 과정
이진트리의 맨 마지막 자리에 노드를 추가한다.
부모노드와 우선순위를 비교 후 자식 노드가 우선순위가 높으면 부모노드와 자리를 교체한다.
부모노드가 우선순위가 높을 때까지 2를 반복한다.삭제 연산
데이터 삭제는 힙의 루트노드에서 이뤄진다. 루트노드를 삭제한 후 가장 마지막에 추가한 노드를 루트노드의 위치로 이동한다. 이동한 노드와 자식노드의 우선순위를 비교해 힙을 재정렬한다.
삭제연산의 과정
트리의 마지막 노드를 별도로 저장한 후에 트리에서 제거한다.
루트노드에서 시작해서 저장한 노드와 루트노드의 자식노드의 우선순위를 비교 후 저장한 노드가 우선순위가 낮으면 자식노드와 자리를 교체한다.
교체 된 자리의 자식노드와 저장한 노드의 우선순위를 비교한 후 저장노드의 우선순위가 더 낮으면 자리 교체한다.
자리가 교체되지 않을 때까지 3을 반복한다.