Author: admin

/*
head: array of head pointers of the separated lists
tail: array of tail pointers of the separated lists
cur_node: current node being processed
i: data value of the node
*/
void add_node(struct node *head[], struct node *tail[], 
		struct node *cur_node, int i)
{
	cur_node->next = head[i];
	head[i] = cur_node;
	if (!tail[i])
		tail[i] = cur_node;

}


/*first_node: first node in list to be sorted 
num_distinct_values: number of distinct values in the nodes
Return value: head of the sorted list
*/
struct node * sort_list(struct node *first_node, int num_distinct_values)
{
	struct node **head, **tail; 
	struct node *result = NULL, *cur_node, *next_node, *last_element;
	int i;

	if (!first_node)
		return NULL;

	head = (struct node**) calloc(num_distinct_values, sizeof(struct node*));
	tail = (struct node**) calloc(num_distinct_values, sizeof(struct node*)); 

	for (i = 0; i < num_distinct_values; ++i) {
		head[i] = NULL;
		tail[i] = NULL;
	}

	/*Partition the list into separate lists, (0-list, 1-list, 2-list)
	based on the data in the node*/
	cur_node = first_node;
	while (cur_node) {
		next_node = cur_node->next;
		add_node(head, tail, cur_node, cur_node->data);
		cur_node = next_node;
	}

	/*Connect the tail of first linked list with head of second linked list
	and so on*/
	result = head[0];
	last_element = tail[0];
	for (i = 1; i < num_distinct_values; ++i) {
		if (!result)
			result = head[i];

		/*Link last element of previous list with head of current list*/
		if (last_element)
			last_element->next = head[i];

		/*update the last element to the tail of current list*/
		if (tail[i])
			last_element = tail[i];
	}

	free(head);
	free(tail);

	return result;
}

/*
head: array of heads of the separated lists
tail: array of tails of the separated lists
curNode: current node being processed
i: data value of the node
*/
public static void addNode(LinkedListNode[] head, LinkedListNode[] tail, 
			LinkedListNode curNode, int i) {
	curNode.next = head[i];
	head[i] = curNode;
	if (tail[i] == null)
		tail[i] = curNode;

}

/*firstNode: first node in the list to be sorted 
numDistinctValues: number of distinct values 
Return value: head of the sorted list
*/
public static LinkedListNode sortList(LinkedListNode firstNode, 
				int numDistinctValues) {
	LinkedListNode[] head = new LinkedListNode[numDistinctValues]; 
	LinkedListNode[] tail = new LinkedListNode[numDistinctValues];
	LinkedListNode result = null;

	if (firstNode == null)
		return null;

	int i;
	for (i = 0; i < numDistinctValues; ++i) {
		head[i] = null;
		tail[i] = null;
	}

	/*Partition the list into separate lists (0-list, 1-list and 2-list)
	based on the data in the node*/
	LinkedListNode curNode = firstNode;
	while (curNode != null) {
		LinkedListNode nextNode = curNode.next;
		addNode(head, tail, curNode, curNode.data);
		curNode = nextNode;
	}

	/*Connect the tail of first linked list with head of second linked list
	and so on*/
	result = head[0];
	LinkedListNode lastElement = tail[0];
	for (i = 1; i < numDistinctValues; ++i) {
		if (result == null)
			result = head[i];

		/*Link last element of previous list with head of current list*/
		if (lastElement != null)
			lastElement.next = head[i];

		/*update the last element to the tail of current list*/
		if (tail[i] != null)
			lastElement = tail[i];
	}

	return result;
}

#head: list having head nodes of all the separated linked lists
#tail: list having tail nodes of all the separated linked lists
#cur_node: current node being processed
#i: data value of the node
@staticmethod
def add_node(head, tail, cur_node, i) :
	cur_node.next = head[i]
	head[i] = cur_node
	if (tail[i] == None):
		tail[i] = cur_node


