C ++ STL pop_heap не работает

Я пытаюсь использовать кучу, чтобы решить проблему «слияния K списков», которая объединяет k отсортированных связанных списков и возвращает его как один отсортированный список. Обычно я создаю минимальную кучу для хранения всего узла списка и использую предопределенную функцию LessThanLinkedList () для сравнения.
Но я обнаружил, что операции pop_heap () в строке 62 и 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 );
}

5

Решение

pop_heap не удаляет элементы из контейнера. Он не может, поскольку у него даже нет доступа к контейнеру, только к его элементам. Что он делает (при условии, конечно, что [begin, end) формирует допустимую непустую кучу) переставляет элементы так, что первый элемент кучи перемещается в качестве последнего элемента диапазона, и оставляет [begin, end-1) как действительная куча. Если вы действительно хотите удалить элемент из контейнера, вам просто нужно стереть последний элемент контейнера (например, с помощью вызова pop_back()) после звонка pop_heap,

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

Другие решения


По вопросам рекламы [email protected]