힙
중에서 가장 널리 쓰이는 형태 중 하나로 이진 트리 형태의 힙.
이진 트리
는 각 노드의 자식 노드가 반드시 2개 이하인 트리이다.
이진 힙
은 완전 이진 트리라는 조건을 만족해야 한다.
모든 레벨의 노드가 채워져 있어야 하며, 마지막 레벨은 왼쪽부터 채워져 있어야 한다.
힙(Heap)에는 최대힙(Max heap)
, 최소힙(Min heap)
두 종류가 있다.
최대 힙
: 부모 노드는 항상 자식 노드보다 크거나 같아야 한다.최소 힙
: 부모 노드는 항상 자식 노드보다 값이 작거나 같아야 한다.즉, 최대 힙의 루트는 힙 내에서 가장 큰 값, 최소 힙의 루트는 힙 내에서 가장 작은 값을 의미한다는 것이다.
힙 전체를 통틀어서 이 규칙이 꼭 유지되어야 한다.
최대 힙과 최소 힙의 차이는 사실 정렬할 때 조건 밖에 없다.
우선순위 큐와 연관지어 Max Heap
을 구현해보자.
새로운 요소가 추가되면 우선 트리의 가장 마지막 노드에 넣어준다.
그 후 부모 노드와 비교해서 작으면 부모와 위치를 교환하고, 반복해준다.
노드의 자식은 2개까지 가질 수 있다.
따라서 n번째 노드의 부모는 Math.floor((n-1) / 2)
와 동일하다.
원소를 힙의 가장 마지막 노드에 추가한다.
추가한 요소를 부모와 비교한다.
순서가 힙 조건과 일치한다면 멈춘다.
힙 조건과 순서가 맞지 않다면 부모와 위치를 교환한다.
힙 조건과 일치할 때까지 반복한다.
루트 노드를 제거한 경우, 우선 가장 마지막 노드의 값이 루트 노드의 값으로 변경된다.
그 후 자식 중 더 작은 값과 비교해서 해당 값이 더 크다면 자식 요소와 교환하고 이를 반복한다.
자식 노드는 부모 노드와 반대로 n*2 + 1
로 구한다.
두 자식 노드 중 더 작은 노드와 값을 비교하고 반복한다.
힙의 루트 노드를 삭제한다.
마지막 노드를 루트로 이동한다.
루트를 자식 노드와 비교한다. 이 때, 두 자식 노드 중 최대 힙인 경우 더 큰 자식과 비교하며, 최소 힙인 경우 더 작은 자식과 비교한다.
순서가 힙 조건과 일치한다면 멈춘다.
만약 순서가 맞지 않는다면 위치를 교환한다.
힙 조건이 일치할 때까지 반복한다.