From c61fd255e8133ff34c8c40faa69807aab76a3b59 Mon Sep 17 00:00:00 2001 From: Pavel Charvat Date: Wed, 22 Aug 2018 19:06:15 +0200 Subject: [PATCH] Heaps: Small fixes in comments. --- ucw/heap-gen.h | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) diff --git a/ucw/heap-gen.h b/ucw/heap-gen.h index 393c6c9c..c1a66d06 100644 --- a/ucw/heap-gen.h +++ b/ucw/heap-gen.h @@ -73,7 +73,7 @@ * 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. + * FIXME: Maybe also try the 1-tree representation. */ # if !defined(HEAP_RANK_PAIRING_TYPE1) && !defined(HEAP_RANK_PAIRING_TYPE2) @@ -290,7 +290,8 @@ P(cut_root_and_consolidate)(P(heap_p) h, P(node_p) a) // @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. + // To achieve constant time initialization, we track current subset of visited ranks in a bitmask, other indices stay undefined. + // Alternatively we could spend O(max current rank) time for initializations, the amortized complexity would be same. P(node_p) bucket[HEAP_MAX_RANK + 1]; byte bucket_ary[HEAP_MAX_RANK + 1]; byte bucket_count = 0; @@ -468,7 +469,8 @@ P(cut_root_and_consolidate)(P(heap_p) h, P(node_p) a) // @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. + // To achieve constant time initialization, we track current subset of visited ranks in a bitmask, other indices stay undefined. + // Alternatively we could spend O(max current rank) time for initializations, the amortized complexity would be same. P(node_p) bucket[HEAP_MAX_RANK + 1]; byte bucket_ary[HEAP_MAX_RANK + 1]; byte bucket_count = 0; -- 2.39.2