首页 > 代码库 > 二项堆
二项堆
算法来自算法导论第19章
设计类:二项堆这个东西的逻辑是这样的:节点-二项树-二项堆,so刚开始时想设计三个类,BNode BTree BHeap
后来发现BTree是完全没有必要的。。BTree的功能完全可以写在BNode里(Link),所以最后就只设计了两个类。
拖这么久是因为有个指针没指对。。算导里关于Union的部分少了修改next_x->Sibling->Parent的部分,就是这部分坑了我两星期。。反复的debug,最后终于发现是Parent出错了,然后,,就没有然后了。。如此简单的bug
顺便把难看的代码附上
1 //Binomial Heap 2 #include <iostream> 3 #include <vector> 4 #include <string> 5 #include <my.cpp> 6 7 class BNode:public my::total_ordering<BNode>{ 8 friend std::ostream& operator<<(std::ostream&,const BNode*); 9 friend class BHeap; 10 11 public: 12 explicit BNode(int key,BNode *parent=nullptr,BNode *child=nullptr,BNode *sibling=nullptr,int degree=0): 13 Key(key),Parent(parent),Child(child),Sibling(sibling),Degree(degree) {} 14 virtual bool operator==(const BNode& n) const override{ 15 return Key == n.Key; 16 } 17 virtual bool operator<(const BNode& n) const override{ 18 return Key < n.Key; 19 } 20 static void exchange(BNode *n1,BNode *n2){ 21 std::swap(n1->Key,n2->Key); 22 } 23 24 protected: 25 static BNode* Link(BNode *left,BNode *right){ 26 left->Parent = right; 27 left->Sibling = right->Child; 28 right->Child = left; 29 ++right->Degree; 30 return right; 31 } 32 private: 33 int Key; 34 BNode *Parent,*Child,*Sibling; 35 int Degree; 36 37 }; 38 inline std::ostream& operator<<(std::ostream& os,const BNode *n){ 39 if (not n) os << "NULLPTR"; 40 else os << n->Key; 41 return os; 42 } 43 44 class KeyGreaterError{ 45 friend std::ostream& operator<<(std::ostream&,const KeyGreaterError&); 46 47 public: 48 explicit KeyGreaterError(const std::string& str):msg(str) {} 49 explicit KeyGreaterError(const char* str):msg(std::string(str)) {} 50 private: 51 std::string msg; 52 }; 53 inline std::ostream& operator<<(std::ostream& os,const KeyGreaterError& err){ 54 os << err.msg; 55 return os; 56 } 57 58 class BHeap{ 59 friend std::ostream& operator<<(std::ostream&,const BHeap*); 60 61 public: 62 explicit BHeap(BNode *head=nullptr):Head(head) {} 63 explicit operator bool() const{ 64 if (Head) return true; 65 else return false; 66 } 67 BNode* Find_Minimum() const{ 68 BNode *root(Head),*MIN(root); 69 while (root){ 70 if (root < MIN) MIN = root; 71 root = root->Sibling; 72 } 73 return MIN; 74 } 75 void Insert(int x){ 76 BNode *n(new BNode (x)); 77 Insert(n); 78 } 79 BNode* Extract_Min(){ 80 BNode* MIN(Find_Minimum()); 81 if (not MIN) return nullptr; 82 if ((not MIN->Parent) and (not MIN->Sibling)){ 83 Head = nullptr; 84 }else if (not MIN->Parent){ 85 Head = MIN->Sibling; 86 MIN->Sibling->Parent = nullptr; 87 }else if (MIN->Sibling){ 88 MIN->Parent->Sibling = MIN->Sibling; 89 MIN->Sibling->Parent = MIN->Parent; 90 }else{ 91 MIN->Parent->Sibling = nullptr; 92 } 93 BHeap *heap1(new BHeap (this->Head)); 94 BNode *child(MIN->Child); 95 if (child){ 96 BNode *next(child->Sibling),*next_tmp(nullptr); 97 child->Sibling = nullptr; 98 child->Parent = nullptr; 99 while (next){ 100 child->Parent = next; 101 next_tmp = next->Sibling; 102 next->Sibling = child; 103 child = next; 104 next = next_tmp; 105 } 106 } 107 if (child) child->Parent = nullptr; 108 BHeap *heap2(new BHeap (child)); 109 BHeap *union_heap(Union(heap1,heap2)); 110 Head = union_heap->Head; 111 delete union_heap; 112 return MIN; 113 } 114 void Delete(BNode *n){ 115 Decrease_Key(n,-1); 116 delete Extract_Min(); 117 } 118 void Collect_Nodes(){ 119 BNode *MIN = Extract_Min(); 120 while (MIN){ 121 delete MIN; 122 MIN = Extract_Min(); 123 } 124 } 125 126 protected: 127 BNode *Head; 128 129 static BNode* Merge(BHeap *H1,BHeap *H2){ 130 BNode *head1(H1->Head),*head2(H2->Head),*head(nullptr),*now(nullptr); 131 if (head1 and head2){ 132 if (head1->Degree > head2->Degree){ 133 head = head2; 134 head2 = head2->Sibling; 135 }else{ 136 head = head1; 137 head1 = head1->Sibling; 138 } 139 }else if (head1){ 140 head = head1; 141 head1 = head1->Sibling; 142 }else if (head2){ 143 head = head2; 144 head2 = head2->Sibling; 145 }else return nullptr; 146 now = head; 147 while (head1 and head2){ 148 if (head1->Degree > head2->Degree){ 149 now->Sibling = head2; 150 head2->Parent = now; 151 now = head2; 152 head2 = head2->Sibling; 153 }else{ 154 now->Sibling = head1; 155 head1->Parent = now; 156 now = head1; 157 head1 = head1->Sibling; 158 } 159 } 160 while (head1){ 161 now->Sibling = head1; 162 head1->Parent = now; 163 now = head1; 164 head1 = head1->Sibling; 165 } 166 while (head2){ 167 now->Sibling = head2; 168 head2->Parent = now; 169 now = head2; 170 head2 = head2->Sibling; 171 } 172 return head; 173 } 174 static BHeap* Union(BHeap *H1,BHeap *H2){ 175 BHeap *heap(new BHeap (Merge(H1,H2))); 176 delete H1; 177 delete H2; 178 if (not heap->Head) return heap; 179 BNode *x(heap->Head),*next_x(x->Sibling),*prev_x(nullptr); 180 while (next_x){ 181 if ((x->Degree != next_x->Degree) or ((next_x->Sibling) and (next_x->Sibling->Degree == x->Degree))){ 182 prev_x = x; 183 x = next_x; 184 }else if (x->Key <= next_x->Key){ 185 x->Sibling = next_x->Sibling; 186 if (x->Sibling) x->Sibling->Parent = x; 187 BNode::Link(next_x,x); 188 }else{ 189 if (not prev_x) heap->Head = next_x; 190 else prev_x->Sibling = next_x; 191 next_x->Parent = prev_x; 192 BNode::Link(x,next_x); 193 x = next_x; 194 } 195 next_x = x->Sibling; 196 } 197 return heap; 198 } 199 void Insert(BNode *x){ 200 BHeap *heap_orig(new BHeap (this->Head)),*heap_node(new BHeap (x)); 201 BHeap *union_heap (Union(heap_orig,heap_node)); 202 Head = union_heap->Head; 203 delete union_heap; 204 } 205 void Decrease_Key(BNode *node,int key){ 206 if (key > node->Key) throw KeyGreaterError("orig key is "+std::to_string(node->Key)+" but "+std::to_string(key)+" given."); 207 node->Key = key; 208 BNode *node_this(node),*node_parent(node->Parent); 209 while ((node_parent) and (node_this->Key < node_parent->Key) and (node_this->Degree < node_parent->Degree)){ 210 BNode::exchange(node_this,node_parent); 211 node_this = node_parent; 212 node_parent = node_parent->Parent; 213 } 214 } 215 }; 216 inline std::ostream& operator<<(std::ostream& os,const BHeap *h){ 217 os << h->Head; 218 return os; 219 } 220 221 int main(){ 222 BHeap H; 223 for (int i=1;i<=10;++i) H.Insert(i); 224 std::cout << &H; 225 H.Collect_Nodes(); 226 std::cout << " " << &H; 227 }
1 #include <iostream> 2 #include <vector> 3 4 namespace my{ 5 template<typename T> 6 class total_ordering{ 7 public: 8 virtual bool operator==(const T&) const =0; 9 virtual bool operator<(const T&) const =0; 10 virtual bool operator!=(const T& obj) const{ 11 return not (*this == obj); 12 } 13 virtual bool operator<=(const T& obj) const{ 14 return ((*this == obj) or (*this < obj)); 15 } 16 virtual bool operator>(const T& obj) const{ 17 return not (*this <= obj); 18 } 19 virtual bool operator>=(const T& obj) const{ 20 return not (*this < obj); 21 } 22 virtual ~total_ordering() {}; 23 }; 24 25 template <typename P> 26 class QSort{ 27 //typedef double P; 28 typedef std::vector<P> PVec; 29 30 public: 31 QSort(const PVec& x):orig(x) {sort();} 32 PVec getans(){ 33 return orig; 34 } 35 36 private: 37 PVec orig; 38 void sort(){ 39 subsort(this->orig.begin(),this->orig.end()); 40 } 41 void subsort(typename PVec::iterator begin_iter,typename PVec::iterator end_iter){ 42 if (end_iter - begin_iter <= 1) return; 43 P key = *begin_iter; 44 typename PVec::iterator beg=begin_iter,end=end_iter; 45 while (begin_iter != end_iter){ 46 while (begin_iter != end_iter){ 47 if (*--end_iter >= key) continue; 48 swap(begin_iter,end_iter); 49 break; 50 } 51 while (begin_iter != end_iter){ 52 if (*++begin_iter <= key) continue; 53 swap(begin_iter,end_iter); 54 break; 55 } 56 } 57 subsort(beg,begin_iter); 58 subsort(begin_iter+1,end); 59 } 60 static void swap(typename PVec::iterator &a,typename PVec::iterator &b){ 61 if (*a == *b) return; 62 std::swap(*a,*b); 63 } 64 }; 65 66 }
二项堆
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。