알고리듬 #13 | 힙 (Heap)

우선순위 큐

개요

• 큐(FIFO) 와 달리 우선 순위가 높은 요소가 먼저 나가는 큐
  • 클럽에서 줄을 서 있는데, VIP 는 먼저들어 가는 경우 (예시)

특징

• 자료구조가 아닌 개념입니다.
  • 따라서 우선순위 큐를 구현하는 방법은 다양하게 존재합니다.
  • 힙 (Heap) 도 그중 하나입니다.

---

힙 (Heap)

개요

• 이진 트리 형태
• 높은 요소를 먼저 내보냅니다. (FIFO ❌❌❌)
  • 그래서, 요소가 삽입, 삭제될 때 바로 정렬되는 특징이 있습니다.

주의점

• 우선순위 큐 != 힙
  • 만약, 배열을 우선순위에 따라 매번 정렬하면 우선순위 큐가 될 수있습니다.
  • 즉, 우선순위 큐가 힙보다 더 큰 범위의 개념입니다.
  • 그리고, 힙 은 자료구조입니다.

특징

우선순위가 높은 요소가 먼저 나가는 특징을 가집니다.

• 항상, 우선 순위가 높은 요소를 루트로 배치합니다.
• 항상, 루트가 먼저 나갑니다.

두 종류의 힙이 있습니다. (오름차순, 내림차순 차이와 비슷한 차이)

• 최대 힙 (Max Heap) : 루트가 가장 큰 값
• 최소 힙 (Min Heap) : 루트가 가장 작은 값

힙을 제공해주는 다른 언어들과 다르게 자바스크립트에서는 직접 구현해야합니다.

요소 추가

알고리즘

• 추가되는 요소는 트리의 가장 마지막 정점에 위치합니다.
  1. 만약, 추가된 요소의 우선순위가 부모 정점보다 높다면 순서를 바꿉니다.
  2. 추가된 요소가 부모 정점보다 우선순위가 높은 경우 순서를 바꾸는 과정을 반복합니다.
  3. 결국, 가장 우선순위가 높은 정점이 루트가 됩니다. (최대 힙 완성)

시간복잡도

• O(log N) 시간복잡도를 가집니다. (최악의 경우)
  • 완전 이진 트리의 높이가 log N 이기 때문입니다.
  • 힙 == 항상 완전 이진 트리
  • O(log N) 은 비교적 짧은 시간입니다.

요소 제거

알고리즘 (일반적으로 '요소 추가'보다 구현코드가 더 길고 정점끼리 자리를 더 많이 바꿉니다.)

• 루트 정점에서만 제거가 가능합니다.
  1. 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치합니다.
  2. 루트 정점의 두 자식 정점 중 우선순위가 더 높은 정점과 바꿉니다.
  3. 따라서, 가장 우선순위가 높은 정점이 루트가 됩니다. (최대 힙 완성)
  4. 두 자식 정점이 우선순위가 더 낮을 때 까지 반복합니다.
  5. 결국, 1) 가장 우선순위가 높은 정점은 루트가 되고 2) 모든 부모 정점은 항상 자식 정점보다 우선순위가 높게 됩니다.

시간복잡도

• O(log N) 시간복잡도를 가집니다. (최악의 경우)
  • 완전 이진 트리의 높이가 log N 이기 때문입니다
  • 힙 == 항상 완전 이진 트리
  • O(log N) 은 비교적 짧은 시간입니다.

JS 에서의 구현

깃허브: https://github.com/HyeonWooGa/algorhithm-code-snippet

---

자료구조의 목적

소요시간

• 힙(Heap)에 대해서 이해하고 또 구현해보는데 결국 3시간 가량이 걸렸습니다.

하지만

• 너무 재미있습니다...😭 (감동)

그리고

• 아무 생각없이 코딩 테스트를 위해 알고리즘, 자료구조 공부를 하고 있었는데

오늘

• 자료 구조의 최종 목적이 결국, 데이터를 잘 정리하고 활용하기 위한 것이라고 자연스럽게 느껴지게 되었습니다.

---