The weak-heap data structure: variants and applications

TY - GEN

T1 - The weak-heap data structure

T2 - 22nd International Workshop on Combinatorial Algorithms

AU - Edelkamp, Stefan

AU - Elmasry, Amr Ahmed Abd Elmoneim

AU - Katajainen, Jyrki

N1 - Conference code: 22

PY - 2012/10

Y1 - 2012/10

N2 - The weak heap is a priority queue that was introduced as a competitive structure for sorting. Its array-based form supports the operations find-min in O(1) worst-case time, and insert and delete-min in O(lgn) worst-case time using at most ⌈lgn⌉ element comparisons. Additionally, its pointer-based form supports delete and decrease in O(lgn) worst-case time using at most ⌈lgn⌉ element comparisons. In this paper we enhance this data structure as follows:We improve the array-based form to support insert in O(1) amortized time. The main idea is to temporarily store the inserted elements in a buffer, and, once the buffer is full, to move its elements to the heap using an efficient bulk-insertion procedure. As an application, we use this variant in the implementation of adaptive heapsort. Accordingly, we guarantee, for several measures of disorder, that the formula expressing the number of element comparisons performed by the algorithm is optimal up to the constant factor of the high-order term. Unlike other previous constant-factor-optimal adaptive sorting algorithms, adaptive heapsort relying on the developed priority queue is practically workable.We improve the pointer-based form to support insert and decrease in O(1) worst-case time per operation. The expense is that delete then requires at most 2⌈lgn⌉ element comparisons, but this is still better than the 3′lgnφ bound known for run-relaxed heaps. The main idea is to allow some nodes to violate the weak-heap ordering; we call the resulting priority queue a relaxed weak heap. We also develop a more efficient amortized variant that provides delete guaranteeing an amortized bound of 1.5⌈lgn⌉ element comparisons, which is better than the 2⌈logφn⌉ bound known for Fibonacci heaps, where φ is the golden ratio. As an application, we use this variant in the implementation of Dijkstras shortest-paths algorithm. Experimental results indicate that weak heaps are practically efficient; they are competitive with other priority-queue structures when considering the number of element comparisons performed, and lose by a small margin when considering the actual running time.

AB - The weak heap is a priority queue that was introduced as a competitive structure for sorting. Its array-based form supports the operations find-min in O(1) worst-case time, and insert and delete-min in O(lgn) worst-case time using at most ⌈lgn⌉ element comparisons. Additionally, its pointer-based form supports delete and decrease in O(lgn) worst-case time using at most ⌈lgn⌉ element comparisons. In this paper we enhance this data structure as follows:We improve the array-based form to support insert in O(1) amortized time. The main idea is to temporarily store the inserted elements in a buffer, and, once the buffer is full, to move its elements to the heap using an efficient bulk-insertion procedure. As an application, we use this variant in the implementation of adaptive heapsort. Accordingly, we guarantee, for several measures of disorder, that the formula expressing the number of element comparisons performed by the algorithm is optimal up to the constant factor of the high-order term. Unlike other previous constant-factor-optimal adaptive sorting algorithms, adaptive heapsort relying on the developed priority queue is practically workable.We improve the pointer-based form to support insert and decrease in O(1) worst-case time per operation. The expense is that delete then requires at most 2⌈lgn⌉ element comparisons, but this is still better than the 3′lgnφ bound known for run-relaxed heaps. The main idea is to allow some nodes to violate the weak-heap ordering; we call the resulting priority queue a relaxed weak heap. We also develop a more efficient amortized variant that provides delete guaranteeing an amortized bound of 1.5⌈lgn⌉ element comparisons, which is better than the 2⌈logφn⌉ bound known for Fibonacci heaps, where φ is the golden ratio. As an application, we use this variant in the implementation of Dijkstras shortest-paths algorithm. Experimental results indicate that weak heaps are practically efficient; they are competitive with other priority-queue structures when considering the number of element comparisons performed, and lose by a small margin when considering the actual running time.

U2 - 10.1016/j.jda.2012.04.010

DO - 10.1016/j.jda.2012.04.010

M3 - Conference article

SN - 0196-6774

VL - 16

SP - 187

EP - 205

JO - Journal of Algorithms

JF - Journal of Algorithms

Y2 - 20 June 2011 through 22 June 2011

ER -