Efficient Heap Implementation with a Fixed-Size Linear Systolic Array
Jyh-Jong Tsay · Purdue e-Pubs (Purdue University System) · 1989
The heap is a data strudure used in many applications and provides a funfamental technique to solve many problems efficiently.In this paper I we show that a sequence of n INSERT and EXTRACT..MIN heap operations can be performed in time O(nlogmjlogp) with space Oem) on a random access machine to ,vhich a linear systolic array of p processors is attached, provided that, at any time instance, there are at most m (m ~n) data elements in the heap.The algorithm can be easily to modified to handle DELETE operation with time O(n log nj logp) and space O(n).1