[Algorithm] 힙 (Heap)

힙(heap)

• 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰/작은 노드를 찾기 위해서 만든 자료구조
• 힙의 키를 우선순위로 활용하여 우선순위 큐를 구현할 수 있음
• 최대 힙 (max heap)
  • 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
  • {부모 노드의 키 값 > 자식 노드의 키 값}
  • 루트 노드 : 키 값이 가장 큰 노드
• 최소 힙 (min heap)
  • 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
  • {부모 노드의 키 값 < 자식 노드의 키 값}
  • 루트 노드 : 키 값이 가장 작은 노드

 

삽입 연산

 

삭제 연산

• 힙에서는 루트 노드의 원소만을 삭제할 수 있음
• 루트 노드의 원소를 삭제하여 반환
• 힙의 종류에 따라 최대값 또는 최소값 구할 수 있음