ΣΕΜΦΕ forum

Κώδικας: Επιλογή όλων

# Lists is an array of sorted lists (arrays):
# [ [...], [...], … ]
def ListMerge(Lists):
	# The number of elements awaiting merge in each list.
	sizes = [len(L) for L in Lists]
	# Create a heap with a slot for each list.
	heap = range(len(Lists))
	for i in heap:
		# Heap elements are (key, value) pairs of (element, List index)
		heap[i] = (Lists[i][0], i)
	BuildMinHeap(heap)
	# Last tells the index of the list with the min element.
	last = heap[0][1]
	#############################################
	# O(n)
	#############################################
	merged = range(sum(sizes))
	for i in merged:
		# Next-in-order element at root of min heap.
		merged[i] = heap[0][0]
		while sizes[last] == 0:
		last = (last+1) % len(Lists)
		# Fill the hole in the heap and Min-Heapify.
		heap[0] = (Lists[last][-sizes[last]], last)
		sizes[last] -= 1
    #############################################
    # O(log k) where k = len(Lists)
    #############################################
    MinHeapify(heap)
  return merged