힙(Heap) 개념 (1)

우선순위 큐(Priority Queue)를 힙(Heap)으로 제작하기에 앞서 힙(Heap)이 무엇인지 알아야 한다. 

힙(Heap) 이란?

완전 이진 트리로 구성된 힙은 두가지로 나뉜다.

최대 힙 : 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같다.

즉, 루트 노드에 저장된 값이 가장 크다.

최소 힙 : 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 작거나 같다.

즉, 루트 노드에 저장된 값이 가장 작다.

이때 힙에서 자식 노드에서의 크기에 따른 위치는 따로 없다.

예를들어 힙에서 최대 힙을 가정하여 말한다면, 이진 탐색 트리처럼 왼쪽이 작은 값이 오고, 오른족이 큰 값이 오는 

그런것은 만족하지 않아도 되고 단지 부모 노드가 자식 노드보다 값이 크거나 같으면 된다는 조건만 있으면 된다.

아래의 그림을 통해 확인하자.

[그림 1] 최대 힙(Max Heap)

 

[그림 2] 최소 힙(Min Heap)

이처럼 최대 힙과 최소 힙의 정의는 따르 되, 힙의 자식 노드에서 작은 것이 왼쪽, 큰 것이 오른쪽 이런것은 존재하지 않는다. 

이 외의 최대 힙 및 최소 힙의 그림은 다음과 같다.

[그림 3] 최대 힙(Max Heap)

[그림 4] 최소 힙(Min Heap)