<PQ> Heap 이란?

힙은 완전 이진 트리로(마지막 레벨을 제외한 모든 레벨의 노드가 채워져 있는 트리) 루트가 최대값이냐 최소값이냐에 따라 최대 힙과 최소 힙이 있습니다.

B는 완전 이진 트리가 아니다.

최대 힙에 포함된 부모 노드는 자식 노드에 들어있는 값보다 크고 최소 힙에 포함된 부모 노드는 자식 노드에 들어있는 값보다 작습니다. 그래서 최대 최소 값을 찾는데 매우 유용합니다.

최대 힙

최대 힙에서는 루트 노드가 가장 큰 값을 갖습니다. 또한 완전 이진 트리이므로 N개가 들어있다면 트리의 높이는 logN이 됩니다.

최대 힙 삽입

• 가장 마지막 위치에 삽입할 수를 위치시킨다.
  완전 이진 트리이므로 가장 왼쪽 위치가 마지막 위치가 된다.
• 부모와 비교하며 현재 노드가 더 크면 위치를 바꾼다.
• 부모와 비교하여 현재 노드가 작으면 멈춘다. 그 위치가 삽입 위치가 된다.
• 최대 높이 만큼 탐색하게 되므로 복잡도 $O(logN)$으로 가능합니다.

최대 힙 제거

• 제거할 노드를 루트로 하느 서브 트리에서 가장 마지막 위치의 노드를 제거할 노드의 위치로 옮긴다. (일단 target제거 완료)

• 루트에서 시작하여 자식과 비교하며 자식이 더 크면 위치를 바꾸며 반복한다.
• 자식이 작거나 없다면 멈춘다.
• 최대 높이 만큼 탐색하게 되므로 복잡도 $O(logN)$으로 가능합니다.

최소 힙

루트 노드가 트리에서 가장 작은 값이 되는 구조입니다.

최소 힙 삽입

최대 힙 삽입과 부등호만 반대로 해주면 구현 가능합니다.

최소 힙 삭제

최대 힙 삭제와 부등호만 반대로 해주면 구현 가능합니다.

JAVA에서의 힙

JAVA에서 우선순위에 따라 정렬되는 PriorityQueue의 내부에는 Heap으로 구현되어 있으며 기본적으로는 최소값이 우선 순위가 높은 최소 힙입니다. 만약 최대 힙으로 바꾸고 싶다면

• Comparator를 이용하거나

PriorityQueue<Integer> q = new PriorityQueue<>(1, 비교자)

• 값 자체에 -1을 곱해주는 방법

총 2가지로 가능합니다.