C++ STL pop_heap이 작동하지 않습니다.

Question

k 개의 정렬 된 연결된 목록을 병합하고 하나의 정렬 된 목록으로 반환하는 "병합 K 목록"문제를 해결하기 위해 힙을 사용하려고합니다. 일반적으로 모든 목록 노드를 저장하고 비교를 위해 미리 정의 된 함수 LessThanLinkedList()를 사용하기 위해 최소 힙을 만듭니다. 하지만 62 행의 pop_heap() 연산과 75는 절대로 작동하지 않습니다. 미리 정의 된 비교 함수를 매개 변수로 사용했지만 힙의 맨 위는 제거되지 않습니다. 다음은 내 코드입니다. Visual Studio 2010을 IDE로 사용하고 있습니다. 그 이유는 누구나 아는가? 도와 주셔서 정말로 고맙습니다!

#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 컨테이너에서 요소를 제거하지 않습니다. 컨테이너에 액세스 할 수 없기 때문에 요소 만 포함 할 수 없습니다. 그것은 무엇입니까 (물론 [begin, end)이 유효하고 비어 있지 않은 힙을 형성한다고 가정하면) 힙의 첫 번째 요소가 범위의 마지막 요소가되도록 요소를 재정렬하고 [begin, end-1)을 유효한 힙으로 남겨 둡니다. 컨테이너에서 요소를 실제로 제거하려면 pop_heap에 전화 한 후 컨테이너의 마지막 요소 (예 : pop_back()으로 호출)를 지워야합니다.

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