#first_node:  first node in the linked list to be sorted
#num_distinct_values: number of distinct values 
#Return value: head of the sorted linked list
@staticmethod
def sort_linked_list(first_node, num_distinct_values) :
	head = [None] * num_distinct_values 
	tail = [None] * num_distinct_values
	result = None

	if (not first_node):
		return None

	#Partition the input linked list into separate linked lists 
	#(0-list, 1-list and 2-list) based on the data in the node
	cur_node = first_node
	while (cur_node) :
		next_node = cur_node.next
		LinkedListNode.add_node(head, tail, cur_node, cur_node.data)
		cur_node = next_node
	
	#Connect the tail of first linked list with head of second linked list
	#and so on
	result = head[0]
	last_element = tail[0]
	for  i in range(1, num_distinct_values):
		if (not result):
			result = head[i]

		#Link last element of previous linked list with head of 
		#current linked list
		if (last_element):
			last_element.next = head[i]

		#update the last element to the tail of current linked list
		if (tail[i] != None):
			last_element = tail[i]
	

	return result

/*
arrays: the arrays to be merged. arrays[0] has the first array, arrays[1] has 
		the second array and so on
n: number of elements in each array
k: number of arrays
result: the merged results are passed back in this array
*/
void merge_k_sorted_arrays(int arrays[][MAX_NUM_ELEMENTS], int n, int k, 
			int *result)
{
	struct node *heap = (struct node*) calloc(k, sizeof(struct node));
	int *arr_pos = (int*) calloc(k, sizeof(int));
	int i, pos, res_index, array_no;

	/*Store the first element in each array into the heap*/
	for (i = 0; i < k; ++i) {
		heap[i].value = arrays[i][0];
		heap[i].array_no = i;
		arr_pos[i] = 1;
	}

	/*Construct the initial heap using the heapify procedure*/
	for (i = k - 1; i >= 0; --i)
		heapify(heap, i, k);
	
	/*
	Process the remaining elements in the arrays. When all elements in the 
	arrays have been processed, MAX_INT will be present at root of heap
	*/
	res_index = 0;
	while (heap[0].value != MAX_INT) {
		/*
		root of the heap will have the lowest value. So store
		it into the result
		*/
		result[res_index++] = heap[0].value;

		array_no = heap[0].array_no;
		pos = arr_pos[array_no];

		/*
		If the root belongs to array x, then replace the root with
		the next element in array x
		*/
		if (pos >= n) {
			/*If we have exhausted all elements in the array, 
			then insert MAX_INT into the heap*/
			heap[0].value = MAX_INT;
			heap[0].array_no = array_no;
		} else {
			heap[0].value = arrays[array_no][pos];
			heap[0].array_no = array_no;
		}

		/*Re-adjust the heap after replacing the root*/
		heapify(heap, 0, k);

		arr_pos[array_no]++;
	}

	free(arr_pos);
	free(heap);
}


/* Helper function to perform heapify
heap: min heap.  Maximum number of elements in heap is k
pos: position of the heap that may need to be fixed
heap_size: current number of nodes in the heap
*/
void heapify(int heap[], int pos, int heap_size)
{
	int left = 2 * pos;
	int right = (2 * pos) + 1;
	int ix_of_smallest = pos;

	/*Find which of the three are the smallest: heap[pos] OR left child
	OR right child*/
	if (left < heap_size && heap[pos] > heap[left])
		ix_of_smallest = left;
	if (right < heap_size && heap[ix_of_smallest] > heap[right])
		ix_of_smallest = right;

	if (ix_of_smallest != pos) {
		/*
		If pos doesn't contain the smallest value,
		then swap the smallest value into pos 
		*/
		int temp = heap[pos];
		heap[pos] = heap[ix_of_smallest];
		heap[ix_of_smallest] = temp;

		/*Recursively re-adjust the heap*/
		heapify(heap, ix_of_smallest, heap_size);
	}
}

