Evaluation of Priority Queues in the Priority Flood Algorithm for Hydrological Modelling

The Priority-Flood algorithm, widely recognized for its computational efficiency in hydrological analysis, serves as the fundamental method for depression identification in DEMs, and the efficiency of the Priority-Flood algorithm hinges largely on the core component—priority queue implementation. Existing studies have focused predominantly on reducing the amount of data processed by queues, with few systematic reports on concrete queue implementations and corresponding performance analyses. In this study, six priority queues in the Priority-Flood algorithm are compared: a mini-heap (Heap), an AVL tree, a red-black tree (RBTree), a pairing heap (PairingHeap), a skip list (SkipList), and the Hash Heap (HHeap) structure proposed herein. Using multiscale DEM datasets as benchmarks, the results show that HHeap consistently outperforms the other structures across all scales, with particular advantages in ultralarge queues and in scenarios with high data duplication, rendering it the most effective choice for priority queues. The pairing heap approach typically ranks second in terms of overall runtime, whereas the AVL tree exhibits stable performance across scales; min-heap shows pronounced weaknesses under large-scale data conditions. This study provides empirical evidence to guide efficient priority queue selection and implementation and offers a viable technical pathway for ultralarge-scale terrain analysis. Future work will explore integrating HHeap with learning-based sorting and parallelization to further enhance processing performance and robustness in massive DEM contexts.