#include<iostream>

 #include<vector>

 #include<cmath>

 #include<map>

 using namespace std;

 typedef struct ListNode {

     int val;

     ListNode *next;

     ListNode(int x) : val(x), next(NULL) {}

 }ListNode;

 inline int left(int x)

 {

     return  * x + ;

 }

 inline int right(int x)

 {

     return  * x + ;

 }

 void swap(int &x, int &y)

 {

     int c = x;

     x = y;

     y = c;

 }

 int QQ;

 //    以i节点为根节点进行，堆的维护；假设i节点下面的节点都是堆了。

 void MaxHeap(int a[], int i, int k,int ok)

 {

     int l = left(i);

     int r = right(i);

     int smallest = i;

     if (l < k  && a[l] < a[i])

     {

         smallest = l;

     }

     if (r<k&&a[r] < a[smallest])

     {

         smallest = r;

     }

     if (i == smallest)

     {

         return;

     }

     else

     {

         swap(a[smallest], a[i]);

         return MaxHeap(a, smallest, k, );

     }

 }

 ListNode *mergeKLists(vector<ListNode *> &lists) {

     int k = lists.size();

     int *flag = new int[k];    //    标志位

     int *a = new int[k];

     ListNode *head;

     map<int, int> cmap;

     int n = k;

     ListNode **p = (ListNode**)malloc(sizeof(ListNode*)*k);

     for (int i = ; i < k; i++)

     {

         p[i] = lists[i];

         a[i] = p[i]->val;

         cmap.insert(make_pair(a[i], i));

         if (p[i] == NULL)

         {

             flag[i] = ;

         }

         else

         {

             flag[i] = ;

         }

     }

     MaxHeap(a, , k,);

     int t = cmap[a[]];

     head = lists[t];

     ListNode *m = lists[t];

     p[t] = p[t]->next;

     while (n != )

     {

         n = k;

         for (int i = ; i < k; i++)

         {

             if (p[i] == NULL)

             {

                 flag[i] = ;

                 n--;

             }

         }

         if (flag[t] == )

         {

             a[] = a[n];

             MaxHeap(a, , n, );

             t = cmap[a[]];

             m->next = p[t];

             m = m->next;

             p[t] = p[t]->next;

         }

         else

         {

             a[] = p[t]->val;

             cmap.insert(make_pair(a[], t));

             MaxHeap(a, , n, );

             t = cmap[a[]];

             m->next = p[t];

             m = m->next;

             p[t] = p[t]->next;

         }

     }

     ListNode * last;

     for (int i = ; i < k; i++)

     {

         if (p[i] != NULL)

         {

             last = p[i];

         }

     }

     m->next = last;

     return head;

 }

 int main()

 {

     /*int a[] = {3,1,4,2,3,5,6};

     MaxHeap(a, 0, 7, 0);

     cout << "标识"<<QQ << endl;

     for (int i = 0; i < 7; i++)

     {

         cout << a[i] << endl;

     }*/

     int a[] = {,,,, , };

     int b[] = {,, , , ,,};

     int c[] = { , , ,  };

     vector<ListNode*> p;

     ListNode *temp = (ListNode *)malloc(sizeof(ListNode));

     ListNode *head = temp;

     for (int i = ; i < ; i++)

     {

         temp->val = a[i];

         if (i != )

             temp->next = (ListNode *)malloc(sizeof(ListNode));

         else

             temp->next = NULL;

         temp = temp->next;

     }

     ListNode *temp1 = (ListNode *)malloc(sizeof(ListNode));

     ListNode *head1 = temp1;

     for (int i = ; i < ; i++)

     {

         temp1->val = b[i];

         if (i != )

             temp1->next = (ListNode *)malloc(sizeof(ListNode));

         else

             temp1->next = NULL;

         temp1 = temp1->next;

     }

     ListNode *temp2 = (ListNode *)malloc(sizeof(ListNode));

     ListNode *head2 = temp2;

     for (int i = ; i < ; i++)

     {

         temp2->val = c[i];

         if (i != )

             temp2->next = (ListNode *)malloc(sizeof(ListNode));

         else

             temp2->next = NULL;

         temp2 = temp2->next;

     }

     p.push_back(head);

     p.push_back(head1);

     p.push_back(head2);

     for (ListNode * temp = head; temp != NULL; temp = temp->next)

     {

         cout << temp->val << endl;

     }

     for (ListNode * temp = mergeKLists(p); temp != NULL; temp = temp->next)

     {

     cout << temp->val << endl;

     }

 }