C++ STL pop_heap funktioniert nicht

Question

Ich versuche, Heap zu verwenden, um das Problem zu lösen "Merge K-Listen", die k sortierte verknüpfte Listen zusammenführen und es als eine sortierte Liste zurückgeben. Im Allgemeinen erstelle ich einen Min-Heap, um den gesamten Listenknoten zu speichern und benutze die vordefinierte Funktion LessThanLinkedList() für den Vergleich. Aber ich fand pop_heap() Operationen in Zeile 62 und 75 nie funktionieren. Es wird nicht den Anfang des Heaps entfernen, obwohl ich die vordefinierte Vergleichsfunktion als Parameter verwendet habe. Das Folgende ist mein Code. Ich benutze Visual Studio 2010 als IDE. Jeder kennt den Grund? Vielen dank für Deine Hilfe!

#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 entfernt keine Elemente aus dem Container. Es kann nicht, da es nicht einmal Zugriff auf den Container hat, nur seine Elemente. Was es tut (unter der Annahme natürlich, dass [begin, end) einen gültigen, nicht leeren Heap bildet), ordnen Sie die Elemente so an, dass das erste Element des Heaps das letzte Element des Bereichs ist und [begin, end-1) als gültiger Heap übrig lässt. Wenn Sie das Element tatsächlich aus dem Container entfernen möchten, müssen Sie nur das letzte Element des Containers löschen (z. B. mit einem Anruf an pop_back()), nachdem Sie pop_heap aufrufen.

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