Why pop_heap() won't work?


  • 0
    P

    In this problem, I used ( vector< ListNode* > list_heap ) to store the point to each list node, and make them as a heap, but when I debug I found that all of the pop_heap() operation won't work. It's a little wired. Anyone knows the reason? Thanks a lot!

    class Solution {
    public:
    
        struct LessThanLinkedList
        {
            bool operator() ( const ListNode * l1, const ListNode * l2) const
            {
                return( l1->val > l2->val );
            }
        };
    
        ListNode *mergeKLists(vector<ListNode *> &lists) {
            
            int idx;
            bool ball_list_null;
            ListNode * pNode;
            ListNode *new_head;
            
    
            ball_list_null = true;
            
            for( idx = 0; idx < lists.size(); idx++ )// judge whether all lists are null
            {
                if( NULL != lists[idx] )
                {
                    ball_list_null = false;
                    break;
                }
            }
            if( true == ball_list_null )
                return(NULL);
            
            vector< ListNode* > list_heap;
            for( idx = 0; idx < lists.size(); idx++ ) // put the element into the heap vector
            {
                if( NULL != lists[idx] )
                {
                    pNode = lists[idx];
                    while( NULL != pNode )
                    {
                        list_heap.push_back( pNode );
                        pNode = pNode->next;
                    }
                }
            }
            
            std::make_heap( list_heap.begin(), list_heap.end(), LessThanLinkedList() );
            
            if(list_heap.size() > 0) 
            {
                new_head = list_heap[0];
                std::pop_heap( list_heap.begin(), list_heap.end(), LessThanLinkedList() ); //pop won't work!
            }
            
            if( list_heap.size() == 0 )
            {
                new_head->next = NULL;
            }
            else
            {
                pNode = new_head;
                while( list_heap.size() >0 )
                {
                    pNode->next = list_heap[0];
                    std::pop_heap( list_heap.begin(), list_heap.end(), LessThanLinkedList() ); // pop won't work!
                    pNode = pNode->next ;
                }
                pNode->next = NULL;
            }
            return( new_head );
            
        }
    };

  • 0
    G

    Can you be more precise about "doesn't work"? According to the doc, pop_heap() moves the first element of the heap to the end of the heap, do recursive heap update, so that the heap's new size is reduced by one. You can find the "popped' element in the end of the heap.


  • 0
    P

    Thanks a lot for your answer. I asked this question in another website and they answered it.

    http://stackoverflow.com/questions/26495293/c-stl-pop-heap-not-work

    The key point is that the pop operation will not delete elements, but keep it at the end which will make loop condition "while( list_heap.size() >0 )" will be true for ever.


Log in to reply
 

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