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 and/or heap:
“Why does philosophy use concepts and why does faith use symbols if both try to express the same ultimate? The answer, of course, is that the relation to the ultimate is not the same in each case. The philosophical relation is in principle a detached description of the basic structure in which the ultimate manifests itself. The relation of faith is in principle an involved expression of concern about the meaning of the ultimate for the faithful.”
—Paul Tillich (1886–1965)
“We cannot be any stronger in our foreign policy—for all the bombs and guns we may heap up in our arsenals—than we are in the spirit which rules inside the country. Foreign policy, like a river, cannot rise above its source.”
—Adlai Stevenson (1900–1965)