/*
arrays: the arrays to be merged. arrays[0] has the first array, arrays[1] has
		the second array and so on
Return value: the merged results are passed back in this array
*/
public static int[] mergeKSortedArrays(int[][] arrays) {
	int k = arrays.length;	/*number of arrays*/
	int n = arrays[0].length; /*number of elements in each array*/
	Node[] heap = new Node[k];
	int[] arrPos = new int[k];
	int[] result = new int[k * n];

	/*Store the first element in each array into the heap*/
	int i;
	for (i = 0; i < k; ++i) {
		heap[i] = new Node();
		heap[i].value = arrays[i][0];
		heap[i].arrayNo = i;
		arrPos[i] = 1;
	}

	/*Construct the initial heap using the heapify procedure*/
	for (i = k - 1; i >= 0; --i)
		heapify(heap, i, k);

	
	/*
	Process the remaining elements in the arrays. When all elements in the
	arrays have been processed, MAX_INT will be present at root of heap
	*/
	int resIndex = 0;
	while (heap[0].value != MAX_INT) {
		/*
		root of the heap will have the lowest value. So store
		it into the result
		*/
		result[resIndex++] = heap[0].value;

		int arrayNo = heap[0].arrayNo;
		int pos = arrPos[arrayNo];

		/*
		If the root belongs to array x, then replace the root with
		the next element in array x
		*/
		if (pos >= n) {
			/*If we have exhausted all elements in the array, 
			then insert MAX_INT into the heap*/
			heap[0].value = MAX_INT;
			heap[0].arrayNo = arrayNo;
		} else {
			heap[0].value = arrays[arrayNo][pos];
			heap[0].arrayNo = arrayNo;
		}

		/*Re-adjust the heap after replacing the root*/
		heapify(heap, 0, k);

		arrPos[arrayNo]++;
	}

	return result;
}

/* Helper function to perform heapify
heap: min heap.  Maximum number of elements in heap is k
pos: position of the heap that may need to be fixed
heapSize: current number of nodes in the heap
*/
public static void heapify(int[] heap, int pos, int heapSize) {
	int left = 2 * pos;
	int right = (2 * pos) + 1;
	int ixOfSmallest = pos;

	/*Find which of the three are the smallest - heap[pos] OR left child
	OR right child*/
	if (left < heapSize && heap[pos] > heap[left])
		ixOfSmallest = left;
	if (right < heapSize && heap[ixOfSmallest] > heap[right])
		ixOfSmallest = right;


	if (ixOfSmallest != pos) {
		/*
		If pos doesn't contain the smallest value,
		then swap the smallest value into pos 
		*/
		int temp = heap[pos];
		heap[pos] = heap[ixOfSmallest];
		heap[ixOfSmallest] = temp;

		/*Recursively re-adjust the heap*/
		heapify(heap, ixOfSmallest, heapSize);
	}
}

#lists:  the lists to be merged. lists[0] has the first list, lists[1] has 
#		the second list and so on
#Return value:  the merged results are passed back in this list
def merge_k_sorted_lists(lists) :
	k = len(lists)	#number of lists
	n = len(lists[0]) #number of elements in each list
	heap = []
	arr_pos = []

	#Store the first element in each list into the heap
	for  i in range(0, k):
		new_node = Node()
		new_node.value = lists[i][0]
		new_node.list_no = i
		heap.append(new_node)
		arr_pos.append(1)
	
	#Construct the initial heap using the heapify procedure
	for  i in range(k - 1, -1,-1):
		heapify(heap, i, k)

	#Process the remaining elements in the lists. When all elements in  
	#the lists have been processed, MAX_INT will be present at root of heap
	result = [] 
	while (heap[0].value != MAX_INT) :
		#root of the heap will have the lowest value. So store
		#it into the result
		result.append(heap[0].value)

		list_no = heap[0].list_no
		pos = arr_pos[list_no]

		#If the root belongs to list x, then replace the root with
		#the next element in list x
		if (pos >= n) :
			#If we have exhausted all elements in the list, 
			#then insert MAX_INT into the heap
			heap[0].value = MAX_INT
			heap[0].list_no = list_no
		else :
			heap[0].value = lists[list_no][pos]
			heap[0].list_no = list_no
		

		#Re-adjust the heap after replacing the root
		heapify(heap, 0, k)

		arr_pos[list_no] += 1
	
	return result

