The Logarithmic Funnel Heap: An Efficient Indexed Priority Queue

A large group of data-processing applications often require a comprehensive set of efficient operations for priority value management. Indexed priority queues are particularly useful in this context. In this work, we report the design and analysis of an efficient indexed priority queue with a comprehensive set of operations. In particular, $\mathtt{insert}$, $\mathtt{delete}$ and $\mathtt{decrease}$ all run in expected $O(\log^{*}{n})$ time, while $\mathtt{increase}$ is conjectured to run in expected $O(\log\log{n})$ time. The space complexity as well as the time complexity for the construction of the empty heap system are $O(n)$. For massive computational problems, such as (chemical) simulations or the specific analyses of very large graphs, the heap data structure is expected to exhibit utility.