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


  • 62
    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;
        }
    

  • 0
    D

    I was just looking for a clear explanation for the difference. Thanks a lot!


  • 0
    S

    yes, they are different, I was confused about this for a long time.
    But, actually, in Java, PQ class is automatically build in with Heap implementation.
    "An unbounded priority queue based on a priority heap." https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html
    So, if you use Java, you can simply consider Heap as PQ.


Log in to reply
 

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