C++ STL pop_heap non funziona

Question

Sto cercando di usare l'heap per risolvere il problema "unire liste K" che sta unendo k liste ordinate e restituite come una lista ordinata. Generalmente creo un heap minimo per archiviare tutto il nodo della lista e uso la funzione predefinita LessThanLinkedList() per il confronto. Ma ho trovato che le operazioni di pop_heap() nella riga 62 e 75 non funzionano mai. Non rimuoverà la parte superiore dell'heap, anche se ho usato la funzione di confronto predefinita come parametro. Quello che segue è il mio codice. Sto usando Visual Studio 2010 come IDE. Qualcuno conosce la ragione? Grazie mille per il vostro aiuto!

#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 non rimuove elementi dal contenitore. Non può, dal momento che non ha nemmeno accesso al contenitore, solo i suoi elementi. Quello che fa (supponendo ovviamente che [begin, end) formi un heap valido, non vuoto) è riorganizzare gli elementi in modo tale che il primo elemento dell'heap si sposti per essere l'ultimo elemento dell'intervallo e lascia [begin, end-1) come heap valido. Se si desidera rimuovere effettivamente l'elemento dal contenitore, è sufficiente cancellare l'ultimo elemento del contenitore (ad esempio con una chiamata a pop_back()) dopo aver chiamato pop_heap.

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