Algorithms on Queue ADT
pydsa.queue.algo
is a subpackage that contains ADT-implementation-agnostic
algorithms on the Queue ADT.
All algorithms are independent of implementation of the Queue ADT.
merge(queue1, queue2, compare)
¶
Stable-merges two queues.
Elements are compared using the binary predicate compare
to
determine the order in which they appear in the merged queue. Relative order
of elements in the original queues are preserved. A new queue of the same
type as the two queues to merge is created and returned if both queues to
merge are not empty.
Parameters:
Returns:
Name | Type | Description |
---|---|---|
IQueue |
IQueue
|
The merged queue. |
Notes
The complexity of the merge algorithm is O(n1 + n2)
in both time and space, where n1
and n2
are the sizes of the two queues to merge.
Source code in pydsa/queue/algo/merge.py
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
|