mergeHeap Namespace Reference

Merge a variable number of sorted lists, into a single sorted output, using a heap queue. More...

Functions
def	addtoheap (h, i, it)
	Push a tuple(item,index) to a given heap. More...
def	mergek (*lists)
	Create a priority queue for merging a set of sorted lists. More...
def	main ()
	Main program for testing. More...

Detailed Description

Merge a variable number of sorted lists, into a single sorted output, using a heap queue.

Returns an iterator over the sorted values.

See also

https://docs.python.org/2/library/heapq.html

https://docs.python.org/2/library/functions.html#iter

https://wiki.python.org/moin/Generators

Function Documentation

addtoheap()

def mergeHeap.addtoheap	(		h,
			i,
			it
	)

Push a tuple(item,index) to a given heap.

Heaps are binary trees for which every parent node has a value less than or equal to any of its children. Generally implemented using an array or list.

Parameters

h	heap (a list).
it	an iterator for getting the next item from a list.
i	item index (the index of the list it came from).

Referenced by mergek().

main()

def mergeHeap.main

(

)

Main program for testing.

Merge four sorted lists.

References mergek().

mergek()

def mergeHeap.mergek

(

*

lists

)

Create a priority queue for merging a set of sorted lists.

It implements a generator, which yields the next element of the resultant sorted output.

References addtoheap().

Referenced by main().