힙(Heap)

힙

완전 이진 트리에 있는 노드 중 가장 큰 노드나 가장 작은 노드를 찾는 위해 만든 자료구조이다.

힙의 조건

• 완전 이진 트리 : 위에서 아래로 왼쪽에서 오른쪽으로 순차적으로 채워가는 트리
  
  출처 : https://robodream.tistory.com/181
• 부모노드의 키 값 > 자식노드의 키 값
  : 이 조건을 최대힙(Max heap) 이라고 하며 원소가 내림차순으로 정렬되어 있다.
• 부모노드의 키 값 < 자식노드의 키 값
  : 이 조건을 최소힙(min heap) 이라고 한다. 원소가 각 노드의 자식보다 작다. 즉 오름차순이다.

힙의 삽입 연산

삽입시에 가장 중요한 포인트는 이진트릴 유지해야 된다.

아래의 삽입 애니메이션은 최대 힙인 경우 제일 큰 노드의 값이 삽입이 이루어 졌을때 생기는 과정이다.

힙의 삭제 연산

힙에서의 삭제연산은 언제나 루트 노드에있는 원소를 삭제하며, 최대 힙에서는 가장 큰원소를 삭제한다. 최소힙에서는 가장 작은 원소를 삭제 하여 반환한다.