C ++ STL pop_heap not working

Question

I am trying to use a bunch to solve the "merge K lists" problem, which combines k sorted linked lists and returns them as one sorted list. I usually create a bunch of minutes to store the entire node list and use the predefined function LessThanLinkedList () to compare. But I found that the pop_heap () operations on line 62 and 75 never work. It will not remove the top of the heap, although I used a predefined comparison function as a parameter. Below is my code. I am using visual studio 2010 as an IDE. Does anyone know the reason? Many thanks for your help!

#include <stdio.h> #include <stdlib.h> #include <vector> #include <queue> #include <list> #include <numeric> struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; using namespace std; class Solution { public: static bool LessThanLinkedList( const ListNode * l1, const ListNode * l2) { 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++ ) { 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++ ) { if( NULL != lists[idx] ) { pNode = lists[idx]; while( NULL != pNode ) { list_heap.push_back( pNode ); pNode = pNode->next; } } } make_heap( list_heap.begin(), list_heap.end(), LessThanLinkedList ); if(list_heap.size() > 0) { new_head = list_heap[0]; pop_heap( list_heap.begin(), list_heap.end(), LessThanLinkedList );//not work } if( list_heap.size() == 0 ) { new_head->next = NULL; } else { pNode = new_head; while( list_heap.size() >0 ) { pNode->next = list_heap[0]; pop_heap( list_heap.begin(), list_heap.end(), LessThanLinkedList ); // not work pNode = pNode->next ; } pNode->next = NULL; } return( new_head ); } }; void main() { Solution xpfsln; ListNode *l1,*l2,*l3,*l4,*l5,*l6,*l7,*head; l1 = new ListNode(1); l2 = new ListNode(2); l3 = new ListNode(3); l1->next = l2; l2->next = l3; l3->next = NULL; vector<ListNode *> list_vec; list_vec.push_back(l1); head = xpfsln.mergeKLists( list_vec ); } 

Answer 1

pop_heap does not remove items from the container. He cannot, because he does not even have access to the container, just its elements. What it does (assuming that [begin, end) forms a real non-empty heap) reorders the elements so that the first element of the heap goes to the last element of the range and leaves [begin, end-1) actual heap. If you want to remove an element from a container, you just need to delete the last element of the container (for example, with pop_back() called) after calling pop_heap .

 pop_heap( list_heap.begin(), list_heap.end(), LessThanLinkedList ); list_heap.pop_back();