C# Using MinHeap (PriorityQueue) Implemented Using SortedDictionary

  • 4

    We need to keep track of the heads of all lists at all times and be able to do the following operations efficiently:
    1- Get/Remove Min
    2- Add (once you remove the head of one list, you need to add the next from that list)

    A min heap (or a priority queue) is obviously the data structure we need here, where the key of the dictionary is the value of the ListNode, and the value of the dictionary is a queue of ListNodes having that value. (we need to queue the ones with the same value since Dictionary cannot have dupes)
    I implemented mine using a SortedDictionary of queues.
    SortedDictionary is internally implemented using a binary tree, and provides O(logn) for Add() and O(1) for PopMin(), so it's as efficient as it gets.

     * Definition for singly-linked list.
     * public class ListNode {
     *     public int val;
     *     public ListNode next;
     *     public ListNode(int x) { val = x; }
     * }
    public class Solution {
        public class MinHeap
            public SortedDictionary<int, Queue<ListNode>> map = new SortedDictionary<int, Queue<ListNode>>();
            public void Add(int val, ListNode node)
                    map.Add(val, new Queue<ListNode>());
            public ListNode PopMin()
                int minKey = map.First().Key;
                ListNode node = map[minKey].Dequeue();
                if (map[minKey].Count == 0)
                return node;
        public ListNode MergeKLists(ListNode[] lists) 
            MinHeap heap = new MinHeap();
            foreach (var node in lists)
                if(node == null)
                heap.Add(node.val, node);
            ListNode curr = null, newHead = null;
            while (heap.map.Count > 0)
                ListNode node = heap.PopMin();
                if (node.next != null)
                    heap.Add(node.next.val, node.next);
                if (curr == null)
                    curr = node;
                    newHead = curr;
                    curr.next = node;
                    curr = curr.next;
            return newHead;

  • 0

    Cleanest, easiest-understand C# solution I seen so far.

  • 0

    In a SortedDictionary, Remove method is not O(1), it is still O(logn)...
    It takes 30 lines of code to implement a Heap in C#....

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.