asdf

1 files changed, 31 insertions, 12 deletions

diff --git a/radixheap b/radixheap
index e1d4596..e42f9a0 100644
--- a/radixheap
+++ b/radixheap
@@ -29,26 +29,35 @@ last value deleted from the queue.
 
 The invariant is as follows:
 
-    - bucket k contains items where bit k - 1 is different from
-      last_deleted, and where bits k to 31 are equal to last_deleted.
+      Bucket k contains items where bit k - 1 is the highest bit
+      that is different from last_deleted. The items in bucket 0
+      are equal to last_deleted.
 
-That means the items in bucket 0 are equal to last_deleted. Items in
-bucket 10 are different in the 9th bit, and possibly in bit 0 to
-8. And items in bucket 32 are different in bit 31 and possibly any
-other bit.
+That means items in bucket 10 are different in the 9th bit, and
+possibly in bit 0 to 8. And items in bucket 32 are different in bit 31
+and possibly any other bit.
+
+Operations
 
 When a new item is inserted, it has to be added to the correct
 bucket. How can we compute the bucket number? We have to find the
-highest bit where the two numbers differ. This is easily done by
-XOR'ing them together, and then finding the highest set bit. Adding
-one gives the bucket number. Inserting a new item is as simple as
-adding it to the bucket.
+highest bit where the new item differs from last_deleted. This is
+easily done by XOR'ing them together, and then finding the highest set
+bit. Adding one gives the bucket number. Inserting a new item is as
+simple as adding it to the bucket. The invariant is clearly preserved
+because last_deleted didn't change and the new item will be in the
+correct bucket.
 
 Extracting the minimum involves first finding the minimal item by
 walking the lowest-numbered non-empty bucket and finding the minimal
 item in that bucket. Then that item is deleted and last_deleted is
-updated.  Then the bucket is walked again and each item is moved to a
-new bucket according to the new last_deleted.
+updated.  Then the bucket is walked again and each item is reinserted
+into a new bucket according to the new last_deleted item.
+
+We have to make sure this preserves this invariant. All the items in
+the bucket that is being redistributed will satisfy the invariant
+because they are simply being reinserted. The items that are not being
+redistributed will still differ
 
 We have to be sure this doesn't violate the invariant. First note that
 all the items in the bucket that is being redistributed will satisfy
@@ -58,6 +67,16 @@ last_deleted in bit c - 1. If it weren't, the new last_deleted would
 itself have belonged in bucket c. And there are no non-empty buckets
 with a lower number than the one that is being redistributed.
 
+Performance
+- Of insertion
+- Of extraction
+
+Refinement
+- Maintain a pointer to the minimum item in each bucket.
+- Maintain a pointer to the minimum bucket
+
+
+
 So 
 
 items are different from the previous last_deleted at position k -