An efficient implementation of priority queues using fixed-sized systolic coprocessors (Q685514)

We consider the problem of maintaining a set which supports the INSERT, DELETE and EXTRACT-MIN operations on a random access machine to which a linear systolic array of \(p\) processing elements is attached. We give an implementation that performs a sequence of \(n\) INSERT and EXTRACT-MIN operations on-line in time \(O(n \log m/\log p)\) and space \(O(m)\), provided that, at any time instance, there are at most \(m(m\leq n)\) data elements existing. The implementation can be easily modified to handle DELETE operations. This gives \(O(n \log m/\log p)\) time solutions to the problems that can be reduced to the problem of performing a sequence of \(O(n)\) INSERT, DELETE and EXTRACT-MIN operations.