A c++ implement using heap


  • 0
    X

    We all know that multiset uses binary search tree to achieve high performance, which means we can also implment heap using multiset. Here is the codes for this problem that beats 68%(sometimes beats 55% due to leetcode internal reasons) of all c++ submitions(if you use pop_heap and push_heap, you can achieve a better performance of beating about 85% of all submits).

    class Solution {
    public:
        class comp{
        public:
            bool operator() (ListNode *a,ListNode *b){
                return a->val < b->val;
            }
        };
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            multiset<ListNode *,comp> min_heap;
            for (auto list:lists)
                if (list != NULL)
                    min_heap.insert(list);
            if (min_heap.empty()) return (ListNode*) NULL;
            ListNode head = ListNode(0), *current = &head;
            while(true){
                while(current->next!= NULL && current->next->val < (*min_heap.begin())->val)
                    current = current->next;
                if (current->next!= NULL)
                    min_heap.insert(current->next);
                current->next = *min_heap.begin();
                current = current->next;
                min_heap.erase(min_heap.begin());
                if (min_heap.empty()) 
                    break;
            }
            return head.next;
        }
    };
    

Log in to reply
 

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