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.

Depression detection in digital terrain analysis is crucial for surface process modelling. High-resolution satellite imagery has led to an increasing demand for processing ultra-large-scale digital elevation models (DEMs) with billions of grid cells, which has exposed the computational inefficiencies of traditional priority-flood algorithms based on priority queues. While existing research has primarily focused on reducing the data volume in priority-flood’s priority queues, few studies have focused on optimizing the sorting mechanism within these queues. In this paper, we propose a hybrid Hash Red Black Tree (HRBTree) data structure, integrating the efficient insertion capability of hash tables with the ordered key-value maintenance of the RBTree, thereby reconstructing the priority queue architecture of the priority-flood algorithm. Using multi-scale DEM datasets ranging from millions to 1.6 billion grid cells, we systematically evaluated the computational efficiency of the enhanced priority-flood algorithm across varying data scales. The experimental results demonstrate that the proposed HRBTree structure exhibits superior adaptability, particularly in ultra-large-scale datasets (> 1 billion nodes), achieving a maximum speedup of 49% compared with traditional priority queue structures, which validates the effectiveness of heterogeneous data structure fusion. After modifying three classic priority-flood variants (Wang & Liu, Barnes, and Zhou), the HRBTree demonstrates strong generalizability. Specifically, on billion-scale datasets, the HRBTree-optimized Wang & Liu algorithm achieves a 45.6% speedup (average 35.1%), the Barnes algorithm improves by up to 37.6%, and the Zhou algorithm reaches a 28.2% speedup, confirming the structure’s compatibility with diverse algorithmic frameworks. This study provides critical insights for the engineering application of terrain analysis algorithms and lays the foundation for next-generation high-performance, scalable computing paradigms in terrain analysis systems.

Digital elevation models (DEMs) depression processing is a critical preprocessing step in hydrological modelling. In this study, the evolution of depression processing algorithms across DEMs resolutions was systematically examined, tracing the paradigm shift from traditional data modification methods for coarse-resolution DEMs to modern data preservation strategies for high-precision DEMs that maintain original terrain fidelity. Quantitative analysis of the acceleration ratio indicator revealed that algorithmic engineering efficiency can differ by as much as 189% under the same time complexity, which highlights the disparity between theoretical complexity and actual performance. Current research faces three principal challenges in processing ultra-large-scale data: the influence of geographical characteristics on data structures, performance bottlenecks in traditional algorithms, and the efficiency limitations of serial computation. Future research should concentrate on three key areas: (1) developing novel data structures based on enhanced binary tree encoding to mitigate the effects of geographical characteristics; (2) integrating artificial intelligence technologies to address the limitations of traditional algorithms; and (3) constructing parallel computing frameworks. These advances are expected to significantly increase the accuracy of surface water flow simulations and facilitate the comprehensive application of DEMs in hydrology.