Priority Queue

Design a hardware module for the Priority Queue problem.

Given an input stream and a value k, keep track of the k smallest values seen so far.

After each input item, output one row containing the current k smallest values in ascending order. If fewer than k items have been seen, pad the remaining positions with 65535.

Hardware I/O Encoding

• stream is a one-dimensional stream of unsigned 16-bit integers
• k is a scalar unsigned 4-bit integer
• the output is a two-dimensional stream of unsigned 16-bit integers
• each outer output row corresponds to one processed input item
• each row has exactly k output values in ascending order

Examples

Example 1

• input stream = [5, 3, 8], k = 2
• output rows: [5, 65535], [3, 5], [3, 5]

Example 2

• input stream = [9, 1, 4], k = 3
• output rows: [9, 65535, 65535], [1, 9, 65535], [1, 4, 9]