leetcode:Merge k Sorted Lists （建立堆）

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

思路：

    将每个链表的表头元素取出来，建立一个小顶堆，因为k个链表中都排好序了，因此每次取堆顶的元素就是k个链表中的最小值，可以将其合并到合并链表中，再将这个元素的指针指向的下一个元素也加入到堆中，再调整堆，取出堆顶，合并链表。。。。以此类推，直到堆为空时，链表合并完毕。

    因为想练习建堆的过程，所以我没有用STL里的make_heap等方法，而是自己写的建堆函数。若想看用STL的建堆方法的，可以参考网上答案。

    建堆的时间复杂度是k/2logk, 每次取出堆顶再加入元素的复杂度是logk,假设每条链表平均有n个元素，则一共有nk-k次。因此总的时间复杂度为O(nklogk)。

    还有一种思路是取出两条，用merge2Lists的方法合并为一条，再将这条和下一条用merge2Lists来合并为一条，以此类推。假设每条链表平均有n个元素，此种时间复杂度是O(2n+3n+…+kn), 为O(nk²),因此若用此法会超时。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return NULL;
        ListNode *newList=  new ListNode(0);
        ListNode *r=newList;
        int k=lists.size();
        vector<ListNode*> heap;
        for (int i = 0; i < k; ++i)
        {
            if(lists[i]) heap.push_back(lists[i]);
        }
        
            

        while(!heap.empty())
        {
            makeMinHeap(heap);

            ListNode*p=new ListNode(heap[0]->val);
            r->next=p;
            r=p;

            heap[0]=heap[0]->next;
            if(!heap[0]) 
            {
                swap(heap[0],heap[heap.size()-1]);
                heap.pop_back();//                        vector has no pop_front(),pay attention!!!!!!
            }
        }
        return newList->next;



        
    }

    void minHeapfixdown(vector<ListNode*>& a,int i,int n){
        int j,temp;
        ListNode* ptemp=a[i];
        temp=a[i]->val;
        j=2*i+1;

        while(j<n)
        {
            if((j+1<n)&&a[j+1]->val<a[j]->val)
            {
                j++;
            }
            if(a[j]->val>temp) break;

            a[i]=a[j];
            i=j;
            j=2*i+1;
        }

        a[i]=ptemp;
    }

    void makeMinHeap(vector<ListNode*>& a)
    {
        int n=a.size();
        for (int i = n/2-1; i >=0 ; --i)
        {
            minHeapfixdown(a,i,n);
        }
    }

};
           

注意：vector没有pop_front()方法，但是可以巧妙的 首尾交换，再pop_back()方法！！！！！神技