From d009c6234c499968bba36901160dae658df70b50 Mon Sep 17 00:00:00 2001 From: Søren Sandmann Pedersen Date: Fri, 9 Mar 2012 14:15:57 -0500 Subject: asdf --- radixheap | 43 +++++++++++++++++++++++++++++++------------ 1 file 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 - -- cgit v1.2.3