우선순위 큐와 힙

일반적으로 큐는 FIFO 구조로, 먼저 입력된 데이터가 먼저 출력되지만 

우선순위 큐는 각 데이터의 우선순위에 따라 나중에 입력된 데이터가 더 먼저 출력될 수도 있다.

우선순위 큐의 구현 방법에는 3가지가 있다.

1.배열

2.연결 리스트

3.힙

여기서 1,2방식은 각 각 문제점이 있다.

1. 데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야 한다.

2.삽입의 위치를 찾기 위해서 최악의 경우 저장된 모든 데이터와 우선순위의 비교를 진행해야 될 수도 있다.

2의 경우는 1,2방식 모두에게 해당하며 1의 경우는 1의 방식에 해당된다.

그래서 우선순위 큐는 힙이라는 자료구조를 이용해서 구현하는 것이 일반적이다.

힙이란?

이진트리이되 완전 이진 트리이며, 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다. 

즉, 루트 노드에 저장된 값이 가장 커야 한다.

힙의 데이터 저장과정

새로운 데이터는 마지막 위치에 저장하며, 부모 노드와 우선순위를 비교해서 바꾼다. 

바꾼 후에도 같은 과정을 계속 반복하며 자신의 위치를 찾는다.

힙의 데이터 삭제과정

마지막 노드를 루트 노드의 자리로 옮긴 다음에, 자식 노드와의 비교를 통해서 제자리를 찾아가게 한다.

힙의 성능 평가

배열 기반 데이터 저장의 시간 복잡도                            O(n)

배열 기반 데이터 삭제의 시간 복잡도                            O(1)

연결 리스트 기반 데이터 저장의 시간 복잡도                  O(n)

연결 리스트 기반 데이터 삭제의 시간 복잡도                  O(1)

힙의 경우는 트리의 높이에 해당하는 수만큼만 비교연산을 진행한다. 라는 의미로 받아들일 수가 있다.

힙 기반 데이터 저장의 시간 복잡도                            O(log n)

힙 기반 데이터 삭제의 시간 복잡도                            O(log n)

힙 자체의 구현에 어울리는 자료구조

완전 이진 트리의 구조를 갖고 그 구조를 유지해야 하는 힙은 배열을 기반으로 구현해야 한다.

이는 원칙으로 여겨지고 있는데 그 이유는 

"연결 리스트를 기반으로 힙을 구현하면 새로운 노드를 힙의 '마지막 위치'에 추가하는 것이 쉽지 않다."

특정 노드의 인덱스 값을 얻는 법

왼쪽 자식 노드의 인덱스 값                            부모 노드의 인덱스 값 X 2

오른쪽 자식 노드의 인덱스 값                         부모 노드의 인덱스 값 X 2 + 1

부모 노드의 인덱스 값                                   자식 노드의 인덱스 값 / 2