C++ STL pop_heap nie działa

Question

Próbuję użyć sterty, aby rozwiązać problem "scal list K", który łączy k sortowane połączone listy i zwraca je jako jedną posortowaną listę. Generalnie tworzę stertę min do przechowywania całego węzła listy i używam predefiniowanej funkcji LessThanLinkedList() dla porównania. Ale znalazłem operacji pop_heap() w linii 62 i 75 nigdy nie działają. Nie usunie wierzchołka sterty, chociaż użyłem predefiniowanej funkcji porównania jako parametru. Oto mój kod. Używam Visual Studio 2010 jako IDE. Ktoś zna przyczynę? Bardzo dziękuję za Twoją pomoc!

#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

nie usuwa elementów z pojemnika. Nie może, ponieważ nie ma nawet dostępu do kontenera, tylko jego elementy. To, co robi (zakładając oczywiście, że [begin, end) tworzy prawidłową, niepustą stertę) zmienia elementy tak, aby pierwszy element sterty przesuwał się jako ostatni element zakresu i pozostawia [begin, end-1) jako prawidłową stertę. Jeśli chcesz faktycznie usunąć element z pojemnika, musisz po prostu usunąć ostatni element kontenera (np. Z numerem pop_back()) po wywołaniu pop_heap.

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