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:
“Man is more disposed to domination than freedom; and a structure of dominion not only gladdens the eye of the master who rears and protects it, but even its servants are uplifted by the thought that they are members of a whole, which rises high above the life and strength of single generations.”
—Karl Wilhelm Von Humboldt (1767–1835)
“There is no such thing as a language, not if a language is anything like what many philosophers and linguists have supposed. There is therefore no such thing to be learned, mastered, or born with. We must give up the idea of a clearly defined shared structure which language-users acquire and then apply to cases.”
—Donald Davidson (b. 1917)
“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)