Merge k sorted linked lists and return it as one sorted list

Merge k sorted linked lists with total of N elements and return it as one sorted list...
Sol:- Well, this is very well known problem, and has many solutions.
Naive Approach:-
1. By Merging one list with other and resultant of previous with next lists
2. By Merging lists with pair there will be K/2 lists and now repeat the rest lists untill it became a single         list.

Optimal Approach:-
3. Keeping in mind the list are already sorted so we can use it's benefit. Use Heap which will work in following ways.
a) Take first elements of each lists and Min-Heapify it(least element).
b) Take out root element(least element) from the heap and put it into end of the resultant lists.
c) For step b if there is enough element in that list you have to put next element of the corresponding list to which root belongs.
d)if there is no next element of the corresponding list to which root belongs then replace First position element(Root) of the Heap with last position element and reduce Heap size by 1.
e)Follow the above operation upto N you are done.

//My running code in C++.....

#include<iostream>
#include<cstdlib>
using namespace std;
#define N 25
#define K 5     // so N/K=5 which is no. of possible lists in this case

//List structure
typedef struct List_Structure
{
int data;
struct List_Structure *next;
}List;

// List creation and data insertion  
void Insertion(List **Head,int data)
{
List *Node=(List*)malloc(sizeof(List));
if(!Node){cout<<"Memory Error";return;}
Node->data=data;
Node->next=NULL;
if(!*Head)
{
*Head=Node;
}
else
{
List *temp=*Head;
while(temp->next)
temp=temp->next;
temp->next=Node;
}
}
// Function for list Traversal.
void Traverse(List *Head)
{
if(!Head)return;
cout<<Head->data<<" ";
Traverse(Head->next);
}

//Heapify(min) to get least element out of K elements where K is the no. of lists.
void Heapify(List *a[],int p,int size)
{
int lchild=0,max=0,rchild=0;
List *temp;
lchild=2*p+1;
rchild=2*p+2;
if(rchild>size)
{
rchild=0;
if(lchild>size)
lchild=0;
}
if(rchild)
{
if(a[lchild]->data<a[rchild]->data)
{
if(a[lchild]->data<a[p]->data)
max=lchild;
}
else
{
if(a[rchild]->data<a[p]->data)
max=rchild;
}
}
else if(lchild&&rchild==0)
{
if(a[lchild]->data<a[p]->data)
max=lchild;
}

if(max)
{
temp=a[p];
a[p]=a[max];
a[max]=temp;
}
}

//Heap function goes here.....It's managing function for the problem
List *Heap(List *Head[],int size)
{ List *Root=NULL,*temp=NULL,*ptr=NULL;
List *arr[N/K];
for(int i=0;i<N/K;i++)
arr[i]=Head[i];

for(int i=(size-1)/2;i>=0;i--)
Heapify(arr,i,size);

int i=0;
while(i<N)
{
if(!Root)
{
temp=Root=arr[0];
}
else
{
temp->next=arr[0];
temp=arr[0];

}

if(arr[0]->next!=NULL)
arr[0]=arr[0]->next;
else
{
arr[0]=arr[size];
--size;
}
Heapify(arr,0,size);
i++;
}

return Root;
}

int main(void)
{ List *Head[N/K]={NULL};
for(int i=0;i<N/K;i++)
Head[i]=NULL;
int k=5,j,value;
for(int i=0;i<N/K;i++)
{
for(j=0;j<N/K;j++)
{
cin>>value;
Insertion(&Head[i],value);
}
}
//you lists are as  
for(int i=0;i<N/K;i++)
{
Traverse(Head[i]);
cout<<endl;
}
//Merged list...
List *Start=Heap(Head,N/K-1);
Traverse(Start);
return 0;

}