数据结构与算法：配对堆

参考 配对堆(Pairing Heap)

#include 
#include 
using namespace std;

template <typename T>
class PairingHeap{
    //配对堆是斐波那契堆的简化版本,比一般的堆更快
    //多叉树,根节点存储最小值,孩子兄弟表示法
private:
    struct PairNode{
        T element;
        PairNode *leftChild;        //孩子节点
        PairNode *nextSibling;      //右兄弟节点
        PairNode *prev;             //如果此节点是第一个孩子节点,prev指向父节点,否则指向左兄弟节点
        PairNode(T d):element(d),leftChild(nullptr),nextSibling(nullptr),prev(nullptr){};
    };

    PairNode* root; //多叉树根节点

    PairNode* combineSiblings(PairNode *firstSibling){
        //把链表上的兄弟节点建成堆
        if (!firstSibling->nextSibling) return firstSibling;
        static vector<PairNode *> treeArray(5);
        int numSiblings = 0;
        //把兄弟节点放到vector里
        for (;firstSibling; numSiblings++){
            if (numSiblings == treeArray.size()) treeArray.resize(numSiblings * 2);
            treeArray[numSiblings] = firstSibling;
            firstSibling->prev->nextSibling = NULL;
            firstSibling = firstSibling->nextSibling;
        }
        if (numSiblings == treeArray.size()) treeArray.resize(numSiblings + 1);
        treeArray[numSiblings] = nullptr;
        int i = 0;
        //把兄弟节点两两合并
        for (; i + 1 < numSiblings; i += 2) compareAndLink(treeArray[i], treeArray[i + 1]);
        int j = i - 2;
        if (j == numSiblings - 3) compareAndLink (treeArray[j], treeArray[j + 2]);
        for (; j >= 2; j -= 2) compareAndLink(treeArray[j - 2], treeArray[j] );
        return treeArray[0];
    }
    void compareAndLink(PairNode * &first, PairNode *second){
        //将两个堆合并,节点大的挂到节点小的树下面,结果保存在first中
        if (!second) return;
        if (second->element < first->element){
            second->prev = first->prev;
            first->prev = second;
            first->nextSibling = second->leftChild;
            if (first->nextSibling) first->nextSibling->prev = first;
            second->leftChild = first;
            first = second;
        }
        else{
            second->prev = first;
            first->nextSibling = second->nextSibling;
            if (first->nextSibling) first->nextSibling->prev = first;
            second->nextSibling = first->leftChild;
            if (second->nextSibling) second->nextSibling->prev = second;
            first->leftChild = second;
        }
    }

public:

    PairingHeap():root(nullptr){};
    PairingHeap(PairingHeap & rhs):root(nullptr){*this=rhs;}
    bool isEmpty(){return root==nullptr;}
    void insert(T& x){
        PairNode* node=new PairNode(x);
        if (!root) root=node;
        else compareAndLink(root, node);
    }
    void merge(PairingHeap& rhs){
        compareAndLink(root,rhs.root);
        rhs.root=nullptr;
    }

    T& findMin(){return root->element;}
    void deleteMin(){
        PairNode *oldRoot = root;
        if (!root->leftChild) root=nullptr;
        else root = combineSiblings(root->leftChild); //把它的孩子节点变成一个堆
        delete oldRoot;
    }

    void decreaseKey(PairNode* p,int& newdata){
        //降低p的值
        if (p->element<newdata) return;
        p->element=newdata;
        //调整堆使其符合堆序
        if (p!=root){
            if (p->nextSibling) p->nextSibling->prev=p->prev;
            if (p->prev->leftChild == p) p->prev->leftChild = p->nextSibling;
            else{
                p->prev->nextSibling = p->nextSibling;
                p->nextSibling = NULL;
                compareAndLink(root, p);
            }
        }
    }
};


int main(){
    PairingHeap<int> p;
    for (int i=4;i<10;i++) p.insert(i);
    int x=p.findMin();
    cout << "最小节点是" << x << endl;
    p.deleteMin();
    cout << "删除最小节点" << endl;
    x=p.findMin();
    cout << "最小节点是" << x << endl;
    PairingHeap<int> rhs;
    for (int i=2;i<12;i++) rhs.insert(i);
    p.merge(rhs);
    cout << "合并堆" << endl;
    x=p.findMin();
    cout << "最小节点是" << x << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120