shithub: asif

Info  •  Files  •  Log

pheap: finally fix

some assumptions were wrong, others were unverified.  three pointers
are used to represent the graph: parent, left (children), right (older
sibling).  siblings are stored as a linked list, with the most recent
one being in front.  most importantly, parent is either the previous
sibling in the list, or if it's the first node, the parent in the
tree.  essentially, this is a doubly linked list, with the parent
pointer helping efficiency despite the overload.  the biggest source
of issue was managing links correctly.

mergequeue takes the roots of two heaps.  a root may not by definition
have a parent or sibling (right pointer), but the left trees must be
taken care of.  mergepairs takes the *root* of a heap (when popping,
the root node is slashed off), splits, then merges recursively from
left to right.  here right nodes must be handled correctly to avoid
dropping entire branches of the tree and maintain parent links
correctly.  split trees are cut off from each other; the first two
heaps are merged together, and a third is recursively split and merged
the same way.  finally, decreasekey must preserve and fix the siblings
list, cut off the node, then merge the new heap with the root.
description subject to potential bugs, ymmv.

all relatively simple issues...  interesting future directions: smooth
heaps (2018 Kozma and Saranurak), related slim heaps.

--- a/pheap.c

+++ b/pheap.c

@@ -21,6 +21,9 @@

 	if(p == queue)

 		fprint(2, "pheap::checkheap %#p\n", p);

 	assert(p == queue || p->parent != nil && p->parent != p);

+	assert(p->parent == nil || p->parent->right == p || p->parent->left == p);

+	if(p->parent != nil && p->parent->left == p)

+		assert(p->parent->n <= p->n);

 	for(q=p; q!=nil; q=q->right)

 		checkheap(q->left, queue);

 }

@@ -37,7 +40,7 @@

 	for(i=0; i<level; i++)

 		fprint(2, "\t");

 	for(q=p; q!=nil; q=q->right){

-		fprint(2, "[%#p,%.5f]", q, q->n);

+		fprint(2, "[%#p %.5f] — ", q, q->n);

 		printright(q->left, level+1);

 	}

 	fprint(2, "\n");

@@ -73,11 +76,15 @@

 		return a;

 	else if(a->n < b->n){

 		b->right = a->left;

+		if(a->left != nil)

+			a->left->parent = b;

 		a->left = b;

 		b->parent = a;

 		return a;

 	}else{

 		a->right = b->left;

+		if(b->left != nil)

+			b->left->parent = a;

 		b->left = a;

 		a->parent = b;

 		return b;

@@ -85,27 +92,21 @@

 }

 static Pairheap *

-mergepairs(Pairheap *a, Pairheap *q)

+mergepairs(Pairheap *a)

 {

 	Pairheap *b, *c;

 	if(a == nil)

 		return nil;

-	if(a->parent != nil && a->parent->left == a)

-		a->parent->left = nil;

 	a->parent = nil;

-	assert(a->parent == nil || a->parent->left != a);

 	b = a->right;

 	if(b == nil)

 		return a;

 	a->right = nil;

-	if(b->parent != nil && b->parent->left == b)

-		b->parent->left = nil;

-	b->parent = nil;

-	assert(b->parent == nil || b->parent->left != b);

 	c = b->right;

+	b->parent = nil;

 	b->right = nil;

-	return mergequeue(mergequeue(a, b), mergepairs(c, q));

+	return mergequeue(mergequeue(a, b), mergepairs(c));

 }

 void

@@ -129,8 +130,9 @@

 	if(p == nil)

 		return nil;

 	dprint(Logparanoid, "pheap::popqueue %#p %.6f\n", p, p->n);

-	*queue = mergepairs(p->left, p);

+	*queue = mergepairs(p->left);

 	debugqueue(queue);

+	p->left = p->right = nil;

 	return p;

 }

@@ -137,25 +139,25 @@

 void

 decreasekey(Pairheap *p, double Δ, Pairheap **queue)

 {

-	Pairheap *q;

-

 	dprint(Logparanoid, "pheap::decreasekey %#p %.6f Δ %.6f\n", p, p->n, Δ);

-	p->n -= Δ;

-	if(p->parent != nil && p->n < p->parent->n){

-		assert(p->parent->left != nil);

-		if(p->parent->left == p)

-			p->parent->left = p->right;

-		else{

-			for(q=p->parent->left; q!=nil && q!=p; q=q->right)

-				if(q->right == p)

-					break;

-			assert(q != nil);

-			q->right = p->right;

-		}

-		p->parent = nil;

-		*queue = mergequeue(p, *queue);

-		debugqueue(queue);

+	if(p->parent == nil){

+		p->n -= Δ;

+		return;

 	}

+	if(p->parent->left == p){

+		assert(p->parent->n <= p->n);

+		p->parent->left = p->right;

+	}else{

+		assert(p->parent->right == p);

+		p->parent->right = p->right;

+	}

+	if(p->right != nil)

+		p->right->parent = p->parent;

+	p->right = nil;

+	p->parent = nil;

+	p->n -= Δ;

+	*queue = mergequeue(p, *queue);

+	debugqueue(queue);

 }

 Pairheap *