Tuesday, February 03, 2004
Warning: the average reader will not enjoy this post. It's quite geeky and may be mildly disturbing to all who find school un-orgasmic. (And maybe even those who do.)
I just thought I needed to tell you all about the orgas-tastic (what? It's a city in West Virginia) data structure we covered today. It's called a binomial queue. It counts in binary. Yay. Insert, FindMin, DeleteMin, and Merge are all in Theta(log N) time. The structure is not just one tree (ordered as a heap, ie each node has only smaller nodes below it), but many, making it called a forest. Hehe. Each tree, or block, is a multi-way tree, meaning it can have an unspecified number of nodes. B0 has 20=1 nodes in it. B1 has 21=2 nodes in it. Each Bi consists of two blocks of Bi-1. To maintain the heap structure, the block with the smaller root has its root become parent of the other block. Each Bi is a composition of Bi-1s. The number of nodes is represented as a binary number in where Bi is the ith digit. To merge another binomial queue, one simply adds the Bis together, as one would a binary number, making sure to carry when appropriate. So DeleteMin simply finds the smallest by checking each root, deletes it, and then merges the remainder of its block as a new queue into the remaining structure.
I think this is my favorite basic data type ever. Um.... binary....
For the extra-studious of you, you can look at my teacher's slides here.
"There are 10 types of people in this world: those who understand binary, and those who don't."
I just thought I needed to tell you all about the orgas-tastic (what? It's a city in West Virginia) data structure we covered today. It's called a binomial queue. It counts in binary. Yay. Insert, FindMin, DeleteMin, and Merge are all in Theta(log N) time. The structure is not just one tree (ordered as a heap, ie each node has only smaller nodes below it), but many, making it called a forest. Hehe. Each tree, or block, is a multi-way tree, meaning it can have an unspecified number of nodes. B0 has 20=1 nodes in it. B1 has 21=2 nodes in it. Each Bi consists of two blocks of Bi-1. To maintain the heap structure, the block with the smaller root has its root become parent of the other block. Each Bi is a composition of Bi-1s. The number of nodes is represented as a binary number in where Bi is the ith digit. To merge another binomial queue, one simply adds the Bis together, as one would a binary number, making sure to carry when appropriate. So DeleteMin simply finds the smallest by checking each root, deletes it, and then merges the remainder of its block as a new queue into the remaining structure.
I think this is my favorite basic data type ever. Um.... binary....
For the extra-studious of you, you can look at my teacher's slides here.
"There are 10 types of people in this world: those who understand binary, and those who don't."
Subscribe to Posts [Atom]