[알고리즘][데크 & 우선순위 큐] - 2. k개 정렬리스트 병합

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다.

---

😎문제 : https://leetcode.com/problems/merge-k-sorted-lists/submissions/

 

 

k개의 정렬된 리스트를 1개의 정렬된 리스트로 병합하라.

---

[우선순위 큐]

• 우선순위 큐는 큐 또는 스택과 같은 추상 자료형과 유사하지만 추가로 각 요소의 '우선 순위'와 연결되어 있다.
• 우선순위는 가장 늦게 들어온 것을 뽑는 스택과 가장 일찍 을어온 것을 뽑는 큐와 달리 우선순위가 가장 높은 요소를 추출하는 자료형이다.
• 정렬 알고리즘을 사용하면 우선순위 큐를 만들 수 있다.
• 힙 정렬이 가장 효율적인 우선 순위 큐를 구현하는 방법이다.
  • 이외에도 최단 경로를 탐색하는 다익스트라 알고리즘 등 우선순위 큐는 다양한 분야에 활용되며 힙 자료구조와도 관련이 깊다.

[K개 정렬 리스트 병합]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
import heapq


class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        root = result = ListNode(None)

        heap = []

        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(heap,(lists[i].val,i,lists[i]))
        while heap:
            node = heapq.heappop(heap)
            idx = node[1]
            result.next = node[2]

            result = result.next

            if result.next:
                heapq.heappush(heap, (result.next.val, idx,result.next))
        return root.next