計算機科學外文翻譯-wenkub.com
2024-08-30 16:58 本頁面
【正文】 性能對于有n個節(jié)點的二項堆，以下操作的時間復(fù)雜度為O(log n)：(1)插入一個新的節(jié)點(2)查找最小節(jié)點(3)刪除最小節(jié)點(4)減小給定節(jié)點的關(guān)鍵字(5)刪除指定節(jié)點(6)合并兩個二項堆尋找最小節(jié)點也可以通過使用一個額外的指針在O(1)時間內(nèi)完成。function deleteMin(heap) min = ().first() for each current in () if min then min = current for each tree in () (tree) (min)merge(heap, tmp)減小節(jié)點值減小某個節(jié)點關(guān)鍵字之后，它可能會比其父節(jié)點的關(guān)鍵字來的小，從而違背了最小堆的性質(zhì)。通過將子樹按照階數(shù)從小到大重新排列形成一個新堆。通過使用指向最小節(jié)點的指針，此操作的時間可以降低到O（1）。插入可以通過簡單地創(chuàng)建一個只包含此元素的新堆，然后將它與原來的堆合并。在算法的過程中，我們需要研究最三棵樹的任何順序的情況。和合并算法相似的是兩個二項堆的根節(jié)點鏈表同時被遍歷。對應(yīng)上圖，為了合并兩棵階數(shù)相同的二項樹，首先比較根節(jié)點的關(guān)鍵字。由于二叉樹的根節(jié)點具有最小關(guān)鍵字，通過比較兩個根節(jié)點的關(guān)鍵字大小，其中較小的成為最小關(guān)鍵字，并成為新的根節(jié)點。例如13的二進制表示是1101，因此包含13個節(jié)點的二項堆包括三棵二叉樹 ，階數(shù)分別為3，2和0（見下圖）。包括0階二叉樹。這個特點對二叉堆的合并操作來說至關(guān)重要，這也是二項堆相對于傳統(tǒng)堆擁有的主要優(yōu)勢。連接在根節(jié)點上的是所有低階的子樹，這在圖中被高亮顯示。二項樹二項堆是二項樹的集合（與二項堆相比二叉堆則只有一顆二項樹）。 Delete given element from the heap Insert a new element to the heap 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: Find the element with minimum key Merge two given heaps to one heapFinding the element with minimum key can also be done in O(1) by usi
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1