s*w
发帖数: 729 | 1 不知道为啥，我的 heap 时灵时不灵的？请看下面的 code 和输出显示
#include
#include
#include
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int v):val(v),next(NULL) {}
};
bool minHeapPredicate(ListNode* lhs,ListNode* rhs) {
return lhs->val > rhs->val;
}
class Solution {
public:
ListNode *mergeKLists(vector lists) {
ListNode *retHead = NULL, *retTail = NULL;
// store values and nodes into heap
vector heads;
for(int i = 0;i < lists.size();++i)
if(lists[i])
heads.push_back(lists[i]);
make_heap(heads.begin(),heads.end(),minHeapPredicate);
// loop through all elements
while(!heads.empty()) {
// extract the min from heap
pop_heap(heads.begin(),heads.end());
ListNode* tmp = heads.back();
heads.pop_back();
// update the list pointer
ListNode *tmp2 = tmp->next;
if(tmp2) {
heads.push_back(tmp2);
cout << "before heapifying, the heap has: ";
for(int i=0;i
cout << heads[i]->val << " ";
cout << endl;
push_heap(heads.begin(),heads.end(),minHeapPredicate);
cout << "after heapifying, the heap has: ";
for(int i=0;i
cout << heads[i]->val << " ";
cout << endl;
}
// store tmp to ret
cout << "tmp=" << tmp->val << endl;
tmp->next = NULL;
if(retHead == NULL) {
retHead = tmp;
retTail = tmp;
} else {
retTail->next = tmp;
retTail = tmp;
}
}
return retHead;
}
};
void printList(ListNode *p) {
while(p) {
cout << p->val << "->";
p = p->next;
}
cout << endl;
}
int main() {
ListNode *p1 = new ListNode(-1);
ListNode *p2 = new ListNode(1);
p1->next = p2;
ListNode *p4 = new ListNode(-3);
ListNode *p5 = new ListNode(1);
ListNode *p6 = new ListNode(4);
p4->next = p5;
p5->next = p6;
ListNode *p7 = new ListNode(-2);
ListNode *p8 = new ListNode(-1);
ListNode *p9 = new ListNode(0);
ListNode *p10 = new ListNode(2);
p7->next = p8;
p8->next = p9;
p9->next = p10;
printList(p1);
printList(p4);
printList(p7);
vector vl;
vl.push_back(p1);
vl.push_back(p4);
vl.push_back(p7);
Solution s;
ListNode *ret = s.mergeKLists(vl);
printList(p1);
printList(p4);
printList(p7);
printList(ret);
}
outputs as follows:
-1->1->
-3->1->4->
-2->-1->0->2->
-3->1->4->
-1->1->
-2->-1->0->2->
now extracting min from heap: -3
before heapifying, the heap has: -2 -1 1
after heapifying, the heap has: -2 -1 1
-2->-1->0->2->
-1->1->
1->4->
now extracting min from heap: -2
before heapifying, the heap has: 1 -1 -1
after heapifying, the heap has: -1 -1 1
-1->0->2->
-1->1->
1->4->
now extracting min from heap: -1
before heapifying, the heap has: 1 -1 0
after heapifying, the heap has: 0 -1 1
0->2->
-1->1->
1->4->
now extracting min from heap: 0
before heapifying, the heap has: 1 -1 2
after heapifying, the heap has: 1 -1 2
1->4->
-1->1->
2->
now extracting min from heap: 1
before heapifying, the heap has: 2 -1 4
after heapifying, the heap has: 2 -1 4
2->
-1->1->
4->
now extracting min from heap: 2
4->
-1->1->
now extracting min from heap: 4
-1->1->
now extracting min from heap: -1
before heapifying, the heap has: 1
after heapifying, the heap has: 1
1->
now extracting min from heap: 1
-1->1->
-3->-2->-1->0->1->2->4->-1->1->
-2->-1->0->1->2->4->-1->1->
-3->-2->-1->0->1->2->4->-1->1-> | s*w
发帖数: 729 | 2 tnnd, 搞了几个小时终于发现问题了， pop_heap 也要加同一个 compare 的
【在 s*w 的大作中提到】
: 不知道为啥，我的 heap 时灵时不灵的？请看下面的 code 和输出显示
: #include
: #include
: #include
: using namespace std;
: struct ListNode {
: int val;
: ListNode *next;
: ListNode(int v):val(v),next(NULL) {}
: };
| p***y
发帖数: 637 | 3 堆应该单独实现，测试好后再用
【在 s*w 的大作中提到】
: 不知道为啥，我的 heap 时灵时不灵的？请看下面的 code 和输出显示
: #include
: #include
: #include
: using namespace std;
: struct ListNode {
: int val;
: ListNode *next;
: ListNode(int v):val(v),next(NULL) {}
: };
| s*w
发帖数: 729 | 4 面试编程的时候自己实现一个 heap ？ 光写这个 heap 至少要２０分钟吧？
【在 p***y 的大作中提到】
: 堆应该单独实现，测试好后再用
:
:
| l*****a
发帖数: 14598 | 5 所以用JAVA
直接用PriorityQueue
【在 s*w 的大作中提到】
: 面试编程的时候自己实现一个 heap ？ 光写这个 heap 至少要２０分钟吧？
| a**********t
发帖数: 14 | | s***k
发帖数: 50 | 7 C++也有priority_queue的好不好，又不是java独有的，
还有，本题不用heap也能解，分治。。。 |
|
