From f54895b14e65e4fd27133472d5945ab21162693e Mon Sep 17 00:00:00 2001 From: Pavel Charvat Date: Wed, 22 Aug 2018 06:24:51 +0200 Subject: [PATCH] Heaps: Added Fibonacci Heaps and multi-pass version of Rank-Pair Heaps. Also some bugfixes and comments. --- ucw/heap-bench.c | 139 +++++++++--- ucw/heap-gen.h | 534 ++++++++++++++++++++++++++++++++++++++--------- 2 files changed, 537 insertions(+), 136 deletions(-) diff --git a/ucw/heap-bench.c b/ucw/heap-bench.c index 0b2264ca..5594f676 100644 --- a/ucw/heap-bench.c +++ b/ucw/heap-bench.c @@ -20,9 +20,13 @@ static int o_seed; static int o_heap_pairing_noparent; static int o_heap_pairing; -static int o_heap_rank_pairing_noparent; -static int o_heap_rank_pairing_type1; -static int o_heap_rank_pairing_type2; +static int o_heap_rank_pairing_noparent_1pass; +static int o_heap_rank_pairing_noparent_mpass; +static int o_heap_rank_pairing_type1_1pass; +static int o_heap_rank_pairing_type1_mpass; +static int o_heap_rank_pairing_type2_1pass; +static int o_heap_rank_pairing_type2_mpass; +static int o_heap_fibonacci; static int o_test_type = -1; enum test_type { @@ -127,34 +131,69 @@ static void free_graph(struct graph *g) } #define TEST_PREFIX(x) pairing_noparent_##x -#define HEAP_PAIRING +#define HEAP_USE_PAIRING #define TEST_WANT_SORT #include #define TEST_PREFIX(x) pairing_##x -#define HEAP_PAIRING +#define HEAP_USE_PAIRING #define TEST_WANT_SORT #define TEST_WANT_DIJKSTRA #define TEST_WANT_MIX #include -#define TEST_PREFIX(x) rank_pairing_noparent_##x -#define HEAP_RANK_PAIRING +#define TEST_PREFIX(x) rank_pairing_noparent_1pass_##x +#define HEAP_USE_RANK_PAIRING #define HEAP_RANK_PAIRING_TYPE1 +#define HEAP_RANK_PAIRING_1PASS #define TEST_WANT_SORT #include -#define TEST_PREFIX(x) rank_pairing_type1_##x -#define HEAP_RANK_PAIRING +#define TEST_PREFIX(x) rank_pairing_noparent_mpass_##x +#define HEAP_USE_RANK_PAIRING #define HEAP_RANK_PAIRING_TYPE1 +#define HEAP_RANK_PAIRING_MPASS +#define TEST_WANT_SORT +#include + +#define TEST_PREFIX(x) rank_pairing_type1_1pass_##x +#define HEAP_USE_RANK_PAIRING +#define HEAP_RANK_PAIRING_TYPE1 +#define HEAP_RANK_PAIRING_1PASS #define TEST_WANT_SORT #define TEST_WANT_DIJKSTRA #define TEST_WANT_MIX #include -#define TEST_PREFIX(x) rank_pairing_type2_##x -#define HEAP_RANK_PAIRING +#define TEST_PREFIX(x) rank_pairing_type1_mpass_##x +#define HEAP_USE_RANK_PAIRING +#define HEAP_RANK_PAIRING_TYPE1 +#define HEAP_RANK_PAIRING_MPASS +#define TEST_WANT_SORT +#define TEST_WANT_DIJKSTRA +#define TEST_WANT_MIX +#include + +#define TEST_PREFIX(x) rank_pairing_type2_1pass_##x +#define HEAP_USE_RANK_PAIRING #define HEAP_RANK_PAIRING_TYPE2 +#define HEAP_RANK_PAIRING_1PASS +#define TEST_WANT_SORT +#define TEST_WANT_DIJKSTRA +#define TEST_WANT_MIX +#include + +#define TEST_PREFIX(x) rank_pairing_type2_mpass_##x +#define HEAP_USE_RANK_PAIRING +#define HEAP_RANK_PAIRING_TYPE2 +#define HEAP_RANK_PAIRING_MPASS +#define TEST_WANT_SORT +#define TEST_WANT_DIJKSTRA +#define TEST_WANT_MIX +#include + +#define TEST_PREFIX(x) fibonacci_##x +#define HEAP_USE_FIBONACCI #define TEST_WANT_SORT #define TEST_WANT_DIJKSTRA #define TEST_WANT_MIX @@ -182,12 +221,20 @@ static void test_random_sort(uint n, uint k) pairing_noparent_sort(ary, n); if (o_heap_pairing) pairing_sort(ary, n); - if (o_heap_rank_pairing_noparent) - rank_pairing_noparent_sort(ary, n); - if (o_heap_rank_pairing_type1) - rank_pairing_type1_sort(ary, n); - if (o_heap_rank_pairing_type2) - rank_pairing_type2_sort(ary, n); + if (o_heap_rank_pairing_noparent_1pass) + rank_pairing_noparent_1pass_sort(ary, n); + if (o_heap_rank_pairing_noparent_mpass) + rank_pairing_noparent_mpass_sort(ary, n); + if (o_heap_rank_pairing_type1_1pass) + rank_pairing_type1_1pass_sort(ary, n); + if (o_heap_rank_pairing_type1_mpass) + rank_pairing_type1_mpass_sort(ary, n); + if (o_heap_rank_pairing_type2_1pass) + rank_pairing_type2_1pass_sort(ary, n); + if (o_heap_rank_pairing_type2_mpass) + rank_pairing_type2_mpass_sort(ary, n); + if (o_heap_fibonacci) + fibonacci_sort(ary, n); xfree(ary); } @@ -202,10 +249,16 @@ static void test_random_dijkstra(uint n, uint m, uint k) if (o_heap_pairing) pairing_dijkstra(g, start); - if (o_heap_rank_pairing_type1) - rank_pairing_type1_dijkstra(g, start); - if (o_heap_rank_pairing_type2) - rank_pairing_type2_dijkstra(g, start); + if (o_heap_rank_pairing_type1_1pass) + rank_pairing_type1_1pass_dijkstra(g, start); + if (o_heap_rank_pairing_type1_mpass) + rank_pairing_type1_mpass_dijkstra(g, start); + if (o_heap_rank_pairing_type2_1pass) + rank_pairing_type2_1pass_dijkstra(g, start); + if (o_heap_rank_pairing_type2_mpass) + rank_pairing_type2_mpass_dijkstra(g, start); + if (o_heap_fibonacci) + fibonacci_dijkstra(g, start); free_graph(g); } @@ -216,10 +269,16 @@ static void test_random_mix(uint n, uint m, uint k) if (o_heap_pairing) pairing_mix(n, m, k); - if (o_heap_rank_pairing_type1) - rank_pairing_type1_mix(n, m, k); - if (o_heap_rank_pairing_type2) - rank_pairing_type2_mix(n, m, k); + if (o_heap_rank_pairing_type1_1pass) + rank_pairing_type1_1pass_mix(n, m, k); + if (o_heap_rank_pairing_type1_mpass) + rank_pairing_type1_mpass_mix(n, m, k); + if (o_heap_rank_pairing_type2_1pass) + rank_pairing_type2_1pass_mix(n, m, k); + if (o_heap_rank_pairing_type2_mpass) + rank_pairing_type2_mpass_mix(n, m, k); + if (o_heap_fibonacci) + fibonacci_mix(n, m, k); } static struct opt_section options = { @@ -233,9 +292,13 @@ static struct opt_section options = { OPT_HELP("Heap types (default: compare all of them):"), OPT_BOOL(0, "pairing-noparent", o_heap_pairing_noparent, 0, "\tPairing heaps with no parent pointers (without Decrease, etc.)"), OPT_BOOL(0, "pairing", o_heap_pairing, 0, "\tPairing heaps"), - OPT_BOOL(0, "rank-pairing-noparent", o_heap_rank_pairing_noparent, 0, "\tRank pairing heaps with no parent pointers (without Decrease, etc.)"), - OPT_BOOL(0, "rank-pairing-type1", o_heap_rank_pairing_type1, 0, "\tType 1 of rank pairing heaps"), - OPT_BOOL(0, "rank-pairing-type2", o_heap_rank_pairing_type2, 0, "\tType 2 of rank pairing heaps"), + OPT_BOOL(0, "rank-pairing-noparent-1pass", o_heap_rank_pairing_noparent_1pass, 0, "\t1-pass rank pairing heaps with no parent pointers (without Decrease, etc.)"), + OPT_BOOL(0, "rank-pairing-noparent-mpass", o_heap_rank_pairing_noparent_mpass, 0, "\tM-pass rank pairing heaps with no parent pointers (without Decrease, etc.)"), + OPT_BOOL(0, "rank-pairing-type1-1pass", o_heap_rank_pairing_type1_1pass, 0, "\t1-pass type-1 of rank pairing heaps"), + OPT_BOOL(0, "rank-pairing-type1-mpass", o_heap_rank_pairing_type1_mpass, 0, "\tM-pass type-1 of rank pairing heaps"), + OPT_BOOL(0, "rank-pairing-type2-1pass", o_heap_rank_pairing_type2_1pass, 0, "\t1-pass type-2 of rank pairing heaps"), + OPT_BOOL(0, "rank-pairing-type2-mpass", o_heap_rank_pairing_type2_mpass, 0, "\tM-pass type-2 of rank pairing heaps"), + OPT_BOOL(0, "fibonacci", o_heap_fibonacci, 0, "\tFibonacci heaps"), OPT_HELP(""), OPT_HELP("Test type (default: a mix of various tests):"), OPT_SWITCH(0, "random-sort", o_test_type, TT_RANDOM_SORT, 0, "\tSort a random sequence (options: -n, -k)"), @@ -258,16 +321,24 @@ int main(int argc UNUSED, char **argv) if (1 && !o_heap_pairing_noparent && !o_heap_pairing - && !o_heap_rank_pairing_noparent - && !o_heap_rank_pairing_type1 - && !o_heap_rank_pairing_type2 + && !o_heap_rank_pairing_noparent_1pass + && !o_heap_rank_pairing_noparent_mpass + && !o_heap_rank_pairing_type1_1pass + && !o_heap_rank_pairing_type1_mpass + && !o_heap_rank_pairing_type2_1pass + && !o_heap_rank_pairing_type2_mpass + && !o_heap_fibonacci ) { o_heap_pairing_noparent = 1; o_heap_pairing = 1; - o_heap_rank_pairing_noparent = 1; - o_heap_rank_pairing_type1 = 1; - o_heap_rank_pairing_type2 = 1; + o_heap_rank_pairing_noparent_1pass = 1; + o_heap_rank_pairing_noparent_mpass = 1; + o_heap_rank_pairing_type1_1pass = 1; + o_heap_rank_pairing_type1_mpass = 1; + o_heap_rank_pairing_type2_1pass = 1; + o_heap_rank_pairing_type2_mpass = 1; + o_heap_fibonacci = 1; } switch (o_test_type) diff --git a/ucw/heap-gen.h b/ucw/heap-gen.h index 9b487cbb..393c6c9c 100644 --- a/ucw/heap-gen.h +++ b/ucw/heap-gen.h @@ -9,22 +9,41 @@ * * References: * - * [1] Michael L. Fredman, Robert Sedgewick, Daniel D. Sleator, Robert E. Tarjan, + * [1] Michael L. Fredman, Robert Endre Tarjan, + * Fibonacci heaps and their uses in improved network optimization algorithms, + * Journal of the ACM, 34(3):596–615, 1987. + * + * [2] Michael L. Fredman, Robert Sedgewick, Daniel D. Sleator, Robert E. Tarjan, * The pairing heap: A new form of self-adjusting heap, * Algorithmica, 1(1–4):111–129, 1986. * - * [2] Bernhard Haeupler, Siddhartha Sen, Robert E. Tarjan, + * [3] Bernhard Haeupler, Siddhartha Sen, Robert E. Tarjan, * Rank-Pairing Heaps, * SIAM J. Computing, 40(6):1463–1485, 2011. * - * [3] Daniel H. Larkin, Siddhartha Sen, Robert E. Tarjan, + * [4] Daniel H. Larkin, Siddhartha Sen, Robert E. Tarjan, * A Back-to-Basics Empirical Study of Priority Queues, * 2014. */ #define P(x) HEAP_PREFIX(x) -#if defined(HEAP_PAIRING) +#if defined(HEAP_USE_PAIRING) + +/* Pairing Heap: + * ============= + * + * We represent Pairing Heap as a half-ordered binary tree as defined in [2]. + * Root node contains the minimum, @left and @right fields in each node + * point to node's left and right children. Some operations like + * Decrease or Remove also need pointers to parents. + * + * Amortized complexity: + * -- FindMin, Insert, Merge -- O(1) + * -- DeleteMin, Remove, Increase -- O(log N) + * -- Decrease -- O(log N), O(2^sqrt(log log N)), Omega(log log N) + */ + # if defined(HEAP_WANT_REPLACE) # define HEAP_WANT_REMOVE # define HEAP_WANT_INSERT @@ -33,10 +52,36 @@ # define HEAP_NODE_STORE_PARENT # endif -#elif defined(HEAP_RANK_PAIRING) +#elif defined(HEAP_USE_RANK_PAIRING) + +/* Rank-Pairing Heap: + * ================== + * + * We follow the definitions in [3] and represent Rank-Pairing Heaps + * as forests of half-ordered binary trees. @root pointer in heap + * structure points to the minimum node, which is connected with roots + * of other half-trees by a circular single-link list (using @right pointer). + * @parent pointer in each root is NULL and @left pointer contains + * the root's child (at most one in a half-tree). Meaning of the pointers + * in non-root nodes are same as in pairing heaps. Each node also + * contains small number with subtree's rank. + * + * Amortized complexity: + * -- FindMin, Insert, Merge, Decrease -- O(1) + * -- DeleteMin, Remove, Increase -- O(log n) + * + * We support both "Type 1" (default) and "Type 2" variants from [3], + * and also both "1-pass" (default) and "m-pass" merging. + * + * FIXME: And maybe also try the 1-tree representation. + */ + # if !defined(HEAP_RANK_PAIRING_TYPE1) && !defined(HEAP_RANK_PAIRING_TYPE2) # define HEAP_RANK_PAIRING_TYPE1 # endif +# if !defined(HEAP_RANK_PAIRING_1PASS) && !defined(HEAP_RANK_PAIRING_MPASS) +# define HEAP_RANK_PAIRING_1PASS +# endif # if defined(HEAP_WANT_INCREASE) || defined(HEAP_WANT_REPLACE) # define HEAP_WANT_REMOVE # define HEAP_WANT_INSERT @@ -46,10 +91,45 @@ # define HEAP_NODE_STORE_PARENT # endif +#elif defined(HEAP_USE_FIBONACCI) + +/* + * Fibonacci Heap: + * =============== + * + * Defined in [1]. Represented as a forest of heap-ordered trees. + * @root pointer in heap structure points to the minimum node, which + * is connected with roots of other trees by a circular single-link list + * (using @right pointer). Other pointers in root nodes except @son + * should be cleared. @son field in each node contains its left-most + * child, @rank the number of children, @parent is the node's parent, + * @left and @right pointers connect all siblings to a circular + * double-link list (we need quick remove). Non-root nodes also + * contain @mark flag, which is true if we have cut a son from + * this node before. + * + * Amortized complexity: + * -- FindMin, Insert, Merge, Decrease -- O(1) + * -- DeleteMin, Remove, Increase -- O(log n) + * + * FIXME: Small optimizations: @left and @mark fields in roots could be undefined. + */ + +# if defined(HEAP_WANT_INCREASE) || defined(HEAP_WANT_REPLACE) +# define HEAP_WANT_REMOVE +# define HEAP_WANT_INSERT +# endif +# define HEAP_NODE_STORE_PARENT +# define HEAP_NODE_STORE_RANK + #else # error Missing heap type #endif +#if defined(HEAP_NODE_STORE_RANK) && !defined(HEAP_MAX_RANK) +# define HEAP_MAX_RANK 31 +#endif + typedef struct P(heap) *P(heap_p); typedef struct P(node) *P(node_p); @@ -62,6 +142,10 @@ struct P(node) { #if defined(HEAP_NODE_STORE_PARENT) P(node_p) parent; #endif +#if defined(HEAP_USE_FIBONACCI) + P(node_p) son; + bool mark; +#endif #if defined(HEAP_NODE_STORE_RANK) byte rank; #endif @@ -73,8 +157,11 @@ P(init)(P(heap_p) h) h->root = NULL; } -// @a and @b must be non-NULL roots of two half-trees, function merges them and returns new half-tree. -// @parent and @right pointers in @a and @b can be undefined, but in resulting root they are not automatically cleared. +#if defined(HEAP_USE_PAIRING) || defined(HEAP_USE_RANK_PAIRING) +/* Pairing Heap, Rank-Pairing Heap: + * @a and @b must be non-NULL roots of two half-trees, function merges them and returns new half-tree. + * @parent and @right pointers in @a and @b can be undefined, but in resulting root they are not automatically cleared. + */ static inline P(node_p) P(link)(P(heap_p) h, P(node_p) a, P(node_p) b) { @@ -94,17 +181,35 @@ P(link)(P(heap_p) h, P(node_p) a, P(node_p) b) c->parent = b; #endif #if defined(HEAP_NODE_STORE_RANK) - // "a->rank++" would not work for rank pairing heaps - a->rank = b->rank + 1; + a->rank++; #endif return a; } +#endif -#if defined(HEAP_PAIRING) && (defined(HEAP_WANT_DELETE_MIN) || defined(HEAP_WANT_REMOVE) || defined(HEAP_WANT_INCREASE)) -// Merges list of half-trees (from decomposed right spine of a half-tree) into one half-tree, -// using the two-pass pairing algorithm. Empty list is also supported. +#if defined(HEAP_USE_PAIRING) && defined(HEAP_NODE_STORE_PARENT) +/* Pairing Heap: + * Cuts @a, including the @left subtree, from a right spine. @a must not be root. Does not update @parent and @right pointers of @a. + */ +static inline void +P(cut_subtree)(P(node_p) a) +{ + if (a->parent->left == a) + a->parent->left = a->right; + else + a->parent->right = a->right; + if (a->right) + a->right->parent = a->parent; +} +#endif + +#if defined(HEAP_USE_PAIRING) && (defined(HEAP_WANT_DELETE_MIN) || defined(HEAP_WANT_REMOVE) || defined(HEAP_WANT_INCREASE)) +/* Pairing Heap: + * Merges list of half-trees (from decomposed right spine of a half-tree) into one half-tree, + * using the two-pass pairing algorithm. Empty list is also supported. + */ static P(node_p) -P(two_pass)(P(heap_p) h, P(node_p) a) +P(consolidate)(P(heap_p) h, P(node_p) a) { if (!a) return NULL; @@ -145,97 +250,136 @@ P(two_pass)(P(heap_p) h, P(node_p) a) } #endif -#if defined(HEAP_NODE_STORE_PARENT) -// Removes @x from a right spine. @x must not be root. Does not update @parent and @right pointers of @x. -static inline void -P(cut_from_spine)(P(node_p) a) -{ - if (a->parent->left == a) - a->parent->left = a->right; - else - a->parent->right = a->right; - if (a->right) - a->right->parent = a->parent; -} -#endif - -#if defined(HEAP_RANK_PAIRING) && (defined(HEAP_WANT_DELETE_MIN) || defined(HEAP_WANT_REMOVE)) +#if defined(HEAP_USE_RANK_PAIRING) && (defined(HEAP_WANT_DELETE_MIN) || defined(HEAP_WANT_REMOVE)) +/* Rank-Pairing Heap: + * Removes a root node @a (not necessarily minimum) and nodes on the right spine to the list of half-trees. + * Applies the 1-pass/m-pass merging of half-trees with same order, updates minimum. + */ static void P(cut_root_and_consolidate)(P(heap_p) h, P(node_p) a) { + // Prepare a single-link list of roots to merge. + // Inputs: + // 1) Circular single-link list of original roots. We need to include all items except @a. + // 2) NULL-terminated single-link list of the nodes on the right spine starting from @a->left. + // We also fix ranks on the disassembled spine to node's left son + 1. + P(node_p) stop = a; + if (a->left) + { + a = a->left; + P(node_p) b = a; + while (1) + { + b->rank = b->left ? b->left->rank + 1 : 0; + if (!b->right) + break; + b = b->right; + } + b->right = stop->right; + } + else if (a != a->right) + a = a->right; + else + { + // Special case: Removed last node in heap. + h->root = NULL; + return; + } + + // Now @a, @a->@right, ... contains the single-list of half-trees to merge, terminated by @stop pointer (not included). + // @parent pointers in the list are undefined. + + // Allocate array of buckets -- per-rank storage for an odd half-tree used during the merge. + // To achieve constant time, we track current subset of visited ranks in a bitmask, other indices stay undefined. + P(node_p) bucket[HEAP_MAX_RANK + 1]; + byte bucket_ary[HEAP_MAX_RANK + 1]; + byte bucket_count = 0; + u64 bucket_mask = 0; + + // Open a new circular single-list for resulting half-trees. P(node_p) min = NULL; P(node_p) list, *list_tail = &list; - P(node_p) bucket[32]; - byte bucket_ary[32]; - byte bucket_count = 0; - uint bucket_mask = 0; - // We are going to execute very similar code for two lists in a short loop: - // 1) The right spine of root->left - // 2) Remaining heap's half-trees except the deleted root - P(node_p) x = a->left, stop = NULL; - while (1) + // Do the 1-pass or m-pass merging. + do { - while (x != stop) + P(node_p) next = a->right; + while (1) { - P(node_p) next = x->right; - if (!(bucket_mask & (1U << x->rank))) + if (!(bucket_mask & (1LLU << a->rank))) { - bucket_mask |= 1U << x->rank; - bucket_ary[bucket_count++] = x->rank; - bucket[x->rank] = x; + // First visit of a bucket. + bucket_mask |= 1LLU << a->rank; + bucket_ary[bucket_count++] = a->rank; + bucket[a->rank] = a; + break; } - else if (!bucket[x->rank]) + else if (!bucket[a->rank]) { - bucket[x->rank] = x; + bucket[a->rank] = a; + break; } else { - P(node_p) y = bucket[x->rank]; - bucket[x->rank] = NULL; - x = P(link)(h, y, x); - *list_tail = x; - list_tail = &x->right; + P(node_p) b = bucket[a->rank]; + bucket[a->rank] = NULL; + + // Link two half-trees @a and @b. + a = P(link)(h, b, a); + +#if defined(HEAP_RANK_PAIRING_1PASS) + *list_tail = a; + list_tail = &a->right; #if defined(HEAP_NODE_STORE_PARENT) - x->parent = NULL; + a->parent = NULL; +#endif + if (!min || P(less)(h, a, min)) + min = a; + break; #endif - if (!min || P(less)(h, x, min)) - min = x; } - x = next; } - if (stop) - break; - stop = a; - x = a->right; + a = next; } + while (a != stop); - // Process remaining unpaired half-trees in buckets + // Process remaining unpaired half-trees in buckets. for (byte i = 0; i < bucket_count; i++) { - P(node_p) x = bucket[bucket_ary[i]]; - if (!x) + a = bucket[bucket_ary[i]]; + if (!a) continue; - *list_tail = x; - list_tail = &x->right; + *list_tail = a; + list_tail = &a->right; #if defined(HEAP_NODE_STORE_PARENT) - x->parent = NULL; + a->parent = NULL; #endif - if (!min || P(less)(h, x, min)) - min = x; + if (!min || P(less)(h, a, min)) + min = a; } - // Close the resulting list of half-trees and update minimum - *list_tail = list; // list can be undefined here for an empty list, but it's OK + // Close the resulting list of half-trees and update minimum. + *list_tail = list; h->root = min; } #endif -#if defined(HEAP_RANK_PAIRING) && (defined(HEAP_WANT_DECREASE) || defined(HEAP_WANT_REMOVE)) +#if defined(HEAP_USE_RANK_PAIRING) && (defined(HEAP_WANT_DECREASE) || defined(HEAP_WANT_REMOVE)) +/* Rank-Pairing Heap: + * Cut a non-root node @a, including the @left subtree, from a right spine and add it to the list of roots. + * Fixes ranks in ancestors (see [3] for details), but does not fix the rank of @a. + */ static void -P(cut_from_spine_and_update_ranks)(P(node_p) a) +P(cut_subtree_and_fix_ancestors)(P(heap_p) h, P(node_p) a) { P(node_p) x = a->parent, y = a->right; + + // Add @a to the list of roots. + a->parent = NULL; + a->right = h->root->right; + h->root->right = a; + + // Unlink @a from its parent and right child. if (x->left == a) x->left = y; else @@ -246,24 +390,37 @@ P(cut_from_spine_and_update_ranks)(P(node_p) a) y->parent = x; rank = y->rank; } + + // Loop to update ranks of ancestors. Should have constant amortized time in Decrease operation. + // Invariants: + // * @x is the current ancestor to check/fix. + // * @rank is rank of the child node we came from (can be -1 if we came from null subtree, see above) while (1) { + // If @x is a root, just set it's rank to "rank(left(x)) + 1" and stop P(node_p) z = x->parent; if (!z) { x->rank = rank + 1; break; } + #if defined(HEAP_RANK_PAIRING_TYPE1) + // "Type 1" variant of Rank-Pairing Heap: + // if rank(left(x)) == rank(right(x)), then rank(x) := rank(left(x)) + 1 if (!x->left || !x->right) rank++; else if (x->left->rank == x->right->rank) rank = x->left->rank + 1; + // otherwise rank(x) := max(rank(left(x)), rank(right(x))) else if (x->left->rank > x->right->rank) rank = x->left->rank; else rank = x->right->rank; #else + // "Type 1" variant of Rank-Pairing Heap + // if |rank(left(x)) - rank(right(x))| > 1, then rank(x) := max(rank(left(x)), rank(right(x))) + // else rank(x) := max(rank(left(x)), rank(right(x))) + 1 if (!x->left || !x->right) rank = rank > 0 ? rank : rank + 1; else if (x->left->rank >= x->right->rank) @@ -271,15 +428,167 @@ P(cut_from_spine_and_update_ranks)(P(node_p) a) else rank = x->right->rank + (x->right->rank - x->left->rank <= 1); #endif + + // Store the new rank to @x or stop if it would not decrease if (x->rank <= (byte)rank) break; x->rank = (byte)rank; - y = x; x = z; } } #endif +#if defined(HEAP_USE_FIBONACCI) && (defined(HEAP_WANT_DELETE_MIN) || defined(HEAP_WANT_REMOVE)) +/* Fibonacci Heap: + * Cut a root node @a (not necessarily minimum) and add its children to the list of trees. + * Applies the multi-pass merging of trees with same order, updates minimum. + */ +static void +P(cut_root_and_consolidate)(P(heap_p) h, P(node_p) a) +{ + // Prepare a single link list of roots to merge. + // Inputs: + // 1) Circular single-link list of original roots. We need to include all items except @a. + // 2) Circular double-link list of @a's children. + P(node_p) stop = a; + if (a->son) + { + a->son->left->right = a->right; + a = a->son; + } + else if (a != a->right) + a = a->right; + else + { + // Special case: Removed last node in heap. + h->root = NULL; + return; + } + // Now @a, @a->@right, ... contains the single-list of trees to merge, terminated by @stop pointer (not included). + // @left, @parent and @mark fields in the list are undefined. + + // Allocate array of buckets -- per-rank storage for an odd tree used during the merge. + // To achieve constant time, we track current subset of visited ranks in a bitmask, other indices stay undefined. + P(node_p) bucket[HEAP_MAX_RANK + 1]; + byte bucket_ary[HEAP_MAX_RANK + 1]; + byte bucket_count = 0; + u64 bucket_mask = 0; + + // Process all trees in the prepared link list. + // Try to put each tree @a to its bucket. If it's already full, link the two trees into one, + // and repeat the process for increased rank of the new tree. + // @left, @right, @parent and @mark fields in the buckets are undefined. + do + { + P(node_p) next = a->right; + while (1) + { + if (!(bucket_mask & (1LLU << a->rank))) + { + // First visit of a bucket. + bucket_mask |= 1LLU << a->rank; + bucket_ary[bucket_count++] = a->rank; + bucket[a->rank] = a; + break; + } + else if (!bucket[a->rank]) + { + bucket[a->rank] = a; + break; + } + else + { + P(node_p) b = bucket[a->rank]; + bucket[a->rank] = NULL; + + // Link two trees @a and @b. + P(node_p) c; + if (P(less)(h, b, a)) + { + c = a; + a = b; + b = c; + } + b->parent = a; + a->rank++; + if (!a->son) + { + b->left = b->right = b; + a->son = b; + } + else + { + b->left = a->son; + b->right = a->son->right; + b->left->right = b; + b->right->left = b; + } + } + } + a = next; + } + while (a != stop); + + // Make a circular single-link list of remaining trees and put minimum into the heap structure. + // Also fix undefined fields in root nodes. + P(node_p) min = NULL; + P(node_p) list, *list_tail = &list; + for (byte i = 0; i < bucket_count; i++) + { + P(node_p) b = bucket[bucket_ary[i]]; + if (!b) + continue; + *list_tail = b; + list_tail = &b->right; + b->parent = b->left = NULL; + b->mark = false; + if (!min || P(less)(h, b, min)) + min = b; + } + *list_tail = list; + h->root = min; +} +#endif + +#if defined(HEAP_USE_FIBONACCI) && (defined(HEAP_WANT_DECREASE) || defined(HEAP_WANT_REMOVE)) +/* Fibonacci Heap: + * Cut a non-root subtree @a from its parent and add it to the list of roots. + * Also mark/cut ancestors if necessary. + */ +static void +P(cut_subtree_and_fix_ancestors)(P(heap_p) h, P(node_p) a) +{ + P(node_p) b = a->parent; + while (1) + { + // Remove @a from @b's children + if (!--(b->rank)) + b->son = NULL; + else if (b->son == a) + b->son = a->right; + a->left->right = a->right; + a->right->left = a->left; + + // Add @a to list of roots and clear possibly set mark + a->mark = false; + a->left = a->parent = NULL; + a->right = h->root->right; + h->root->right = a; + + // Repeat for parent if needed + a = b; + b = a->parent; + if (!b) + break; + else if (!a->mark) + { + a->mark = true; + break; + } + } +} +#endif + #if defined(HEAP_WANT_EMPTY) static inline bool P(empty)(P(heap_p) h) @@ -300,18 +609,22 @@ P(find_min)(P(heap_p) h) static void P(insert)(P(heap_p) h, P(node_p) a) { -#if defined(HEAP_PAIRING) +#if defined(HEAP_USE_PAIRING) a->left = a->right = NULL; #if defined(HEAP_NODE_STORE_PARENT) a->parent = NULL; #endif h->root = h->root ? P(link)(h, h->root, a) : a; -#elif defined(HEAP_RANK_PAIRING) +#elif defined(HEAP_USE_RANK_PAIRING) || defined(HEAP_USE_FIBONACCI) a->left = NULL; #if defined(HEAP_NODE_STORE_PARENT) a->parent = NULL; #endif +#if defined(HEAP_USE_FIBONACCI) + a->son = NULL; + a->mark = false; +#endif #if defined(HEAP_NODE_STORE_RANK) a->rank = 0; #endif @@ -328,6 +641,7 @@ P(insert)(P(heap_p) h, P(node_p) a) if (P(less)(h, a, b)) h->root = a; } + #else # error HEAP_WANT_INSERT is not supported for this heap type #endif @@ -342,9 +656,9 @@ P(merge)(P(heap_p) h, P(heap_p) g) if (!g) return; g->root = NULL; -#if defined(HEAP_PAIRING) +#if defined(HEAP_USE_PAIRING) h->root = h->root ? P(link)(h, h->root, a) : a; -#elif defined(HEAP_RANK_PAIRING) +#elif defined(HEAP_USE_RANK_PAIRING) || defined(HEAP_USE_FIBONACCI) P(node_p) b = h->root; if (!b) h->root = a; @@ -369,9 +683,11 @@ P(delete_min)(P(heap_p) h) P(node_p) a = h->root; if (!a) return NULL; -#if defined(HEAP_PAIRING) - h->root = P(two_pass)(h, a->left); -#elif defined(HEAP_RANK_PAIRING) +#if defined(HEAP_USE_PAIRING) + h->root = P(consolidate)(h, a->left); +#elif defined(HEAP_USE_RANK_PAIRING) + P(cut_root_and_consolidate)(h, a); +#elif defined(HEAP_USE_FIBONACCI) P(cut_root_and_consolidate)(h, a); #else # error HEAP_WANT_DELETE_MIN is not supported for this heap type @@ -384,26 +700,24 @@ P(delete_min)(P(heap_p) h) static void P(remove)(P(heap_p) h, P(node_p) a) { -#if defined(HEAP_PAIRING) - P(node_p) b = P(two_pass)(h, a->left); + // FIXME: We could generally avoid some comparisons if not deleting minimum and if merging is + // done carefully so that the old minimum stays on top of possibly more equal nodes. +#if defined(HEAP_USE_PAIRING) + P(node_p) b = P(consolidate)(h, a->left); if (!a->parent) { h->root = b; return; } - P(cut_from_spine)(a); + P(cut_subtree)(a); if (b) h->root = P(link)(h, h->root, b); -#elif defined(HEAP_RANK_PAIRING) - // Move @x to a root by emulating decrease; we don't need to update heap->root yet + +#elif defined(HEAP_USE_RANK_PAIRING) || defined(HEAP_USE_FIBONACCI) if (a->parent) - { - P(cut_from_spine_and_update_ranks)(a); - a->parent = NULL; - a->right = h->root->right; - h->root->right = a; - } + P(cut_subtree_and_fix_ancestors)(h, a); P(cut_root_and_consolidate)(h, a); + #else # error HEAP_WANT_REMOVE is not supported for this heap type #endif @@ -414,13 +728,14 @@ P(remove)(P(heap_p) h, P(node_p) a) static void P(decrease)(P(heap_p) h, P(node_p) a) { -#if defined(HEAP_PAIRING) +#if defined(HEAP_USE_PAIRING) if (!a->parent) return; - P(cut_from_spine)(a); + P(cut_subtree)(a); a->parent = a->right = NULL; h->root = P(link)(h, h->root, a); -#elif defined(HEAP_RANK_PAIRING) + +#elif defined(HEAP_USE_RANK_PAIRING) if (!a->parent) { if (a == h->root) @@ -428,14 +743,25 @@ P(decrease)(P(heap_p) h, P(node_p) a) } else { - P(cut_from_spine_and_update_ranks)(a); + P(cut_subtree_and_fix_ancestors)(h, a); a->rank = a->left ? a->left->rank + 1 : 0; - a->parent = NULL; - a->right = h->root->right; - h->root->right = a; } if (P(less)(h, a, h->root)) h->root = a; + +#elif defined(HEAP_USE_FIBONACCI) + if (!a->parent) + { + if (a == h->root) + return; + } + else if (!P(less)(h, a, a->parent)) + return; + else + P(cut_subtree_and_fix_ancestors)(h, a); + if (P(less)(h, a, h->root)) + h->root = a; + #else # error HEAP_WANT_DECREASE is not supported for this heap type #endif @@ -446,13 +772,13 @@ P(decrease)(P(heap_p) h, P(node_p) a) static void P(increase)(P(heap_p) h, P(node_p) a) { -#if defined(HEAP_PAIRING) +#if defined(HEAP_USE_PAIRING) if (!a->left) return; - P(node_p) b = P(two_pass)(h, a->left); + P(node_p) b = P(consolidate)(h, a->left); a->left = NULL; h->root = P(link)(h, h->root, b); -#elif defined(HEAP_RANK_PAIRING) +#elif defined(HEAP_USE_RANK_PAIRING) || defined(HEAP_USE_FIBONACCI) // FIXME: Optimize? P(remove)(h, a); P(insert)(h, a); @@ -466,7 +792,7 @@ P(increase)(P(heap_p) h, P(node_p) a) static void P(replace)(P(heap_p) h, P(node_p) a) { -#if defined(HEAP_PAIRING) || defined(HEAP_RANK_PAIRING) +#if defined(HEAP_USE_PAIRING) || defined(HEAP_USE_RANK_PAIRING) || defined(HEAP_USE_FIBONACCI) P(remove)(h, a); P(insert)(h, a); #else @@ -477,10 +803,13 @@ P(replace)(P(heap_p) h, P(node_p) a) #undef HEAP_PREFIX -#undef HEAP_PAIRING -#undef HEAP_RANK_PAIRING +#undef HEAP_USE_PAIRING +#undef HEAP_USE_RANK_PAIRING #undef HEAP_RANK_PAIRING_TYPE1 #undef HEAP_RANK_PAIRING_TYPE2 +#undef HEAP_RANK_PAIRING_1PASS +#undef HEAP_RANK_PAIRING_MPASS +#undef HEAP_USE_FIBONACCI #undef HEAP_WANT_EMPTY #undef HEAP_WANT_FIND_MIN @@ -495,3 +824,4 @@ P(replace)(P(heap_p) h, P(node_p) a) #undef P #undef HEAP_NODE_STORE_PARENT #undef HEAP_NODE_STORE_RANK +#undef HEAP_MAX_RANK -- 2.39.2