Structure of A Binomial Heap
A binomial heap is implemented as a set of binomial trees that satisfy the binomial heap properties:
- Each binomial tree in a heap obeys the minimum-heap property: the key of a node is greater than or equal to the key of its parent.
- There can only be either one or zero binomial trees for each order, including zero order.
The first property ensures that the root of each binomial tree contains the smallest key in the tree, which applies to the entire heap.
The second property implies that a binomial heap with n nodes consists of at most log n + 1 binomial trees. In fact, the number and orders of these trees are uniquely determined by the number of nodes n: each binomial tree corresponds to one digit in the binary representation of number n. For example number 13 is 1101 in binary, and thus a binomial heap with 13 nodes will consist of three binomial trees of orders 3, 2, and 0 (see figure below).
Example of a binomial heap containing 13 nodes with distinct keys.
The heap consists of three binomial trees with orders 0, 2, and 3.
Read more about this topic: Binomial Heap
Famous quotes containing the words structure of a, structure of, structure and/or heap:
“... the structure of a page of good prose is, analyzed logically, not something frozen but the vibrating of a bridge, which changes with every step one takes on it.”
—Robert Musil (1880–1942)
“Just as a new scientific discovery manifests something that was already latent in the order of nature, and at the same time is logically related to the total structure of the existing science, so the new poem manifests something that was already latent in the order of words.”
—Northrop Frye (b. 1912)
“Each structure and institution here was so primitive that you could at once refer it to its source; but our buildings commonly suggest neither their origin nor their purpose.”
—Henry David Thoreau (1817–1862)
“—First a shiver, and then a thrill,
Then something decidedly like a spill,—
And the parson was sitting up on a rock,
At half-past nine by the meet’n’-house clock,—
Just the hour of the Earthquake shock!
MWhat do you think the parson found,
When he got up and stared around?
The poor old chaise in a heap or mound,
As if it had been to the mill and ground!”
—Oliver Wendell Holmes, Sr. (1809–1894)