#Helper function to perform heapify
#heap: min heap.  Maximum number of elements in heap is k
#pos: position of the heap that may need to be fixed
#heap_size: current number of nodes in the heap
def heapify(heap, pos, heap_size) :
	left = 2 * pos
	right = (2 * pos) + 1
	ix_of_smallest = pos

	#Find which of the three are the smallest - value at pos OR left child
	#OR right child
	if (left < heap_size and heap[pos] > heap[left]):
		ix_of_smallest = left
	if (right < heap_size and heap[ix_of_smallest] > heap[right]):
		ix_of_smallest = right
 
	if (ix_of_smallest != pos) :
		#If pos doesn't contain the smallest value,
		#then swap the smallest value into pos 
		heap[pos], heap[ix_of_smallest] = heap[ix_of_smallest], heap[pos]

		#Recursively readjust the heap
		heapify(heap, ix_of_smallest, heap_size)

/*
a: array of size m+n which has m elements at beginning and n spaces at end
b: array of size n with n elements
m: number of elements in array a
n: number of elements in array b
*/
void merge_arrays(int a[], int b[], int m, int n)
{
	int i, j, fill_pos;

	i = m - 1;
	j = n - 1;
	fill_pos = m + n - 1; /*Start filling from the rear of the array*/

	while (i >= 0 && j >= 0) {
		if (a[i] > b[j]) {
			a[fill_pos--] = a[i--];
		} else {
			a[fill_pos--] = b[j--];
		}
	}

	/*Fill up the remaining elements of array a if any*/
	while (i >= 0)
		a[fill_pos--] = a[i--];

	/*Fill up the remaining elements of array b if any*/
	while (j >= 0)
		a[fill_pos--] = b[j--];

} 

/*
a: array of size m+n which has m elements at beginning and n spaces at end
b: array of size n with n elements
m: number of elements in array a
n: number of elements in array b
*/
public static void mergeArrays(int[] a, int[] b, int m, int n) 	{
	int i = m - 1;
	int j = n - 1;
	int fillPos = m + n - 1; /*Start filling from the rear of the array*/

	while (i >= 0 && j >= 0) {
		if (a[i] > b[j]) {
			a[fillPos--] = a[i--];
		} else {
			a[fillPos--] = b[j--];
		}
	}

	/*Fill up the remaining elements of array a if any*/
	while (i >= 0)
		a[fillPos--] = a[i--];

	/*Fill up the remaining elements of array b if any*/
	while (j >= 0)
		a[fillPos--] = b[j--];
}  

#a: list of size m+n which has m elements at beginning 
#b: list of size n with n elements
#m: number of elements in list a
#n: number of elements in list b
def merge_lists(a, b, m, n) :
	i = m - 1
	j = n - 1
	fill_pos = m + n - 1 #Start filling from the rear of list a

	while (i >= 0 and j >= 0) :
		if (a[i] > b[j]) :
			a[fill_pos] = a[i]
			fill_pos -= 1
			i -= 1
		else :
			a[fill_pos] = b[j]
			fill_pos -= 1
			j -= 1
		
	#Fill up the remaining elements of list a if any
	while (i >= 0):
		a[fill_pos] = a[i]
		fill_pos -= 1
		i -= 1

	#Fill up the remaining elements of list b if any
	while (j >= 0):
		a[fill_pos] = b[j]
		fill_pos -= 1
		j -= 1