Clean C++ code using maxHeap. With explanation


  • 4
    E
    class Solution {
    
    public:
        
        // custom comparator used to compare between two listNode pointers. 
        // note : all pointers to be compared is supposed to be valid pointers.
        struct comparator
        {
            bool operator() ( ListNode* i, ListNode* j)
             {
                return i->val > j->val;
             }
        };
    
        ListNode *mergeKLists(vector<ListNode *> &lists) 
        {
        
           // shortcut for edge cases. 
           if (lists.size() == 0) return NULL;
           if (lists.size() == 1) return lists[0]; 
           
           // initialize the maxHeap. 
           priority_queue<ListNode*, std::vector<ListNode*>, comparator> maxHeap;
           
           // push the head of each of the items in list. 
           for (int i = 0; i< lists.size(); i++)
           {
               if (lists[i]!= NULL) maxHeap.push(lists[i]);
           }
           
           // shortcut if we failed to find even one valid list. 
           if (maxHeap.size() == 0) return NULL;
           
           // build the empty node as the return pointer.
           ListNode returnVal = ListNode(-1), *tmp = &returnVal; 
          
           // loop until the heap is empty. 
           while (maxHeap.size() >0)
           {
               tmp->next = maxHeap.top();
               maxHeap.pop();
               tmp = tmp->next;
               if (tmp->next != NULL && maxHeap.size()!=0)
               {
                   maxHeap.push(tmp->next);
               }
           }
           
           return returnVal.next;
        }
    };

  • 0
    F

    How much is the run time?


  • 0
    C

    is it a min head? because top() function return the smallest node.


  • 0
    F

    some boundary checks can be avoided

    ListNode* mergeKLists(vector<ListNode*>& lists) {
    	ListNode* head = NULL;
    	ListNode** it = &head;
    	priority_queue<ListNode*, vector<ListNode*>, compare> q;
    	for (int i = 0; i < lists.size(); i++) {
    		if (lists[i]) q.push(lists[i]);
    	}
    	while (!q.empty()) {
    		*it = q.top();
    		q.pop();
    		if ((*it)->next) {
    			q.push((*it)->next);
    		}
    		it = &((*it)->next);
    	}
    	return head;
    }

  • 0
    H

    where is the explaination


  • 0
    P

    this is actually Min Heap,


Log in to reply
 

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