자료구조와 알고리즘 - 힙

본 내용은 프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 토대로 작성하였습니다.

1. 힙이란?

• 이진 트리 형태
• 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬되는 특징이 있음
• 우선순위 큐를 구현하기 위한 가장 적합한 방법
  • 힙과 우선순위 큐가 같은 것이 아님
• 우선순위가 높은 요소를 루트에 배치
• 최대 힙(Max Heap): 루트가 가장 큰 값이 되는 힙
• 최소 힙(Min Heap): 루트가 가장 작은 값이 되는 힙
• JavaScript에서는 직접 구현해야 함

우선 순위 큐

• 우선 순위가 높은 요소가 먼저 나가는 큐
• 자료구조가 아닌 개념
• 구현하는 방법은 다양하게 존재

2. Heap의 동작

Heap 요소 추가

• 요소가 추가될 떄는 트리의 가장 마지막 정점에 위치
• 추가 후 부모 정점보다 우선순위가 높다면 부모 정점과 순서를 바꿈
  • 이 과정을 반복하면, 우선순위가 가장 높은 정점이 루트가 됨
• 완전 이진트리의 높이는 logN이기에 힙의 요소 추가 알고리즘은 O(logN) 시간 복잡도를 가짐

Heap 요소 제거

• 요소 제거는 루트 정점만 가능
• 루트 정점이 제거된 후, 가장 마지막 정점이 루트에 위치
• 루트 정점의 두 자식 정점 중 더 우선순위가 높은 정점과 바꿈
• 두 자식 정점이 우선순위가 더 낮을 때 까지 반복
• 완전 이진 트리의 높이는 logN이기에 힙의 요소 제거 알고리즘은 O(logN) 시간복잡도를 가짐

Reference

프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript