BinaryHeap

힙 중에서 가장 널리 쓰이는 형태 중 하나로 이진 트리 형태의 힙.
이진 트리는 각 노드의 자식 노드가 반드시 2개 이하인 트리이다.

이진 힙은 완전 이진 트리라는 조건을 만족해야 한다.
모든 레벨의 노드가 채워져 있어야 하며, 마지막 레벨은 왼쪽부터 채워져 있어야 한다.

힙(Heap)에는 최대힙(Max heap), 최소힙(Min heap) 두 종류가 있다.

• 최대 힙: 부모 노드는 항상 자식 노드보다 크거나 같아야 한다.
• 최소 힙: 부모 노드는 항상 자식 노드보다 값이 작거나 같아야 한다.

즉, 최대 힙의 루트는 힙 내에서 가장 큰 값, 최소 힙의 루트는 힙 내에서 가장 작은 값을 의미한다는 것이다.
힙 전체를 통틀어서 이 규칙이 꼭 유지되어야 한다.
최대 힙과 최소 힙의 차이는 사실 정렬할 때 조건 밖에 없다.

우선순위 큐와 연관지어 Max Heap 을 구현해보자.

삽입: 요소를 추가할 때

새로운 요소가 추가되면 우선 트리의 가장 마지막 노드에 넣어준다.
그 후 부모 노드와 비교해서 작으면 부모와 위치를 교환하고, 반복해준다.
노드의 자식은 2개까지 가질 수 있다.
따라서 n번째 노드의 부모는 Math.floor((n-1) / 2)와 동일하다.

1. 원소를 힙의 가장 마지막 노드에 추가한다.

   

2. 추가한 요소를 부모와 비교한다.
   순서가 힙 조건과 일치한다면 멈춘다.

   

3. 힙 조건과 순서가 맞지 않다면 부모와 위치를 교환한다.
   힙 조건과 일치할 때까지 반복한다.

   

삭제: 요소를 제거할 때

루트 노드를 제거한 경우, 우선 가장 마지막 노드의 값이 루트 노드의 값으로 변경된다.
그 후 자식 중 더 작은 값과 비교해서 해당 값이 더 크다면 자식 요소와 교환하고 이를 반복한다.
자식 노드는 부모 노드와 반대로 n*2 + 1로 구한다.
두 자식 노드 중 더 작은 노드와 값을 비교하고 반복한다.

1. 힙의 루트 노드를 삭제한다.

   

2. 마지막 노드를 루트로 이동한다.
   루트를 자식 노드와 비교한다. 이 때, 두 자식 노드 중 최대 힙인 경우 더 큰 자식과 비교하며, 최소 힙인 경우 더 작은 자식과 비교한다.
   순서가 힙 조건과 일치한다면 멈춘다.

   

3. 만약 순서가 맞지 않는다면 위치를 교환한다.
   힙 조건이 일치할 때까지 반복한다.