[ 자료구조 ] 힙(heap)

개념특징힙은 영어로 ‘더미’다. 컴퓨터공학에서 힙은 데이터 더미를 완전이진트리 구조로 표현하여 최대값 또는 최소값을 빠르게 찾을 수 있는 자료구조다. 우선순위큐를 구현하는 데 자주 사용된다. 힙은 최대힙과 최소힙이 있다.최대힙최대힙은 루트노드가 최대값이다. 부모노드의 값이 자식노드의 값보다 커야한다.최소힙최소힙은 루트노드가 최소값이다. 부모노드의 값이 자식노드의 값보다 작아야한다.연산힙 연산이 끝난 후에도 완전이진트리 구조를 유지해야한다. 최대힙 기준으로 삽입연산과 삭제연산을 설명하면 다음과 같다.삽입연산데이터 삽입은 힙의 맨 끝에서 이뤄진다. 부모노드와 우선순위를 비교해 부모보다 자식이 높으면 부모와 자식의 위치를 바꾸면서 루트노드까지 비교한다.1. 이진트리의 맨 마지막 자리에 노드를 추가한다.2. 부..