Chap09. 우선순위 큐와 힙 구조

 

이전에 구현했던 우선순위 큐:

https://tose33.tistory.com/562

c++) Priority Queue 구현

 

 

우선순위 큐는 우선순위가 높은 데이터가 먼저 나오도록 하는 자료구조다

 

우선순위 큐는 배열과 연결 리스트로 구현할수 있다.

하지만 배열로 구현될 경우, 데이터를 삽입 및 삭제할때 데이터를 한 칸씩 밀거나 앞으로 당기는 연산을 해야하고 또한 모든 데이터를 우선순위 비교를 해야한다.

연결 리스트의 경우 배열의 첫번째 문제점은 해결되지만 여전히 두번째 문제점이 남는다.

즉 배열과 연결 리스트로 우선 순위큐를 구현할 경우, 우선순위 큐의 노드의 수에 비례해 성능이 저하된다.

 

따라서 우선순위 큐는 주로 힙 구조로 구현된다.

 

 

힙 (Heap) 

- 우선순위 큐는 주로 Heap 구조로 구현된다.

 

- Heap 구조는 최댓갓 최솟값을 빠르게 찾기위해 고안된 완전 이진 트리를 기본으로한 자료구조다.

 

- 구현할때는 배열을 이용해 구현하며, 편의를 위해 시작 인덱스는 0이 아닌 1부터 시작된다. 

 

- 노드들의 인덱스는 다음과 같은 특성들을 갖고 있다.

• 노드 i의 부모 노드의 인덱스 = floor(i / 2) 
• 노드 i의 왼쪽 자식의 인덱스 = i * 2
• 노드 i의 오른쪽 자식의 인덱스 = i * 2 + 1 

 

힙에서의 데이터 삽입

힙에서는 데이터를 삽입한 이후에도 삭제한 이후에도 항상 힙 구조를 유지해야 한다. 

즉 부모의 우선순위가 항상 자식의 우선순위 보다 크거나 같아야 한다는 것.

 

힙에서의 데이터 삽입은 다음과 같이 이루어진다.

 

1. 마지막 위치 즉 트리의 마지막 레벨에서 가장 오른쪽 위치에 노드를 삽입한다.

2. 부모와 우선순위를 비교해 위치를 바꿔야 한다면 바꾼다.

2번을 루트 노드와 비교할때까지 반복한다.

 

 

힙에서의 데이터 삭제

삭제는 삽입의 과정을 반대로 수행한다고 보면 된다.

우선순위 큐의 데이터의 삭제는 가장 높은 우선순위의 데이터 삭제 즉 dequeue를 의미한다.

즉 루트 노드를 삭제하는 것인데 마찬가지로 삭제 이후로도 힙 구조가 유지되어야 할 것이다.

 

루트 노드의 삭제 이후에도 힙 구조를 유지하는 방법은 다음과 같다.

 

1. 마지막 노드를 루트 노드의 자리로 옮긴다 (마지막 노드란 트리의 마지막 레벨의 가장 오른쪽 노드)

2. 왼쪽 자식, 오른쪽 자식 노드와 우선순위를 비교해 위치를 바꿔야 한다면 우선순위가 높은 자식과 위치를 바꾼다.

3. 2번을 자리를 바꾸지 않아도 될때까지 반복한다 

 

 

힙에서의 삽입과 삭제 연산의 시간복잡도

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

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

 

힙은 완전 이진 트리이다. (complete binary tree) 

https://www.programiz.com/dsa/complete-binary-tree

 

힙에서 삽입이나 삭제가 일어날때 데이터간의 비교는 부모와 자식 노드에서 일어나고, 이는 총 진행되는 비교 연산이 트리의 높이에 해당한다는 것을 알 수 있다.

 

완전 이진 트리이기 때문에 저장 할 수 있는 데이터의 수는 트리의 높이가 1 증가할때마다 두배씩 늘어난다.

즉 데이터의 수가 두배 늘어날때마다 비교 연산의 횟수가 1회 증가한다. 

==> O(logN)