Ordered Dags: HypercubeSort

Abstract

We generalise the insertion into a binary heap to any directed acyclic graph (DAG) with one source vertex. This lets us formulate a general method for converting any such DAG into a data structure with priority queue interface. We apply our method to a hypercube DAG to obtain a sorting algorithm of complexity $\mathcal{O}(n{\log }^2(n))$. As another curious application, we derive a relationship between length of longest path and maximum degree of a vertex in a DAG.