💡우선순위 큐
- 기존 큐, 스택과 같은 자료구조와 비슷한 추상 자료형이지만 특별히, 각 요소의 우선순위와 연관돼 있다.
- 우선순위 큐는 특정 조건인 우선순위에 따라 값을 추출하는 자료구조다.
- 대표 예시로 최대값 추출을 들 수 있다
- [1,4,2,7,3] 이라는 값에서 최대값을 추출하는 우선순위 큐가 있다고 가정하면, 남아 있는 값들의 최대값을 우선순위로 추출하여 7, 4, 3, 2, 1 순으로 추출 될 것이다.
- 여기서 시간복잡도의 개념을 고려하면 기본 정렬 기능을 통해 O(n) 시간복잡도를 기대할 수 있다.
- 하지만 더 효율적인 방법으로 힙 정렬 등 힙 자료구조와 연동으로 새로운 접근도 가능할 수 있다는 사실을 인지하자.
💡우선순위 큐 활용 문제
- k개의 정렬된 리스트를 1개의 리스트(정렬된 상태)로 병합하기
(Merge all the linked-lists into one sorted linked-list and return it.)
- 예시
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
💡우선순위 큐 아닌 단순 풀이
- 나만의 풀이
- 리트코드에서는 통과할 수 없다.
- 왜냐면 input 값으로 들어오는 lists값이 ListNode라는 연결리스트 자료구조이기 때문에 단순 List로 해결 X
def simple_solution(lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
total_values=[]
for each_list in lists:
total_values.extend(each_list)
total_values.sort()
return total_values
💡우선순위 큐 구현
- 우선순위 큐는 heapq 자료구조와 관련이 깊다
- python은 PriorityQueue 클래스를 지원하고 있지만 이 클래스 내부에서도 heapq 모듈을 활용하여 우선순위 큐를 구현하고 있다.
- PriorityQueue 클래스는 멀티 스레드 활용 시 스레드 세이프 기능을 제공하고 있어 스레드 활용 프로그래밍 시 안전한 작동을 보장한다.
- 하지만 실제 파이썬 특성상 멀티 스레드 활용 시 세이프 기능이 큰 의미가 없으며, 활용도가 낮다.
- 그래서 대부분 heapq를 활용하여 구현한다.
- heap 자료구조는 최소값을 가지고 올 수 있고, heappop 실행할 때마다 내부 값을 재정렬한다.
from heapq import heappush, heappop
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
# 초기 값이 [None, None] 이 상태로 들어간다
root = result = ListNode(None)
"""
print(result.val) # ==> None
print(result.next) # ==> None
"""
heap = []
# 각 연결 리스트의 루트를 힙에 저장한다
for i, lst in enumerate(lists):
# 이 말은 lists 노드의 i번째 값이 있으면(None이 아니면)
if lists[i]:
# heappush의 인자값이 중복이 있다면, 에러를 발생하기 때문에
# 중복된 값을 구분할 수 있는 추가 인자값이 필요하다.
# heappush 활용해서 값을 추가할 때 heap 정렬의 구조에 따라 들어가는걸 확인할 수 있음
heappush(heap, (lists[i].val, i, lists[i]))
"""
Input : [ListNode([1,4,5]),ListNode([1,3,4]),ListNode([2,6])]
Output :
[([1, 3, 4], 1, <__main__.ListNode object at 0x0371A590>),
([1, 4, 5], 0, <__main__.ListNode object at 0x0371A570>),
([2, 6], 2, <__main__.ListNode object at 0x0371A1F0>)]
"""
# heap 자료구조 안에 데이터가 다 없어질때까지 로직 구현
while heap:
# heappop으로 값을 가져오면 가장 작은 노드의 연결 리스트부터 차례대로 나온다.
# 여기서 node는 tuple type ex) ([2, 6], 2, <__main__.ListNode object at 0x0371A1F0>)
node = heappop(heap)
# 위에서 설정한 연결 리스트의 index값
idx = node[1]
# 연결 리스트로 정의된 객체 자체를 정답 값으로 업데이트
result.next = node[2] # => ex) <__main__.ListNode object at 0x0371A1F0>
# result 값 갱신
result = result.next
if result.next:
# heap 자료구조에 다시 추가한다.
heappush(heap, (result.next.val, idx, result.next))