Lec 5: Binomial Queue⚓︎

typedef struct BinNode * Position;
typedef struct Collection * BinQueue;
typedef struct BinNode * BinTree;

struct BinNode {
    ElementType Element;
    Position    LeftChild;
    Position    NextSibling;
};

struct Collection {
    int     CurrentSize; // total number of nodes
    BinTree TheTrees[MaxTrees];
}

BinTree CombineTrees(BinTree T1, BinTree T2) {
    // merge equal-sized T1 and T2
    if (T1->Element > T2->Element)
        // attach the larger one to the smaller one
        return CombineTrees(T2, T1);
    // insert T2 to the front of the children list of T1
    T2->NextSibling = T1->LeftChild;
    T1->LeftChild = T2;
    return T1;
}
// Time Complexity: O(1)

BinQueue Merge(BinQueue H1, BinQueue H2) {
    BinTree T1, T2, Carry = NULL;
    int i, j;
    if (H1->CurrentSize + H2->CurrentSize > Capacity)
        ErrorMessage();
    H1->CurrentSize += H2->CurrentSize;
    for (i = 0, j = 1; j <= H1->CurrentSize; i++, j*=2) {
        T1 = H1->TheTrees[i];
        T2 = H2->TheTrees[i]; // current trees
        // assign each digit to a tree:
        // | Carry | T2 | T1 |
        switch (4 * !!Carry + 2 * !!T2 + !!T1) {
            case 0:  // 000
            case 1:  // 001
                break;
            case 2:  // 010
                H1->TheTrees[i] = T2;
                H2->TheTrees[i] = NULL;
                break;
            case 4:  // 100
                H1->TheTrees[i] = Carry;
                Carry = NULL;
                break;
            case 3:  // 011
                Carry = CombineTrees(T1, T2);
                H1->TheTrees[i] = H2->TheTrees[i] = NULL;
                break;
            case 5:  // 101
                Carry = CombineTrees(T1, Carry);
                H1->TheTrees[i] = NULL;
                break;
            case 6:  // 110
                Carry = CombineTrees(T2, Carry);
                H2->TheTrees[i] = NULL;
                break;
            case 7:  // 111
                H1->TheTrees[i] = Carry;
                Carry = CombineTrees(T1, T2);
                H2->TheTrees[i] = NULL;
                break;
        } // end switch
    }  // end for-loop
    return H1;
}


ElementType DeleteMin(BinQueue H) {
    BinQueue DeletedQueue;
    Position DeletedTree, OldRoot;
    // the minimum item to be returned
    ElementType MinItem = Infinity;
    // MinTree is the index of the tree with the minimum item
    int i, j, MinTree;

    if (IsEmpty(H)) {
        PrintErrorMessage();
        return -Infinity;
    }

    // Step 1: find the minimum item
    // MaxTrees can be replaced by the actual number of roots
    for (i = 0; i < MaxTrees; i++) {
        if (H->TheTrees[i] && H->TheTrees[i]->Element < MinItem) {
            MinItem = H->TheTrees[i]->Element;
            MinTree = i;
        } // end if
    } // end for-i-loop
    DeletedTree = H->TheTrees[MinTree];

    // Step 2: remove the MinTree form H => H' 
    H->TheTrees[MinTree] = NULL;

    // Step 3.1: remove the root
    OldRoot = DeletedTree;
    DeletedTree = DeletedTree->LeftChild;
    free(OldRoot);
    // Step 3.2: create H
    DeletedQueue = Initialize();
    DeletedQueue->CurrentSize = (1 << MinTree) - 1; // 2^MinTree - 1
    for (j = MinTree - 1; j >= 0; j--) {
        DeletedQueue->TheTrees[j] = DeletedTree;
        DeletedTree = DeletedTree->NextSibling;
        DeletedQueue->TheTrees[j]->NextSibling = NULL; 
    } // end for-j-loop
    H->CurrentSize -= DeletedQueue->CurrentSize + 1;

    // Step 4: merge H' and H
    H = Merge(H, DeletedQueue);
    return MinItem;
}


BinQueue Insert(ElementType X, BinQueue H) {
    BinTree Carry; 
    int i; 

    H->CurrentSize++;
    Carry = malloc(sizeof(struct BinNode));
    Carry->Element = X;
    Carry->LeftChild = Carry->NextSibling = NULL;

    i = 0;
    while (H->TheTrees[i]) { 
        Carry = CombineTrees(Carry, H->TheTrees[i]); //combine two equal-sized trees
        H->TheTrees[i++] = NULL;
    }

    H->TheTrees[i] = Carry;
    return H;
}


BinTree Find(BinQueue H, ElementType X)
{
    BinTree T, result = NULL;
    int i, j; 

    for( i = 0, j = 1; j <= H->CurrentSize; i++, j *= 2) {  /* for each tree in H */
        T= H->TheTrees[i];
        if (X >= T->Element){  /* if need to search inside this tree */
            result = Recur_Find(T, X);
            if (result != NULL) return result;
        } 
    }
    return result;
}
BinTree Recur_Find(BinTree T, ElementType X)
{
    BinTree result = NULL;
    if (X == T->Element) 
        return T;
    if (T->LeftChild != NULL){
        result = Recur_Find(T->LeftChild, X);
        if (result != NULL) 
            return result;
    } 
    if (T->NextSibling != NULL)
        result = Recur_Find(T->NextSibling, X);
    return result;
}