[자료구조] 우선순위 큐(Priority Queue), 힙(Heap)

🌵우선순위 큐(Priority Queue) 란?

큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조
우선순위 큐(Priority Queue)는 들어온 순서와 상관없이, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조

일반적으로 힙(Heap) 구조를 사용해 구현한다.

 

* 힙으로 구현하는 이유는?

- 힙의 경우 삭제나 삽입 과정에서 모두 부모와 자식 간의 비교만 계속 이루어진다.

이진 트리의 높이가 하나 증가할 때마다 저장 가능한 자료의 개수는 2배 증가하며, 비교 연산 횟수는 1회 증가

즉, 삭제나 삽입 모두 최악의 경우에는 O(log2n)의 시간 복잡도를 가진다. 

이처럼 배열이나 연결 리스트가 삭제에서는 시간 복잡도의 우위를 점할지라도, 삽입의 시간 복잡도가 힙(Heap) 기반이 월등하기 때문에, 편차가 심한 배열과 연결리스트보다는 힙으로 구현

 

 

 

🌵힙(Heap)이란?

힙(Heap)은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조

• 완전이진트리(Complete Binary Tree) 형태
• 부모노드와 서브트리간 대소 관계가 성립 (반정렬 상태)
• 이진탐색트리(BST)와 달리 중복된 값 허용

 

 

🌵힙(Heap)의 종류

(1) 최대 힙 (Max Heap)

: 완전 이진트리이면서, 루트 노드로 올라갈수록 저장된 값이 커지는 구조

- 부모 노드의 키 값이 자식 노드보다 크거나 같은 완전이진트리

- key(부모노드) >= key(자식노드) 

 

* 숫자가 클수록 우선순위가 높다

 

 

(2) 최소 힙 (Min Heap)

: 완전 이진트리이면서, 루트 노드로 올라갈수록 값이 작아지는 구조

- 부모 노드의 키 값이 자식 노드보다 작거나 같은 완전이진트리

- key(부모 노드) <= key(자식 노드)

* 숫자가 작을수록 우선순위가 높다

 

🌵힙(Heap)에서의 데이터 저장

위와 같은 최소 힙에서의 데이터 저장을 가정하자

 

1. 새로 들어올 노드를 우선순위가 가장 낮다는 가정을 하고 ‘맨 끝 위치’에 저장

맨 끝 위치에 저장한다는 것도 완전 이진트리를 만족하는 틀 안에서 이루어져야 한다.

ex) 위 그림에서는 새로 들어올 노드가 3이라고 가정하면 노드 7의 left Child 로 들어가야 한다.

 

2. 부모 노드와 우선 순위를 비교해서 위치 변경 ->  위치가 맞을 때까지 계속 반복

ex) 위 그림에서 새로운 노드 3은 부모노드의 7보다 숫자가 작기 때문에 우선순위가 높으므로 노드 7과 노드 3의 위치를 바꿔준다.

       노드 5의 경우도 마찬가지로 노드 3 보다 우선순위가 낮기 때문에 위치를 교환한다.

       노드 1의 경우에는 새로운 노드 3보다 우선순위가 높으므로 위치를 변경하지 않는다.

 

- 힙 삽입의 시간 복잡도는  O(log2n)

 

 

🌵힙(Heap)에서의 데이터 삭제

우선순위 큐에서의 pop은 우선순위가 가장 높은 데이터를 빼낸다는 의미

힙에서 가장 우선순위가 높은 데이터는 루트노드인데, 이 루트 노드를 삭제하면서 힙의 구조를 그대로 유지하는 것이 관건

힙 구조를 유지하기 위해 heapq모듈의 heapify를 사용한다.

 

1. 루트 노드를 삭제 

ex) 위 그림인 경우, 노드 1 삭제

 

2. 루트 노드가 삭제된 빈자리에 완전이진트리의 마지막 노드를 가져온다.

ex) 위 그림일 경우, 노드 7가 루트 노드 들어가게 된다.

 

3. 루트 자리에 위치한 새로운 노드를 자식 노드와 비교하여 교환
이때 최대 힙인 경우 자식노드 중 더 큰 값과 교환을 하며, 최소 힙인 경우 더 작은 값과 교환

 

4. 정상적인 힙트리가 될 때까지 반복

 

 

 

🌵관련문제

🥈[백준 알고리즘 1927번 : 최소 힙]

https://www.acmicpc.net/problem/1927

1927번: 최소 힙

[SOLUTION]

https://gyurisinzorba.tistory.com/85

[Python] 백준 알고리즘 1927번 : 최소 힙

---

 

🥈[백준 알고리즘 11279번 : 최대 힙]

https://www.acmicpc.net/problem/11279

11279번: 최대 힙

[SOLUTION]

https://gyurisinzorba.tistory.com/86?category=1019803 

[Python] 백준 알고리즘 11279번 : 최대 힙

 

---

 

🥈[백준 알고리즘 11286번 : 절댓값 힙]

https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙

[SOLUTION]

https://gyurisinzorba.tistory.com/91?category=1019803 

[Python] 백준 알고리즘 11286번 : 절댓값 힙

---

🥈[백준 알고리즘 15903번 : 카드 합체 놀이]

https://www.acmicpc.net/problem/15903

15903번: 카드 합체 놀이

[SOLUTION]

https://gyurisinzorba.tistory.com/99?category=1019803 

[Python] 백준 알고리즘 15903번 : 카드 합체 놀이

---

🥈[백준 알고리즘 2075번 : N번째 큰 수]

https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

[SOLUTION]

https://gyurisinzorba.tistory.com/92?category=1019803 

[Python] 백준 알고리즘 2075번 : N번째 큰 수

---

🥇[백준 알고리즘1655번 : 가운데를 말해요]

https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

[SOLUTION]

https://gyurisinzorba.tistory.com/93?category=1019803 

[Python] ⭐️백준 알고리즘 1655번 : 가운데를 말해요

 

 

 

 

~ 해당 포스팅은 업데이트 중 ~