We provide the following tutorials to show how pydatastructs APIs can help in solving complicated data structures and algorithms problems easily. For now the problems are abstract. However, we plan to add some more examples showing usage of pydatastructs on real world data sets such as Stanford Large Network Dataset Collection and Urban Dictionary Words And Definitions. If you are interested in playing around with the above datasets using our API, then please feel free to reach out to us on our community channels.

Max-Min Stream

In this problem, we will be dealing with a stream of integer numbers. We have to display the k-th largest and k-th smallest number for all the prefixes of the input stream. In simple words, after reading each number, we have to display the k-th largest and k-th smallest number up until that number in the stream. If the size of the stream is smaller than k then we will display the minimum for k-th smallest and maximum for k-th largest numbers respectively.

Input Format

The first line of input will contain the value, k. After that, each line of input will contain an integer representing the new number of the stream. The stopping point of the stream will be denoted by 0. Note that stopping point i.e., 0 will also be considered a part of the input stream.

Output Format

Each line of the output should contain two space separated numbers, the first one representing the k-th largest/maximum number and the second one representing the k-th smallest/minimum number.

>>> from pydatastructs import BinaryHeap, Queue
>>> def modify_heaps(min_heap, max_heap, curr_num, k):
...     min_heap.insert(curr_num)
...     max_heap.insert(curr_num)
...     if min_heap.heap._num > k:
...         min_heap.extract()
...     if max_heap.heap._num > k:
...         max_heap.extract()
...     large, small = (max_heap.heap[0].key, min_heap.heap[0].key)
...     return large, small
>>> min_heap = BinaryHeap(heap_property='min')
>>> max_heap = BinaryHeap(heap_property='max')
>>> k = 2
>>> curr_nums = Queue(items=[4, 5, 8, 0]) # input stream as a list
>>> curr_num = curr_nums.popleft()
>>> large_small = []
>>> while curr_num != 0:
...     large, small = modify_heaps(min_heap, max_heap, curr_num, k)
...     large_small.append((large, small))
...     curr_num = curr_nums.popleft()
>>> large, small = modify_heaps(min_heap, max_heap, curr_num, k)
>>> large_small.append((large, small))
>>> print(large_small)
[(4, 4), (5, 4), (5, 5), (4, 5)]

Minimise Network Delay

In this problem there will be a network containing N nodes, labelled as 1 … N, and E edges. Any two nodes may be connected by an undirected edge E(u, v) and introduces a delay of time t(u, v) in transfer of information between the nodes u and v.

We will be given K queries where each query contains the source node and the destination node and we will be required to determine the minimum time it will take for a piece of information to start from the source node and reach at the destination node.

We will assume that the size of information and the processing time at any node doesn’t affect the travel time.

Input Format

The first line will contain a single positive integer N.

The second line will contain a single positive integer E.

Then E lines will follow, each line containing three space separated integers. The first two denoting node labels connected by an undirected edge which introduces a time delay denoted by the third integer.

After that the next line will contain a positive integer K.

Then K lines will follow each containing two space separated node labels, the first denoting the source node and the second one denoting the destination node for that query.

Output Format

K lines, each containing the minimum time required for the k-th query.

>>> from pydatastructs import Graph, AdjacencyListGraphNode
>>> from pydatastructs.graphs.algorithms import shortest_paths
>>> N = 4
>>> E = 3
>>> nodes = []
>>> for n in range(N):
...     nodes.append(AdjacencyListGraphNode(str(n + 1)))
>>> u_v_t = [(1, 2, 1), (2, 3, 1), (3, 4, 1)] # edges and their time delay
>>> graph = Graph(*nodes)
>>> for e in range(E):
...     u, v, t = u_v_t[e]
...     graph.add_edge(str(u), str(v), t)
...     graph.add_edge(str(v), str(u), t)
>>> K = 3
>>> u_v = [(1, 4), (3, 2), (4, 3)] # queries
>>> delays = []
>>> for k in range(K):
...     u, v = u_v[k]
...     delay = shortest_paths(graph, 'dijkstra', str(u))[0]
...     delays.append(delay[str(v)])
>>> print(delays)
[3, 1, 1]