計(jì)算機(jī)科學(xué)外文翻譯(已修改)
2025-09-04 16:58 本頁面
【正文】 Binomial heapIn puter science, a binomial heap is a heap similar to a binary heap but also supports quick merging of two heaps. This is achieved by using a special tree structure. It is important as an implementation of the mergeable heap abstract data type(also called meldable heap), which is a priority queue supporting merge operation.Binomial tree A binomial heap is implemented as a collection of binomial trees (pare with a binary heap, which has a shape of a single binary tree). A binomial tree is defined recursively: A binomial tree of order 0 is a single node A binomial tree of order k has a root node whose children are roots of binomial trees of orders k?1, k?2, ..., 2, 1, 0 (in this order).Binomial trees of order 0 to 3: Each tree has a root node with subtrees of all lower ordered binomial trees, which have been highlighted. For example, the order 3 binomial tree is connected to an order 2, 1, and 0 (highlighted as blue, green and red respectively) binomial tree.A binomial tree of order k has 2k nodes, height k.Because of its unique structure, a binomial tree of order k can be constructed from two trees of order k?1 trivially by attaching one of them as the leftmost child of root of the other one. This feature is central to the merge operation of a binomial heap, which is its major advantage over other conventional heaps.The name es from the shape: a binomial tree of order has nodes at depth . 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 minimumheap 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 logn + 1 binomial trees. In fact, the n
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1