우선순위 큐를 위해 만들어진 자료구조, heap

큐

일반적인 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다.
즉, 어떤 부가적인 조건 없이 먼저 들어온 데이터가 먼저 나가는 구조이다.

우선순위 큐(Priority Queue)는 들어간 순서에 상관없이, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.
우선순위 큐는 배열, 연결 리스트, 힙으로 구현이 가능하다.
이 중에서 힙(Heap)을 이용하여 구현하는 것이 가장 효율적이다.

힙(heap)

• 완전 이진 트리의 종류.
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조.
• 힙 속성(최대힙Max Heap일 경우 부모 노드는 반드시 자식 노드보다 값이 커야 한다는 규칙)을 만족하는 거의 완전한 트리.
  • 일종의 느슨한 정렬 상태(반정렬 상태)를 유지한다.
    • 큰 값이 상위 레벨에 있고, 작은 값이 하위 레벨에 있다는 정도.
    • 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리.
• 힙 트리에서는 중복된 값을 허용한다.
  • 이진 탐색 트리에서는 중복된 값을 허용하지 않는다.

종류

최대 힙(max heap)

• 부모 노드는 항상 자식 노드보다 크거나 같아야 한다.
• 가장 큰 값이 루트 노드에 있다.
• key(parent) >= key(child)

최소 힙(min heap)

• 부모 노드는 항상 자식 노드보다 값이 작거나 같아야 한다.
• 가장 작은 값이 루트 노드에 있다.
• key(parent) <= key(child)

구현

• 힙은 일반적으로 배열로 표현한다.
• 개발 편의성과 가독성 때문에 배열 인덱스 1부터 사용한다.
  • 구현을 쉽게 하기 위해 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
  • 예를 들어, 루트 노드의 오른쪽 노드의 번호는 항상 3이다.

• 힙에서의 부모 노드와 자식 노드의 관계
  • 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
  • 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
  • 부모의 인덱스 = (자식의 인덱스) / 2