힙(heap)

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

힙의 조건 : 완전 이진 트리이며 , 아래에서 설명할 최대 힙 , 최소 힙의 조건을 충족 해야한다.

완전 이진트리

완전 이진 트리란 루트 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리(Tree)를 의미합니다.

힙의 종류

• 최대 힙 (max Heap)
• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
• key(부모 노드) => key(자식 노드)
• 최소 힙(min heap)
• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리