힙(우선순위 큐)

힙(Heap)

• 힙이란?
  • 완전 이진트리 기반의 우선순위 큐(Priority Queue)를 구현하기 위한 자료구조
• 종류
  • 최대 힙(Max Heap) : 부모 노드의 값이 자식 노드보다 항상 큼
  • 최소 힙(Min Heap) : 부모 노드의 값이 자식 노드보다 항상 작음
• 특징
  • 완전 이진트리 구조로, 항상 왼쪽부터 차례대로 채워짐
  • 부모-자식간 우선순위 조건이 유지됨
  • 탐색 O(N), 삽입/삭제 O(logN)시간 복잡도를 갖음
• 힙 연산
  • 삽입(Insert) -> O(logN)
    • 새 데이터를 힙의 마지막 노드에 추가
    • 부모 노드와 비교하여 힙 속성을 유지하도록 교환(Swapping)
    • 올바른 위치를 찾을 때까지 반복
  • 삭제(Delete) -> O(logN)
    • 루트 노드(최대 or 최소)를 제거
    • 마지막 노드를 루트로 올림
    • 자식과 비교하면서 힙 속성을 유지하도록 교환
    • 올바른 위치를 찾을 때 까지 반복

---

우선순위 큐(Priority Queue)

• 우선순위 큐란?
  • 우선순위가 높은 데이터가 먼저 나오는 큐
  • 일반적으로 FIFO(First In First Out) 방식의 큐와 다르게 들어온 순서가 아니라 우선순위에 따라 먼저 처리
• 구현
  • 배열 기반
    • 정렬: O(N), 삽입 O(1)
    • 정렬X : 삽입 O(1), 삭제 O(N)
  • 이진 힙(Binary Heap)기반
    • 삽입/삭제 모두 O(logN)
  • 트리 기반(RB Tree, AVL Tree)
    • O(logN)
• 힙을 이용한 우선순위 큐
  • 힙을 사용하면 O(logN)에 우선순위가 높은 요소를 삽입/삭제 가능
  • 최소 힙을 사용하면 항상 가장 작은 값이 먼저 나오도록 정렬
  • 최대 힙을 사용하면 항상 가장 큰 값이 먼저 나오도록 정렬