[자료구조] 우선순위큐(Priority Queue)에 사용되는 Heap 자료구조

서론

우선순위큐를 사용하며 이 자료구조를 정확히 이해하기 위해선 그 전에 힙을 완벽히 이해하여야 겠다는 생각이 들었다.
이전과 같이 모르는 것을 그냥 넘어가는 일이 없도록 하자.

Heap

Priority Queue

• 데이터에 가중치를 두어 가중치의 오름차순 또는 내림차순으로 정렬한 큐.
• 주로 시뮬레이션 시스템, 작업 스케줄링에 사용.
• 배열 또는 연결 리스트로도 구현이 가능하지만 힙 자료구조를 사용하는 것이 가장 효과적.
  • 리스트를 사용하여 구현한 경우 삽입의 시간 복잡도는 O(1), 삭제의 시간 복잡도는 O(n).
  • Heap을 사용하여 구현한 경우 삽입과 삭제 모두 시간 복잡도는 O(logN)

Heap 자료구조의 개념

• 배열을 기반으로 한 완전 이진 트리로 구성.
• 일반적 이진 트리와 다르게 중복된 값을 허용.
• Heapify 과정을 통해 원하는 동작을 완수.
• 삭제의 경우 항상 루트노드를 제거하는 방식으로 작동.

Heapify

• Heap 자료구조에 값을 삽입 또는 삭제할 경우 트리의 값이 올바른 위치에 자리할 때 까지 반복하는 과정
• min Heapify
  • 추가 과정
    추가된 데이터를 트리의 가장 마지막 인덱스에 삽입 후, 루트 노드가 자식 노드보다 항상 작게 트리를 재구성.
  • 삭제 과정
    트리의 루트 노드를 삭제 후, 인덱스의 가장 마지막 데이터를 트리의 루트 노드로 옮긴 후 루트 노드가 자식 노드보다 항상 작게 트리를 재구성.
• max Heapify
  min Heapify와 반대.