Binomial Heap

PAL Definice Binomiální halda

A data structure made of Binomial Trees

Operations

Merge

Merging trees of the same order is trivial, following the definition. Merging heaps requires merging trees from lowest order to highest and potentially taking care of a “carry” tree.

MergeHeaps(X, Y) {
    result = empty heap
    C = null  // carry tree
    
    for d = 0 to max(maxOrder(X), maxOrder(Y)) {
        A = tree of order d from X (or null)
        B = tree of order d from Y (or null)
        count = number of non-null trees among {A, B, C}
        
        if (count == 1) {
            Add the non-null tree to result
            C = null
        }
        else if (count == 2) {
            C = MergeTree(the two non-null trees)
        }
        else if (count == 3) {
            Add tree with smallest root to result
            C = MergeTree(other two trees)
        }
    }
    
    if (C != null) add C to result
    Update min pointer by scanning all roots
    return result
}