斐波那契堆这种高级数据结构在算法导论第三版中有非常详细的分析和介绍这里不回顾斐波那契堆的基础知识只给出个人的实现想了解斐波那契堆请参看算法导论#include iostream #include stack #include vector #include utility #include memory #include limits.h #include random using namespace std; //注意斐波那契堆具有最小堆序 template typename T struct FibonacciHeapNode //斐波那契堆节点 { T data; bool mark false; //级联标记 unsigned int degree 0; //节点的度 FibonacciHeapNode* parent nullptr; FibonacciHeapNode* first_child nullptr; FibonacciHeapNode* right_sibling nullptr; FibonacciHeapNode* left_sibling nullptr; FibonacciHeapNode(const T d) :data(d) {} FibonacciHeapNode(const FibonacciHeapNode be_copied) :data(be_copied.data), mark(be_copied.mark), degree(be_copied.degree) {} }; template typename T int Searchd(FibonacciHeapNodeT* ptr, int d) { if (d 1) { if (ptr-right_sibling nullptr) return 0; else return 2; } else { if (ptr-first_child ! nullptr) return 1; else { if (ptr-right_sibling ! nullptr) return 2; else return 0; } } } template typename T class FibonacciHeap { public: T getAndRemoveMinkey(); //返回并移除最小值 bool removeFirstNodeWithSpecificValue(const T key); //移除斐波那契堆中第一个具有给定值的节点 void insert(const T key); bool changeNodeValue(const T original_vaule, const T goal_value); //将斐波那契堆中第一个原始值改为目标值 T getMinValue() //获取最小值 { if (head_ptr_for_root_list nullptr) return min_value_for_type; else return min-data; } void merge(FibonacciHeap be_merged); //合并两个斐波那契堆 ~FibonacciHeap(); FibonacciHeap(const T min_value) :min_value_for_type(min_value) {} FibonacciHeap(const FibonacciHeap be_copied); void printHeap(); //以广义表形式打印斐波那契堆 bool isEmpty() { return num_of_node_in_heap 0; } private: FibonacciHeapNodeT* removeMinNode(); FibonacciHeapNodeT* unionSubHeap(FibonacciHeapNodeT* left, FibonacciHeapNodeT* right); //将斐波那契堆中两个子堆合并 void insertInRootList(FibonacciHeapNodeT* pre, FibonacciHeapNodeT* be_inserted); //根链表中插入新节点 void changeKey(FibonacciHeapNodeT* root, FibonacciHeapNodeT* node, const T key); void removeNode(FibonacciHeapNodeT* root, FibonacciHeapNodeT* node); bool adjustToRemainOrder(FibonacciHeapNodeT* parent, FibonacciHeapNodeT* node, bool increase_or_decrease); //子堆中的右兄弟链中某节点关键字增值或减值后重新维护右兄弟链各节点的大小顺序,返回true表示右兄弟链各节点父节点degree减小false相反 pairFibonacciHeapNodeT*, FibonacciHeapNodeT* searchFirstAppearKey(const T key); //搜索斐波那契堆中第一个具有给定关键码的节点 bool checkAndMaintainSibListOrderliness(FibonacciHeapNodeT* cur, FibonacciHeapNodeT* node, bool increase_or_decrease); //根据右兄弟链大小次序的维护结果即右兄弟链上各节点父节点度有无变化和级联标记判断是否需要级联剪切,true表明无需剪切,false表示需要 void destorySubHeap(FibonacciHeapNodeT* root); //销毁子堆 FibonacciHeapNodeT* copy_sub_heap(FibonacciHeapNodeT* be_copied_sub_heap); void reSetMin(); FibonacciHeapNodeT* min nullptr; //指向最小值指针 FibonacciHeapNodeT* head_ptr_for_root_list nullptr; //指向根链表首节点指针 unsigned long long num_of_node_in_heap 0; //斐波那契堆中节点数 unsigned long long size_of_root_list 0; //根链表大小 T min_value_for_type; //斐波那契堆中保存类型可能具有的最小值,该最小值不能为节点关键码 }; template typename T FibonacciHeapNodeT* FibonacciHeapT::copy_sub_heap(FibonacciHeapNodeT* be_copied_sub_heap) { FibonacciHeapNodeT* copy_root new FibonacciHeapNodeT(*be_copied_sub_heap); if (be_copied_sub_heap-first_child ! nullptr) { FibonacciHeapNodeT* run be_copied_sub_heap-first_child; copy_root-first_child copy_sub_heap(run); FibonacciHeapNodeT* head copy_root-first_child; head-parent copy_root; head-right_sibling head; head-left_sibling head; run run-right_sibling; while (run ! be_copied_sub_heap-first_child) { FibonacciHeapNodeT* t copy_sub_heap(run); t-parent copy_root; t-left_sibling head-left_sibling; head-left_sibling-right_sibling t; t-right_sibling head; head-left_sibling t; run run-right_sibling; } } return copy_root; } template typename T FibonacciHeapT::FibonacciHeap(const FibonacciHeap be_copied) { num_of_node_in_heap be_copied.num_of_node_in_heap; size_of_root_list be_copied.size_of_root_list; min_value_for_type be_copied.min_value_for_type; if (be_copied.head_ptr_for_root_list ! nullptr) { head_ptr_for_root_list copy_sub_heap(be_copied.head_ptr_for_root_list); head_ptr_for_root_list-left_sibling head_ptr_for_root_list; head_ptr_for_root_list-right_sibling head_ptr_for_root_list; if (be_copied.head_ptr_for_root_list be_copied.min) { min head_ptr_for_root_list; } FibonacciHeapNodeT* run be_copied.head_ptr_for_root_list-right_sibling; while (run ! be_copied.head_ptr_for_root_list) { FibonacciHeapNodeT* cur copy_sub_heap(run); cur-left_sibling head_ptr_for_root_list-left_sibling; head_ptr_for_root_list-left_sibling-right_sibling cur; cur-right_sibling head_ptr_for_root_list; head_ptr_for_root_list-left_sibling cur; if (min nullptr run be_copied.min) { min cur; } run run-right_sibling; } } } template typename T void FibonacciHeapT::destorySubHeap(FibonacciHeapNodeT* root) { if (root-first_child ! nullptr) { FibonacciHeapNodeT* cur root-first_child; while (cur-right_sibling ! cur) { FibonacciHeapNodeT* temp cur-right_sibling; cur-right_sibling temp-right_sibling; destorySubHeap(temp); } destorySubHeap(cur); } delete root; } template typename T FibonacciHeapT::~FibonacciHeap() { if (head_ptr_for_root_list nullptr) { return; } while (head_ptr_for_root_list-right_sibling ! head_ptr_for_root_list) { FibonacciHeapNodeT* cur head_ptr_for_root_list-right_sibling; head_ptr_for_root_list-right_sibling cur-right_sibling; destorySubHeap(cur); } destorySubHeap(head_ptr_for_root_list); } templatetypename T bool FibonacciHeapT::changeNodeValue(const T original_vaule, const T goal_value) { if (original_vaule goal_value) { return false; } pairFibonacciHeapNodeT*, FibonacciHeapNodeT* temp searchFirstAppearKey(original_vaule); if (temp.first nullptr) { return false; } changeKey(temp.first, temp.second, goal_value); return true; } template typename T T FibonacciHeapT::getAndRemoveMinkey() { shared_ptrFibonacciHeapNodeT t(removeMinNode()); if (t nullptr) { return min_value_for_type; } else { return t-data; } } template typename T void FibonacciHeapT::merge(FibonacciHeapT be_merged) { if (head_ptr_for_root_list nullptr) { min be_merged.min; head_ptr_for_root_list be_merged.head_ptr_for_root_list; num_of_node_in_heap be_merged.num_of_node_in_heap; size_of_root_list be_merged.size_of_root_list; be_merged.min nullptr; be_merged.head_ptr_for_root_list nullptr; be_merged.num_of_node_in_heap 0; be_merged.size_of_root_list 0; } else if (be_merged.head_ptr_for_root_list ! nullptr) { FibonacciHeapNodeT* pre head_ptr_for_root_list-left_sibling; pre-right_sibling be_merged.head_ptr_for_root_list; FibonacciHeapNodeT* last be_merged.head_ptr_for_root_list-left_sibling; be_merged.head_ptr_for_root_list-left_sibling pre; last-right_sibling head_ptr_for_root_list; head_ptr_for_root_list-left_sibling last; if (min-data be_merged.min-data) { min be_merged.min; } num_of_node_in_heap be_merged.num_of_node_in_heap; size_of_root_list be_merged.size_of_root_list; be_merged.min nullptr; be_merged.head_ptr_for_root_list nullptr; be_merged.num_of_node_in_heap 0; be_merged.size_of_root_list 0; } } template typename T void FibonacciHeapT::insert(const T key) { FibonacciHeapNodeT* pre nullptr; if (head_ptr_for_root_list ! nullptr) { pre head_ptr_for_root_list-left_sibling; } FibonacciHeapNodeT* be_inserted new FibonacciHeapNodeT(key); if (head_ptr_for_root_list nullptr || min-data be_inserted-data) { min be_inserted; } insertInRootList(pre, be_inserted); num_of_node_in_heap; size_of_root_list; } template typename T void FibonacciHeapT::printHeap() { if (head_ptr_for_root_list nullptr) { cout NULL; cout endl; return; } size_t num 0; for (FibonacciHeapNodeT* run head_ptr_for_root_list; ; run run-right_sibling) { cout 第 num 棵子堆的广义表形式:; stackFibonacciHeapNodeT* work_stack; FibonacciHeapNodeT* ptr run; FibonacciHeapNodeT* root_right_bro run-right_sibling; run-right_sibling nullptr; int d 0; while (true) //输出子女右兄弟链二叉树对应广义表形式 { if (Searchd(ptr, d) 0) { if (ptr run) { if (d 0) { cout ( ptr-data );; } break; } else { if (d 0) { cout ptr-data; } cout ); ptr work_stack.top(); d 1; work_stack.pop(); } } else { if (d 0) { if (ptr-first_child ! nullptr) { cout ptr-data (; work_stack.push(ptr); ptr ptr-first_child; } else { cout ptr-data; cout ,; ptr ptr-right_sibling; } } else { cout ,; ptr ptr-right_sibling; d 0; } } } run-right_sibling root_right_bro; cout endl; cout endl; if (run-right_sibling head_ptr_for_root_list) { return; } } } template typename T pairFibonacciHeapNodeT*, FibonacciHeapNodeT* FibonacciHeapT::searchFirstAppearKey(const T key) { if (head_ptr_for_root_list nullptr) { return { nullptr, nullptr }; } for (FibonacciHeapNodeT* run head_ptr_for_root_list; ; run run-right_sibling) { int d 0; stackFibonacciHeapNodeT* work_stack; FibonacciHeapNodeT* ptr run; FibonacciHeapNodeT* root_right_bro run-right_sibling; run-right_sibling nullptr; while (true) { if (Searchd(ptr, d) 0) { break; } else { FibonacciHeapNodeT* interval nullptr; if (d 0) { if (key ptr-data) { if (work_stack.empty() true) { break; } ptr work_stack.top(); d 1; work_stack.pop(); continue; } else if (key ptr-data) { break; } } if (d 0 ptr-first_child ! nullptr) { work_stack.push(ptr); ptr ptr-first_child; } else { if (ptr-right_sibling work_stack.top()-first_child) { ptr work_stack.top(); d 1; work_stack.pop(); continue; } else { ptr ptr-right_sibling; d 0; } } } } run-right_sibling root_right_bro; if (ptr-data key) { return { run, ptr }; } if (run-right_sibling head_ptr_for_root_list) { return { nullptr, nullptr }; } } } template typename T bool FibonacciHeapT::removeFirstNodeWithSpecificValue(const T key) { pairFibonacciHeapNodeT*, FibonacciHeapNodeT* temp searchFirstAppearKey(key); if (temp.first nullptr) { return false; } removeNode(temp.first, temp.second); return true; } template typename T void departRightHeap(FibonacciHeapNodeT* right_sub_heap) //把right_sub_heap从右兄弟链中分离 { FibonacciHeapNodeT* p right_sub_heap-parent; if (p ! nullptr) { right_sub_heap-left_sibling-right_sibling right_sub_heap-right_sibling; right_sub_heap-right_sibling-left_sibling right_sub_heap-left_sibling; if (p-first_child right_sub_heap) { if (right_sub_heap-right_sibling right_sub_heap) { p-first_child nullptr; } else { p-first_child right_sub_heap-right_sibling; } } } } template typename T void insertNodeInRightSibLink(FibonacciHeapNodeT* post, FibonacciHeapNodeT* be_inserted_root) { be_inserted_root-left_sibling post-left_sibling; post-left_sibling-right_sibling be_inserted_root; post-left_sibling be_inserted_root; be_inserted_root-right_sibling post; } template typename T void insertInEmptyLink(FibonacciHeapNodeT* run, FibonacciHeapNodeT* cur) { run-first_child cur; cur-left_sibling cur; cur-right_sibling cur; } template typename T FibonacciHeapNodeT* FibonacciHeapT::unionSubHeap(FibonacciHeapNodeT* left, FibonacciHeapNodeT* right) { stackFibonacciHeapNodeT* work_stack; FibonacciHeapNodeT* left_sub_heap left; FibonacciHeapNodeT* right_sub_heap right; FibonacciHeapNodeT* cur nullptr; bool first_cycle true; while (true) //合并子堆对根节点关键码值较大子堆在较小子堆根节点右兄弟链寻找插入位置,找到位置则插入较大子堆根节点否则说明右兄弟链中发现与较大子堆根节点关键码重复的节点此时递归合并该节点代表子堆和较大子堆 { FibonacciHeapNodeT* run left_sub_heap-first_child; if (run ! nullptr) { if (first_cycle) { first_cycle false; if (left_sub_heap-data right_sub_heap-data) { do { if (run-data right_sub_heap-data) { run run-right_sibling; } else { break; } } while (run ! left_sub_heap-first_child); } } } if (run ! left_sub_heap-first_child || run ! nullptr right_sub_heap-data run-data) { if (run-data ! right_sub_heap-data) { departRightHeap(right_sub_heap); insertNodeInRightSibLink(run, right_sub_heap); if (run left_sub_heap-first_child) { left_sub_heap-first_child right_sub_heap; } } else { work_stack.push(left_sub_heap); if (run-degree right_sub_heap-degree) left_sub_heap run; else { left_sub_heap right_sub_heap; right_sub_heap run; } continue; } } else { departRightHeap(right_sub_heap); if (run nullptr) { insertInEmptyLink(left_sub_heap, right_sub_heap); } else { insertNodeInRightSibLink(run, right_sub_heap); } } right_sub_heap-parent left_sub_heap; right_sub_heap-mark false; left_sub_heap-degree; left_sub_heap-mark false; cur left_sub_heap; break; } while (work_stack.empty() false) //自底向上重新链接合并结果至父节点 { if (cur-parent ! work_stack.top()) { FibonacciHeapNodeT* run work_stack.top(); departRightHeap(cur); if (run-first_child nullptr) { insertInEmptyLink(run, cur); } else { insertNodeInRightSibLink(run-first_child, cur); run-first_child cur; } cur-parent run; cur-mark false; } cur work_stack.top(); work_stack.pop(); } return cur; } template typename T void insertAfter(FibonacciHeapNodeT* node, FibonacciHeapNodeT* run) { node-right_sibling run-right_sibling; run-right_sibling node; node-right_sibling-left_sibling node; node-left_sibling run; } template typename T void FibonacciHeapT::insertInRootList(FibonacciHeapNodeT* pre, FibonacciHeapNodeT* be_inserted) { if (pre nullptr) { pre head_ptr_for_root_list be_inserted; be_inserted-right_sibling be_inserted; be_inserted-left_sibling be_inserted; } else { insertAfter(be_inserted, pre); } } template typename T bool FibonacciHeapT::adjustToRemainOrder(FibonacciHeapNodeT* parent, FibonacciHeapNodeT* node, bool increase_or_decrease) //increase_or_decrease表示node值增加否则减小 { FibonacciHeapNodeT* run nullptr;//node值已改变所以需要在node所在右兄弟链上查找值等于node的节点如果找到需要合并该节点和node节点代表的子堆 if (increase_or_decrease) { if (node-right_sibling parent-first_child) { return false; } run node-right_sibling; do { if (run-data node-data) { run run-right_sibling; } else { break; } } while (run ! parent-first_child); } else { if (node parent-first_child) { return false; } run node-left_sibling; do { if (run-data node-data) { run run-left_sibling; } else { break; } } while (run ! parent-first_child-left_sibling); } bool result; if (result (increase_or_decrease ? run ! parent-first_child : run ! parent-first_child-left_sibling)) { if (node-data run-data) { if (run-degree node-degree) { departRightHeap(node); unionSubHeap(run, node); } else { if (node-right_sibling ! run) { departRightHeap(node); insertNodeInRightSibLink(run, node); } departRightHeap(run); unionSubHeap(node, run); } --parent-degree; return true; } else { if (increase_or_decrease ? node-right_sibling run : node-left_sibling run) { return false; } } } else { if (node run) { if (increase_or_decrease) { parent-first_child node-right_sibling; return false; } parent-first_child node; return false; } } departRightHeap(node); if (increase_or_decrease) { insertNodeInRightSibLink(run, node); } else { insertAfter(node, run); if (result false) parent-first_child node; } return false; } template typename T bool FibonacciHeapT::checkAndMaintainSibListOrderliness(FibonacciHeapNodeT* cur, FibonacciHeapNodeT* node, bool increase_or_decrease) { if (node-parent ! nullptr) { if (!adjustToRemainOrder(node-parent, node, increase_or_decrease)) { return true; } else { if (node-parent-mark true) { cur node-parent; return false; } else { node-parent-mark true; return true; } } } else { return true; } } template typename T void FibonacciHeapT::reSetMin() { FibonacciHeapNodeT* tra head_ptr_for_root_list-right_sibling; min head_ptr_for_root_list; for (; tra ! head_ptr_for_root_list; tra tra-right_sibling) { if (min-data tra-data) { min tra; } } } template typename T void FibonacciHeapT::changeKey(FibonacciHeapNodeT* root, FibonacciHeapNodeT* node, const T key) { if (key node-data) { return; } FibonacciHeapNodeT* cur nullptr; FibonacciHeapNodeT* pre root; if (key node-data) //如果node的值增加,则需要将node的子女节点中不满足堆序的节点代表的子堆剪切至根链表,然后判断node是否需要级联切断 { node-data key; bool compare_to_update_min false; if (node-parent nullptr node min) { compare_to_update_min true; reSetMin(); } if (node-first_child nullptr) { if (checkAndMaintainSibListOrderliness(cur, node, true)) { return; } } else { FibonacciHeapNodeT* run node-first_child; unsigned long long num_of_lossing_node 0; bool finish false; while (finish false) { if (run-data node-data) { node-first_child run; break; } run-right_sibling-left_sibling run-left_sibling; run-left_sibling-right_sibling run-right_sibling; --node-degree; num_of_lossing_node; run-parent nullptr; FibonacciHeapNodeT* temp nullptr; if (run-right_sibling run) { finish true; } else { temp run-right_sibling; } insertInRootList(pre, run); run-mark false; size_of_root_list; if (compare_to_update_min min-data run-data) { min run; } run temp; } if (node-degree 0) { node-first_child nullptr; } if (finish false) { if (node-mark false) { if (num_of_lossing_node 0 || num_of_lossing_node 1) { if (num_of_lossing_node 1) { node-mark true; } if (checkAndMaintainSibListOrderliness(cur, node, true)) { return; } } else { cur node; } } else { if (num_of_lossing_node 0) { if (checkAndMaintainSibListOrderliness(cur, node, true)) { return; } } else { cur node; } } } else { if (node-mark false num_of_lossing_node 1) { node-mark true; if (checkAndMaintainSibListOrderliness(cur, node, true)) { return; } } else { cur node; } } } } else { node-data key; if (node-parent nullptr) { if (min-data node-data) { min node; } return; } if (node-parent-data node-data) //node值减小则应判断node与其父节点是否满足最小堆序,若满足则调整node所在右兄弟链上节点的大小次序并判断node的父节点是否需要级联切断 若不满足则node代表子堆应当被剪切至根链表 { if (checkAndMaintainSibListOrderliness(cur, node, false)) { return; } } else { cur node; } } while (true) //从当前节点cur开始向上进行级联切断操作 { if (cur-parent nullptr) { cur-mark false; break; } departRightHeap(cur); insertInRootList(pre, cur); cur-mark false; pre pre-right_sibling; node cur-parent; cur-parent nullptr; if (cur-data min-data) { min cur; } size_of_root_list; --node-degree; if (node-mark false) { cur-mark true; break; } cur node; } } template typename T FibonacciHeapNodeT* FibonacciHeapT::removeMinNode() //该操作的详细说明参见算法导论 { if (head_ptr_for_root_list nullptr) { return nullptr; } FibonacciHeapNodeT* pre min-left_sibling; FibonacciHeapNodeT* original_min min; if (pre min) { pre nullptr; head_ptr_for_root_list nullptr; } else { pre-right_sibling min-right_sibling; min-right_sibling-left_sibling pre; } FibonacciHeapNodeT* run min-first_child; if (run nullptr) { min-left_sibling min-right_sibling nullptr; if (head_ptr_for_root_list min) { head_ptr_for_root_list pre-right_sibling; } if (head_ptr_for_root_list ! nullptr) { reSetMin(); } else { min nullptr; --num_of_node_in_heap; --size_of_root_list; return original_min; } } else { FibonacciHeapNodeT* tail_or_head pre; while (true) { run-right_sibling-left_sibling run-left_sibling; run-left_sibling-right_sibling run-right_sibling; run-parent nullptr; run-mark false; if (run-right_sibling run) { insertInRootList(pre, run); break; } FibonacciHeapNodeT* temp run-right_sibling; insertInRootList(pre, run); run temp; pre pre-right_sibling; } min-first_child nullptr; min-left_sibling nullptr; min-right_sibling nullptr; if (head_ptr_for_root_list nullptr) { head_ptr_for_root_list pre; } else if (head_ptr_for_root_list min) { head_ptr_for_root_list tail_or_head-right_sibling; } } vectorFibonacciHeapNodeT* be_merged_sub_heap; bool finish false; while (finish false) //合并根链表上根节点度数相等的子堆 { head_ptr_for_root_list-right_sibling-left_sibling head_ptr_for_root_list-left_sibling; head_ptr_for_root_list-left_sibling-right_sibling head_ptr_for_root_list-right_sibling; FibonacciHeapNodeT* temp head_ptr_for_root_list; if (temp-right_sibling temp) { finish true; head_ptr_for_root_list nullptr; } else { head_ptr_for_root_list head_ptr_for_root_list-right_sibling; } temp-left_sibling temp-right_sibling nullptr; while (true) { if (be_merged_sub_heap.empty() true || be_merged_sub_heap.size() temp-degree 1) { be_merged_sub_heap.resize(temp-degree 1, nullptr); be_merged_sub_heap[temp-degree] temp; break; } if (be_merged_sub_heap[temp-degree] nullptr) { be_merged_sub_heap[temp-degree] temp; break; } unsigned int pre_degree temp-degree; if (be_merged_sub_heap[temp-degree]-data temp-data) { temp unionSubHeap(be_merged_sub_heap[temp-degree], temp); } else { temp unionSubHeap(temp, be_merged_sub_heap[temp-degree]); } if (temp-degree pre_degree) { be_merged_sub_heap[pre_degree] temp; break; } be_merged_sub_heap[pre_degree] nullptr; if (be_merged_sub_heap.size() temp-degree 1) { be_merged_sub_heap.resize(temp-degree 1, nullptr); } if (be_merged_sub_heap[temp-degree] nullptr) { be_merged_sub_heap[temp-degree] temp; break; } } } min nullptr; pre nullptr; size_of_root_list 0; for (size_t i 0; i be_merged_sub_heap.size(); i) //合并后还原根链表 { if (be_merged_sub_heap[i] ! nullptr) { size_of_root_list; insertInRootList(pre, be_merged_sub_heap[i]); pre pre-right_sibling; if (min nullptr || min-data pre-data) { min pre; } } } --num_of_node_in_heap; return original_min; } template typename T void FibonacciHeapT::removeNode(FibonacciHeapNodeT* root, FibonacciHeapNodeT* node) { changeKey(root, node, min_value_for_type); removeMinNode(); } int main() { const int N 5000; const int M 2000; FibonacciHeapint obj(INT_MIN); FibonacciHeapint obj2(INT_MIN); vectorint input(N); vectorint input2(M); int k 0; for (int i 1; i 100; i) { for (int j 1; j 50; j) { input[k] j; } } k 0; for (int i 1; i 100; i) { for (int j 20; j 0; --j) { input2[k] j; } } shuffle(input.begin(), input.end(), default_random_engine()); shuffle(input2.begin(), input2.end(), default_random_engine()); /*/for (const int i : input) { cout 插入关键码 i endl; cout endl; obj.insert(i); cout 当前最小值 obj.getMinValue() endl; cout 斐波那契堆打印结果 endl; //obj.printHeap(); cout endl; }*/ for (const int i : input) { cout 插入关键码 i endl; cout endl; obj.insert(i); } for (const int i : input2) { cout 插入关键码 i endl; cout endl; obj2.insert(i); } /*cout 删除关键码 9 endl; cout endl; if (obj.removeFirstNodeWithSpecificValue(9)) { cout 删除成功 endl; cout 当前最小值 obj.getMinValue() endl; cout 斐波那契堆打印结果 endl; obj.printHeap(); } else { cout 删除失败 endl; }*/ int t obj.getAndRemoveMinkey(); cout 移除最小值 endl; if (t INT_MIN) { cout 移除失败 endl; exit(-1); } else { cout 移除最小值 t 成功 endl; cout 当前最小值 obj.getMinValue() endl; //obj.printHeap(); } t obj2.getAndRemoveMinkey(); cout 移除最小值 endl; if (t INT_MIN) { cout 移除失败 endl; exit(-1); } else { cout 移除最小值 t 成功 endl; cout 当前最小值 obj2.getMinValue() endl; //obj.printHeap(); } obj.merge(obj2); while (true) { int t obj.getAndRemoveMinkey(); cout 移除最小值 endl; if (t INT_MIN) { cout 移除失败 endl; break; } else { cout 移除最小值 t 成功 endl; cout 当前最小值 obj.getMinValue() endl; //obj.printHeap(); } } /*FibonacciHeapint obj2(obj); for (size_t i 1; i input.size(); i) { while (true) { if (!obj2.changeNodeValue(input[i], 25)) break; else { cout 将值 input[i] 更改为25 endl; //obj.printHeap(); } } } cout 当前最小值 obj2.getMinValue() endl; /*for (const int i : input) { cout 删除关键码 i endl; cout endl; if (obj.removeFirstNodeWithSpecificValue(i)) { cout 删除成功 endl; cout 当前最小值 obj.getMinValue() endl; cout 斐波那契堆打印结果 endl; //obj.printHeap(); } else { cout 删除失败 endl; exit(-1); } } if (obj2.isEmpty()) { cout 当前堆为空 endl; }*/ return 0; }