Skip to content

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:

Name Type Description Default
queue1 IQueue

A queue to merge.

 required
queue2 IQueue

Another queue to merge.

 required
compare Callable[[IQueue, IQueue], bool]

The binary predicate that governs how elements from the original queues are prioritized during merging.

 required

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
def merge(queue1: IQueue,
          queue2: IQueue,
          compare: Callable[[IQueue, IQueue], bool]) -> IQueue:
    """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.

    Args:
        queue1 (IQueue): A queue to merge.
        queue2 (IQueue): Another queue to merge.
        compare (Callable[[IQueue, IQueue], bool]): The binary predicate that governs how elements from the original queues are prioritized during merging.

    Returns:
        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.
    """
    n1 = len(queue1)
    n2 = len(queue2)
    if n1 == 0:
        return queue2
    if n2 == 0:
        return queue1

    # Create an empty queue of the same type as input queues
    # to store the merged sequence
    merged = type(queue1)[type(queue1.front())](n1 + n2, queue1.element_type)

    # Compare the elements at the front of two queues
    while not queue1.empty and not queue2.empty:
        queue = queue1 if compare(queue1.front(), queue2.front()) else queue2
        merged.enqueue(queue.front())
        queue.dequeue()

    # Handle unprocessed tail
    queue = queue1 if not queue1.empty else queue2
    while not queue.empty:
        merged.enqueue(queue.front())
        queue.dequeue()

    return merged