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, 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)
“... the structure of our public morality crashed to earth. Above its grave a tombstone read, “Be tolerant—even of evil.” Logically the next step would be to say to our commonwealth’s criminals, “I disagree that it’s all right to rob and murder, but naturally I respect your opinion.” Tolerance is only complacence when it makes no distinction between right and wrong.”
—Sarah Patton Boyle, U.S. civil rights activist and author. The Desegregated Heart, part 2, ch. 2 (1962)
“In Africa I had indeed found a sufficiently frightful kind of loneliness but the isolation of this American ant heap was even more shattering.”
—Louis-Ferdinand Céline (1894–1961)