Difference between Priority-Queue and Heap, and C++ implementation


  • 61
    M

    I have seen lots of solutions confuse priority queue with heap. I find a good link and list the talk below.

    Concept:

    1.Heap is a kind of data structure. It is a name for a particular way of storing data that makes certain operations very efficient. We can use a tree or array to describe it.

       18
      /	\
     10	 16
    / \   / \
    9  5  8  12
    
    18, 10, 16, 9, 5, 8, 12
    

    2.Priority queue is an abstract datatype. It is a shorthand way of describing a particular interface and behavior, and says nothing about the underlying implementation.

    A heap is a very good data structure to implement a priority queue. The operations which are made efficient by the heap data structure are the operations that the priority queue interface needs.

    Implementation: c++

    1.priority_queue: we can only get the top element (from ChiangKaiShrek's solution)

    struct compare {
        bool operator()(const ListNode* l, const ListNode* r) {
            return l->val > r->val;
        }
    };
    ListNode *mergeKLists(vector<ListNode *> &lists) { //priority_queue
        priority_queue<ListNode *, vector<ListNode *>, compare> q;
        for(auto l : lists) {
            if(l)  q.push(l);
        }
        if(q.empty())  return NULL;
    
        ListNode* result = q.top();
        q.pop();
        if(result->next) q.push(result->next);
        ListNode* tail = result;            
        while(!q.empty()) {
            tail->next = q.top();
            q.pop();
            tail = tail->next;
            if(tail->next) q.push(tail->next);
        }
        return result;
    }
    

    2.make_heap: we can access all the elements (from my answer for that solution)

    static bool heapComp(ListNode* a, ListNode* b) {
            return a->val > b->val;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) { //make_heap
        ListNode head(0);
        ListNode *curNode = &head;
        vector<ListNode*> v;   
        for(int i =0; i<lists.size(); i++){
            if(lists[i]) v.push_back(lists[i]);
        }
        make_heap(v.begin(), v.end(), heapComp); //vector -> heap data strcture
    
        while(v.size()>0){
            curNode->next=v.front();
            pop_heap(v.begin(), v.end(), heapComp); 
            v.pop_back(); 
            curNode = curNode->next;
            if(curNode->next) {
                v.push_back(curNode->next); 
                push_heap(v.begin(), v.end(), heapComp);
            }
        }
        return head.next;
    }
    

    If there is something wrong, please figure it out. Hoping to learn more about them.


  • 0
    X

    I have been confused about priority_queue and heap for a long time, thanks for pointing our :)


  • 2
    M

    Maybe use a dummy node can make the code more concise?

    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            priority_queue<ListNode*, vector<ListNode*>, compare> q;
            for (auto l : lists) {
                if (l) {
                    q.push(l);
                }
            }
            
            ListNode pre(0);
            ListNode *node = &pre;
            while (q.size()) {
                ListNode *top = q.top();
                q.pop();
                node->next = top;
                node = node->next;
                if (top->next) {
                    q.push(top->next);
                }
            }
            return pre.next;
        }
        
        struct compare {
            bool operator()(const ListNode* l1, const ListNode* l2) {
                return l1->val > l2->val;
            }
        };
    };

  • 1
    W

    Write short code for fun~

    ListNode* mergeKLists(vector<ListNode*>& lists) {
            auto mycomp = [&](ListNode* n1, ListNode* n2) {return n1->val > n2->val;};
            priority_queue<ListNode*, vector<ListNode*>, decltype(mycomp)> pq(mycomp);
            for(auto ptr: lists) if(ptr) pq.push(ptr);
            ListNode* dummy = new ListNode(-1);
            for(ListNode* run = dummy; !pq.empty(); run = run->next) {
                auto cur = pq.top(); pq.pop();
                if(cur->next) pq.push(cur->next);
                run->next = cur;
            }
            return dummy->next;
        }
    

  • 1
    N

    This solution times out :(.


  • 0
    Z

    Nice code takes advantage of heap structure but TLE for some cases.


  • 1
    L

    what is time complexity of the heap solution?


  • 0

    Time complexity: O(Nlogk), where N is the length of final merged list length and k is the number of lists?


  • 0
    H
    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            ListNode pre(0);
            ListNode* node = &pre;
            auto compare = [](ListNode* l1, ListNode* l2){return l1->val > l2->val;};
            priority_queue<ListNode*, vector<ListNode*>, decltype(compare)> q(compare);
            
            for(auto l: lists)
                if(l)
                    q.push(l);
            
            while(q.size()){
                ListNode* top = q.top();
                q.pop();
                node->next = top;
                node = node->next;
                
                if(top->next)
                    q.push(top->next);
                
            }
            
            return pre.next;
        }
    };

  • 2
    Y

    Beat 98% cpp! use map to solve, easy understand

    ListNode *mergeKLists(vector<ListNode *> &lists) {
            multimap<int, ListNode*> mp;  //a new multimap<val, head> to store data
            for (auto p : lists) {
                if (p != NULL) { //every List , <val, ListHead>, if ListHead != NULL
                    mp.insert(make_pair(p->val, p)); 
                }
            }
            ListNode *ret = NULL;
            ListNode *p = NULL;
            while (!mp.empty()) {
                multimap<int, ListNode*>::iterator it = mp.begin();
    //it is the iterator of max value, because map use RB tree to implement
                if (ret == NULL) {
                    ret = it->second;
                    p = ret;
                } else {
                    p->next = it->second;
                    p = p->next;
                }
                if (it->second->next != NULL) {
                    mp.insert(make_pair(it->second->next->val, it->second->next));
                } //add the next node of the max value of list 
                mp.erase(it); //delete the max value which already add the result list
            }
            return ret;
        }
    

  • 0
    B

    Same logic as others using lamda expression, and what I hope is a clean implementation. And since we didn't create anything new, there's no pointer clean up needed.

    ListNode* mergeKLists(vector<ListNode*>& lists) {
            auto cmp=[](ListNode* a, ListNode* b) {
                return a->val>b->val;
            };        
            priority_queue<ListNode*,vector<ListNode*>,decltype(cmp)> pq(cmp);
            ListNode dummy(0),*p=&dummy;
            
            for (ListNode *node:lists) if (node) pq.push(node);
            
            while (!pq.empty()) {
                if (pq.top()->next) pq.push(pq.top()->next);
                p=p->next=pq.top();
                pq.pop();
            }
            
            return dummy.next;
        }
    

Log in to reply
 

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