[자료구조] 우선순위 큐 구현

💡우선순위 큐

• 기존 큐, 스택과 같은 자료구조와 비슷한 추상 자료형이지만 특별히, 각 요소의 우선순위와 연관돼 있다.
• 우선순위 큐는 특정 조건인 우선순위에 따라 값을 추출하는 자료구조다.
• 대표 예시로 최대값 추출을 들 수 있다
  • [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))