C# Using MinHeap (PriorityQueue) Implemented Using SortedDictionary


  • 3
    R

    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)
            {
                if(!map.ContainsKey(val))
                {
                    map.Add(val, new Queue<ListNode>());
                }
    
                map[val].Enqueue(node);
            }
    
            public ListNode PopMin()
            {
                int minKey = map.First().Key;
                ListNode node = map[minKey].Dequeue();
    
                if (map[minKey].Count == 0)
                    map.Remove(minKey);
    
                return node;
            }
        }
        
        public ListNode MergeKLists(ListNode[] lists) 
        {
            MinHeap heap = new MinHeap();
            foreach (var node in lists)
            {
                if(node == null)
                    continue;
                
                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;
                }
                else
                {
                    curr.next = node;
                    curr = curr.next;
                }
            }
    
            return newHead;
        }
    }
    

  • 0

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


  • 0
    L

    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.