힙(Heap)

힙(Heap)

힙 : 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조

 

최대 힙(max heap)

• 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
• 부모 노드의 키 값 > 자식 노드의 키 값
• 루트 노드 : 키 값이 가장 큰 노드

최소 힙(min heap)

• 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
• 부모 노드의 키 값 < 자식 노드의 키 값
• 루트 노드 : 키 값이 가장 작은 노드

힙

힙이 아닌 이진 트리

힙 연산 - 삽입

17 삽입 과정

23 삽입 과정

힙 연산 - 삭제

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

힙에서의 삭제