http://forums.topcoder.com/?module=Thread&threadID=694678&start=0&mc=2
According to the property can be seen @
http://img843.imageshack.us/img843/9994/algorithmsdoubtdatastru.jpg
I don't understand how or in what case , the comparison would be less than 0.N/2 + 1.N/4 + ......
I see how or why it would be less than N.
Does anyone think it could be an error?
How is it less than 0.8/2 +1.8/4 + 2.8/8 = 2+2 = 4
Total = 4
One way of looking at it is by considering number of comparisons
for formation of
(1-heap + 2-heap + 4-heap)
is equivalent to (0 + 1 + 2) = 3 comparisons for a N = 8.
3 < Total ?
Let consider the following binomial queue:
T
/
S
/ \
R N
/ \ / \
O A G I
Insertion of Nodes in following order:
T,I,N,G,S,A,R,O
as can be seen @ http://goo.gl/4Fq5X
comparisons
1-heap - 0
2-heap - 1 ( pairing 1-heap and 1-heap )
4-heap - 3 ( 2-heap(1) + 2-heap(1) + pairing 2-heap and 2-heap )
according to the insertion code and functions below:
***********************************************************************
Program 9.14 Insertion into a binomial queue
To insert a node into a binomial queue, we first make the node into a 1-heap, identify it as a carry 1-heap, and then iterate the following process starting at i = 0. If the binomial queue has no 2i-heap, we put the carry 2i-heap into the queue. If the binomial queue has a 2i-heap, we combine that with the new one (using the pair method from Program 9.13) to make a 2i+1-heap, increment i, and iterate until finding an empty heap position in the binomial queue. When we carry in to the null link at the end of the array, we call grow to increase the size of the array by 1 and put a null link in the new position (see text).
Object insert(ITEM v)
{ Node t = new Node(v), c = t;
for (int i = 0; i < bq.length+1; i++)
{
if (c == null) break;
if (i == bq.length-1) bq = grow(bq);
if (bq[i] == null) { bq[i] = c; break; }
c = pair(c, bq[i]); bq[i] = null;
}
return t;
}
PQfull()
{ bq = new Node[1]; bq[0] = null; }
private static class Node
{ ITEM item; Node l, r;
Node(ITEM v)
{ item = v; l = null; r = null; }
}
private Node[] bq;
We need to change only a few links to combine two equal-sized powerof-2 heaps into one power-of-2 heap that is twice that size. This method, which we define as a private method in the implementation, is one key to the efficiency of the binomial queue algorithm.
static Node pair(Node p, Node q)
{
if (p.item.less(q.item))
{ p.r = q.l; q.l = p; return q; }
else { q.r = p.l; p.l = q; return p; }
}
http://img843.imageshack.us/img843/9994/algorithmsdoubtdatastru.jpg
I don't understand how or in what case , the comparison would be less than 0.N/2 + 1.N/4 + ......
I see how or why it would be less than N.
Does anyone think it could be an error?
How is it less than 0.8/2 +1.8/4 + 2.8/8 = 2+2 = 4
Total = 4
One way of looking at it is by considering number of comparisons
for formation of
(1-heap + 2-heap + 4-heap)
is equivalent to (0 + 1 + 2) = 3 comparisons for a N = 8.
3 < Total ?
Let consider the following binomial queue:
T
/
S
/ \
R N
/ \ / \
O A G I
Insertion of Nodes in following order:
T,I,N,G,S,A,R,O
as can be seen @ http://goo.gl/4Fq5X
comparisons
1-heap - 0
2-heap - 1 ( pairing 1-heap and 1-heap )
4-heap - 3 ( 2-heap(1) + 2-heap(1) + pairing 2-heap and 2-heap )
according to the insertion code and functions below:
***********************************************************************
Program 9.14 Insertion into a binomial queue
To insert a node into a binomial queue, we first make the node into a 1-heap, identify it as a carry 1-heap, and then iterate the following process starting at i = 0. If the binomial queue has no 2i-heap, we put the carry 2i-heap into the queue. If the binomial queue has a 2i-heap, we combine that with the new one (using the pair method from Program 9.13) to make a 2i+1-heap, increment i, and iterate until finding an empty heap position in the binomial queue. When we carry in to the null link at the end of the array, we call grow to increase the size of the array by 1 and put a null link in the new position (see text).
Object insert(ITEM v)
{ Node t = new Node(v), c = t;
for (int i = 0; i < bq.length+1; i++)
{
if (c == null) break;
if (i == bq.length-1) bq = grow(bq);
if (bq[i] == null) { bq[i] = c; break; }
c = pair(c, bq[i]); bq[i] = null;
}
return t;
}
PQfull()
{ bq = new Node[1]; bq[0] = null; }
private static class Node
{ ITEM item; Node l, r;
Node(ITEM v)
{ item = v; l = null; r = null; }
}
private Node[] bq;
We need to change only a few links to combine two equal-sized powerof-2 heaps into one power-of-2 heap that is twice that size. This method, which we define as a private method in the implementation, is one key to the efficiency of the binomial queue algorithm.
static Node pair(Node p, Node q)
{
if (p.item.less(q.item))
{ p.r = q.l; q.l = p; return q; }
else { q.r = p.l; p.l = q; return p; }
}
