힙이란?
힙을 설명하기 전에 우선순위 큐에 대해서 알아보자.
우선순위 큐는 FIFO 인 큐와 달리 우선 순위가 높은 요소가 먼저 나가는 큐를 말한다. 여기서 주의해야 하는 것은 우선순위 큐는 자료구조가 아닌 개념이다. 따라서 우선순위 큐를 구현하는 방법은 다양하게 존재할 수 있다. 그중 힙은 우선순위 큐를 구현하기 위한 가장 적합한 방법이다. 자료구조 힙은 이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될때 바로 정렬되는 특징이 있다.
그래서 간혹 우선순위 큐와 힙을 같은 것이라고 말하는 경우가 있지만, 실제로는 다르다. 만약 매번 배열을 우선순위에 따라 정렬한다면 그것도 우선순위 큐가 될 수 있다. 단지 힙 보다 효율이 떨어질 뿐이다.
힙의 특징
- 우선순위가 높은 요소를 루트 보다 배치하고 항상 루트가 먼저 나간다라는 특징을 가진다.
- 루트가 가장 큰 값이 되는 최대 힙(Max Heap)과 루트가 가장 작은 값이 되는 최소 힙(Min Heap)으로 나뉠 수 있다. 오름차순이냐, 내림차순이냐의 정도의 차이이다.
- 다른 언어와 다르게 자바스크립트는 힙을 직접 코드로 구현해서 사용해야 한다.
힙의 요소 추가
- 먼저 요소가 추가될 때 이진 트리의 가장 마지막 정점에 추가한다.
- 요소가 추가되었다면 부모 정점보다 우선순위가 높은지 체크한다. 만약 추가된 요소가 더 높다면 부모 정점과 순서를 바꾼다.
- 그리고 더 이상 순서를 바꿀 수 없을 때까지 반복하면 결국 가장 우선순위가 높은 정점이 루트가 된다.
- 그리고 요소는 항상 이진 트리의 마지막에 추가가 되기 때문에 힙은 항상 완전 이진트리이다. 따라서 높이는 log N 이기에 요소 추가 알고리즘은 최악의 경우에도 log N이라는 짧은 시간만에 가능하다.
먼저 최대 힙을 만든다 가정하고 45를 추가해본다고 가정하자. 그러먼 루트에 45 정점이 생긴다. 그리고 힙은 이진트리이기 때문에 배열로 표현이 가능하다.
이번에는 36을 추가해보자. 가장 마지막 위치인 45정점 왼쪽에 추가된다. 이어서 54를 추가한다. 가장 마지막 위치인 루트의 오른쪽에 추가된다. 최대 힙에서 45보다 54가 우선순위가 더 높기 때문에 서로 순서를 바꿔야 한다. 규칙에 따라 루트와 오른쪽 정점을 바꿔준다.
이번에는 27을 추가해보자. 마지막 위치 36에 왼쪽 정점에 추가된다. 이어서 63을 추가한다. 36의 오른쪽 정점에 추가된다. 36보다 63이 우선순위가 더 높기 때문에 바꿔야한다. 규칙에 따라 36과 63을 바꿔준다. 여기서 또 부모 정점과 비교해보니 54보다 63이 우선순위가 더 높음을 알 수 있다. 마찬가지로 규칙에 따라 54와 63를 교체해준다. 루트까지 이동했기 때문에 탐색을 종료한다.
이런 식의 추가 로직에 따라 알고리즘을 작성하면 최대 힙을 완성할 수 있다.
힙의 요소 제거
힙 요소 제거 알고리즘은 추가 알고리즘보다 조금 더 복잡하다.
- 먼저 요소를 제거하는 건 루트 정점만 가능하다.
- 루트 정점이 제거되면 그 공백을 가장 마지막 정점에 배치한다.
- 이때 추가와는 반대로 루트로부터 점점 정점을 아래로 내려야 한다.
- 루트 정점의 두 정점 자식 중 더 우선순위가 높은 정점과 바꾼다.
- 두 자식의 정점이 우선순위가 더 낮을 때까지 반복한다.
- 그러면 자연스럽게 우선순위가 더 높은 정점이 루트 정점이 될 수 있다.
- 추가와 마찬가지로 제거도 완전 이진트리의 높이 만큼만 진행되기 때문에 시간 복잡도가 log 시간을 가진다.
먼저 루트 정점인 63을 제거해보자. 그럼 가장 마지막 정점인 36이 루트에 위치하게 된다.
다음엔 규칙에 따라 자식 정점인 54와 45를 비교한다. 54가 우선 순위가 더 높기 때문에 54와 45를 교체한다. 그리고 자식 정점인 27과 비교한다. 여기서 오른쪽 자식은 없기 때문에 27하고만 비교한다. 이번엔 자식의 우선 순위가 더 낮기 때문에 바꾸지 않고 로직을 종료한다.
