[자료구조] 우선순위 큐와 힙

[우선순위 큐(PriorityQueue)란?]

말 그대로 우선순위(Priority)를 가진 큐(Queue)임

앞서 배운 QUEUE에서는 First-in-First-Out 이였지만
여기서는 OUT시에 우선순위를 바탕으로 OUT 시킨다.

들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다

 

 

그럼 해당 큐 자료구조에서 우선순위를 어떻게 추가해야할까?

 

바로 별도의 우선순위(Priority) 변수를 지닌 구조체를 만들고 이를 하나의 데이터로 생각해서 진행하면 된다

 

그럼 우선순위를 따지는 조건은?

완전 간단한 우선순위 판단 방법이면

예를 들어

 

우선순위 변수가 int형이고 

값이 더 작은게 우선순위가 높은 것

또는 큰게 더 높은 것

이라면 별도로 우선순위 판단함수를 작성하지 않아도 되지만,

복잡한 방법으로 우선순위를 계산해야 한다면

별도의 우선순위 계산함수를 만든다음 우선순위 큐에 

함수포인터 형식으로 인자를 받게끔 만들어
해당 함수를 인자로 전달해주면 댐

 

---

[우선순위 큐 구현 방법]

1. 배열
2. 리스트
3. 이진트리 == 힙(HEAP)

 

이 세 가지 방법 중 힙(HEAP)으로 구현하는게 원칙이다.

 

---

[왜 우선순위 큐를 구현하는데 힙이 쓰이는가]

 

시간복잡도 때문이다.

배열과 링크드 리스트는 총 데이터가 N개라 가정했을때
O(N)이지만 ( == 비교 연산을 최악의 상황에서 N번을 해야함 ) 

앞서배운 트리형식으로 표현되는 힙구조는 O(log2n) 이다.
( 맨 마지막 단말노드라 하더라도 log2n 만큼만 비교연산을 수행하면 된다!! )

따라서 시간복잡도에서 너무나도 큰 차이, 더욱 효율적이기에 

우선순위 큐를 표현하는데 힙이 쓰이는 것이다.

 

---

[힙(HEAP)]

 

힙(HEAP)은 우선순위 큐를 표현하기 위해 등장한 자료구조이다.

힙은 앞서 배운 이진 트리로 표현된다.

이진 트리 중에서도 완전 이진 트리이다!!

이게 가장 중요하다!

힙은 "완전 이진 트리"

 

"완전 이진 트리" 이기 때문에 힙을 구현하기 위해 배열을 사용하는 이유가 설명된다
"완전 이진 트리"란 위에서 아래로 , 왼쪽에서 오른쪽으로 차곡차곡 만들어나가는 트리이다

 

---

[힙을 표현하는데 배열을 쓰는 이유]

 

 

일단 binarytree를 표현할때

node를 사용한 연결리스트로 표현할 수 도 있고 배열로 표현할 수 도 있음.

따라서 연결리스트로도 이진트리를 표현할 수 있는데 

왜 굳이 배열을 사용하여 표현하는 것을 원칙으로 하는 것일까

 

1. parent child 를 계산하기 쉽다

 

 한 노드를 알면 그 노드의 부모 또는 자식들을 인덱스로 바로 접근이 가능하기 때문이다

 

2. Random Access를 통해 마지막 위치 노드 추가가 쉽다

 

node를 사용한 연결리스트로 힙을 구현하면,
HEAP Insert 과정에서 새로운 노드를 HEAP의 "마지막 위치"에 추가하는 것이 쉽지 않다.
linked list로 구현하면 맨 마지막 노드를 추가할때 root node에서 
쭉쭉 내려가 마지막 위치를 찾고 새 데이터를 추가해야하지만
배열 사용시 heapArr[데이터개수] 가 새 데이터가 추가될 자리이기 때문이다

 

hp->heapArr[hp->numOfData]

이렇게 별도의 과정없이 바로 추가할 수 있기 때문임 ㅇㅇ

 

---

그래서 최종적으로 꼭 알고 가야하는 것은...

1. 힙(HEAP)이란 무엇이고, 어떤 방식으로 힙 구조를 표현할 수 있는가? 어떤 도구들로 표현할 수 있는가?

2. 왜 우선순위 큐를 수 많은 표현방식 중에서도 힙(HEAP)으로 표현하는 것인가

3. "우선순위 큐(Priority Queue)" 와 "힙(Heap)"은 같은게 아니다.

 

이 둘이 왜 다른지, 어떻게 다른 건지 이해하고 있어야한다.

매우 근본적인 질문이지만 어찌보면 가장 핵심적인 질문이다.

 

4. 우선순위 큐에 힙이 쓰이는 이유와 힙을 표현하는데 배열이 사용되는데 이유를 구별할 줄 알아야한다.

 

또한 각각 이유를 설명할 수 있어야한다.

 

1) 우선순위 큐에 힙이 쓰이는 이유 = 우선순위 큐에 이진트리가 쓰이는 이유

=> 시간복잡도 때문. O(logN)으로 정렬 가능

 

2) 힙을 표현하는데 배열이 쓰이는 이유

=> Random Access 가능. parent child 노드 계산하기 쉽다. 완전이진트리라 계산방법이 정해져있다.