[자료구조] 힙

힙이란?

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조입니다.
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조입니다.
• 힙은 일정의 반정렬 상태를 유지합니다.
• 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도입니다.
• 간단히 말하면 부모 노드의 값이 자식 노드의 값보다 항상 크거나 작은 이진트리입니다.
• 힙 트리에서는 중복된 값을 허용합니다. (이진트리에선 허용 안합니다.)

 

힙의 종류

최대힙

• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리입니다.

최소힙

• 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리입니다.