左式堆是满足如下性质的二叉树(最小堆序):要么为空树要么根节点的左右子树均为左式堆且根节点的关键码值小于等于左右子树所有节点的关键码值此外左子树代表的左式堆的零路径长度大于等于右子树代表的左式堆的零路径长度一个左式堆的零路径长度定义为:左式堆的根节点到达左式堆中任意至少有一个子女节点为空的节点的路径长度的最小值如果左式堆为空其零路径长度规定为-1,如果左式堆根节点至少有一个子女节点为空则左式堆的零路径长度为0显然由零路径长度的定义当左式堆不为空时它的零路径长度为根节点的左右子树代表的左式堆的零路径长度中的较小值加1左式堆的核心操作为合并操作插入删除操作均为合并操作的特殊情形。合并时如果待合并的左式堆L1,L2有一个为空则直接返回另一个左式堆否则若L1根节点关键码小于等于L2根节点则递归合并L2和L1根节点右子树若不然则递归合并L1和L2右子树合并操作由递归描述但实际实现时采用非递归方法。此外左式堆还支持改变节点关键码值的操作如果改变后堆序仍然满足则操作结束否则若节点值增大则修改节点零路径长度若零路径长度改变(减小)则沿父节点链向根节点调整直到恢复左式堆性质否则不用调整然后将节点值改变的节点的左右子树和原左式堆在该节点的左右子树被剪除后形成的新的左式堆合并。若节点值减小则分离出以该节点为根的子树并沿该节点的父节点链向根节点调整直到恢复左式堆性质然后将分离出的子树和调整后的原左式堆合并。实现左式堆的C代码如下#include iostream #include stack #include algorithm #include vector #include memory #include random using namespace std; //实现的左式堆默认为最小堆序 template typename T struct LeftIstHeapNode //左式堆节点定义 { T* data_field; //数据域 LeftIstHeapNode* left_node_ptr nullptr; //左子女指针 LeftIstHeapNode* right_node_ptr nullptr; //右子女指针 long long zero_road_length 0; //左式堆节点的零路径长度 LeftIstHeapNode(T* d) :data_field(d) {} ~LeftIstHeapNode() { delete data_field; } }; template typename T struct StackNodeInfo { LeftIstHeapNodeT* p; int direction; StackNodeInfo(LeftIstHeapNodeT* p, int d) :p(p), direction(d) {} }; struct JudgeResult { bool isLeftIstHeap true; long long zero_road_length -1; }; template typename T class LeftIstHeap { public: bool empty() { return root nullptr; } //判断左式堆是否为空 bool satisfyLeftIstHeapNature() { return isLeftIstHeap(root).isLeftIstHeap; } T* getMinValue() { return new T(*(root-data_field)); } //获取左式堆中最小节点值 void insert(T* data); //左式堆中插入数据 T* removeMinValue(); //移除左式堆总最小值 bool changeNodeVauleForNodeHaveSepecificValue(T* original_node_value, T* change_value); //改变左式堆中节点被改变的节点是搜索过程中遇到的第一个具有给定节点值的节点 LeftIstHeap() default; ~LeftIstHeap() { destoryHeap(root); } private: void merge(LeftIstHeapNodeT* root); //合并左式堆 void changeNodeValue(LeftIstHeapNodeT* bechanged, T* change_value, stackStackNodeInfoT work_stack); //改变左式堆中指定节点的节点值 static JudgeResult isLeftIstHeap(LeftIstHeapNodeT* root); void destoryHeap(LeftIstHeapNodeT* root) { if (root ! nullptr) { destoryHeap(root-left_node_ptr); destoryHeap(root-right_node_ptr); delete root; } } LeftIstHeapNodeT* root nullptr; }; template typename T void LeftIstHeapT::merge(LeftIstHeapNodeT* bemerged_root) { if (root nullptr) { root bemerged_root; return; } else if (bemerged_root nullptr) { return; } struct StackNodeinfo { LeftIstHeapNodeT* left_ptr_to_heap_be_merged_sub_tree_in nullptr; //本次合并操作中根节点值较小的被合并左式堆的根节点 StackNodeinfo(LeftIstHeapNodeT* l) :left_ptr_to_heap_be_merged_sub_tree_in(l) {} }; LeftIstHeapNodeT* cur_ptr nullptr; //自底向上合并过程中指向当前合并结果对应的左式堆根节点的指针 stackStackNodeinfo work_stack; { LeftIstHeapNodeT* cur_left_ptr root; //自顶向下分解合并操作的过程中当前需要合并的两个左式堆的根节点指针cur_left_ptr,cur_right_ptr LeftIstHeapNodeT* cur_right_ptr bemerged_root; while (cur_left_ptr ! nullptr) //自顶向下分解合并操作 { if (*(cur_right_ptr-data_field) *(cur_left_ptr-data_field)) //cur_right_ptr和cur_left_ptr右子树合并 { work_stack.push(StackNodeinfo(cur_left_ptr)); cur_left_ptr cur_left_ptr-right_node_ptr; } else //cur_left_ptr和cur_right_ptr右子树合并 { work_stack.push(StackNodeinfo(cur_right_ptr)); LeftIstHeapNodeT* temp cur_left_ptr; cur_left_ptr cur_right_ptr-right_node_ptr; cur_right_ptr temp; } } //这里cur_left_ptr必定为空, cur_right_ptr必定不为空,work_stack必不为空 cur_ptr cur_right_ptr; } while (work_stack.empty() false) //自底向上合并左式堆 { work_stack.top().left_ptr_to_heap_be_merged_sub_tree_in-right_node_ptr cur_ptr; //当前合并结果链接至上一层在向下分解合并操作时根节点值较小的左式堆根节点右指针域 if (work_stack.top().left_ptr_to_heap_be_merged_sub_tree_in-left_node_ptr nullptr || cur_ptr-zero_road_length work_stack.top().left_ptr_to_heap_be_merged_sub_tree_in-left_node_ptr-zero_road_length) //交换左右子树恢复左式堆性质 { if (work_stack.top().left_ptr_to_heap_be_merged_sub_tree_in-left_node_ptr nullptr) { work_stack.top().left_ptr_to_heap_be_merged_sub_tree_in-zero_road_length 0; } else { work_stack.top().left_ptr_to_heap_be_merged_sub_tree_in-zero_road_length work_stack.top().left_ptr_to_heap_be_merged_sub_tree_in-left_node_ptr-zero_road_length 1; } swap(work_stack.top().left_ptr_to_heap_be_merged_sub_tree_in-left_node_ptr, work_stack.top().left_ptr_to_heap_be_merged_sub_tree_in-right_node_ptr); } else { work_stack.top().left_ptr_to_heap_be_merged_sub_tree_in-zero_road_length cur_ptr-zero_road_length 1; //右子树零路径长度可能减小故需更新根节点零路径长 } cur_ptr work_stack.top().left_ptr_to_heap_be_merged_sub_tree_in; work_stack.pop(); } root cur_ptr; } template typename T int Searchd(LeftIstHeapNodeT* ptr, int d) { if (d 2) return 0; else { if (d 1) { if (ptr-right_node_ptr nullptr) return 0; else return 2; } else { if (ptr-left_node_ptr ! nullptr) return 1; else { if (ptr-right_node_ptr ! nullptr) return 2; else return 0; } } } } template typename T void adjustUntilRoot(stackStackNodeInfoT work_stack, bool processPtrZero) //向上调整恢复左式堆性质指导根节点 { if (work_stack.empty()) return; if (work_stack.top().direction 1) { if (work_stack.top().p-left_node_ptr nullptr) { if (work_stack.top().p-right_node_ptr ! nullptr) { swap(work_stack.top().p-left_node_ptr, work_stack.top().p-right_node_ptr); } else { return; } } } if (processPtrZero) { work_stack.top().p-zero_road_length 0; work_stack.pop(); } while (work_stack.empty() false) //循环不变式,每一轮循环开始时,栈顶节点按direction方向指向的子节点的零路径长一定减小循环过程中该不变式一直维持 { if (work_stack.top().direction 1) //循环过程中return是因为栈顶节点的零路径长度不变没有必要继续向根节点调整 { if (work_stack.top().p-right_node_ptr ! nullptr work_stack.top().p-left_node_ptr-zero_road_length work_stack.top().p-right_node_ptr-zero_road_length) { swap(work_stack.top().p-left_node_ptr, work_stack.top().p-right_node_ptr); } else { return; } } work_stack.top().p-zero_road_length work_stack.top().p-right_node_ptr-zero_road_length 1; work_stack.pop(); } } template typename T void LeftIstHeapT::changeNodeValue(LeftIstHeapNodeT* bechanged, T* change_value, stackStackNodeInfoT work_stack) { if (*(bechanged-data_field) *change_value) { return; } if (*(bechanged-data_field) *change_value) { *(bechanged-data_field) *change_value; LeftIstHeapNodeT* left_ptr nullptr; LeftIstHeapNodeT* right_ptr nullptr; if (bechanged-left_node_ptr ! nullptr *(bechanged-left_node_ptr-data_field) *change_value) { left_ptr bechanged-left_node_ptr; bechanged-left_node_ptr nullptr; } if (bechanged-right_node_ptr ! nullptr *(bechanged-right_node_ptr-data_field) *change_value) { right_ptr bechanged-right_node_ptr; bechanged-right_node_ptr nullptr; } bool adjust true; if (left_ptr ! nullptr) { if (right_ptr nullptr) { if (bechanged-right_node_ptr ! nullptr) swap(bechanged-left_node_ptr, bechanged-right_node_ptr); else adjust false; } } else { if (right_ptr nullptr) return; } if (adjust) { bechanged-zero_road_length 0; adjustUntilRoot(work_stack, false); } merge(left_ptr); merge(right_ptr); } else { *(bechanged-data_field) *change_value; if (work_stack.empty() false) { if (*(work_stack.top().p-data_field) *(bechanged-data_field)) //堆序仍然满足无需做任何操作直接返回 { return; } if (work_stack.top().direction 1) { work_stack.top().p-left_node_ptr nullptr; } else { work_stack.top().p-right_node_ptr nullptr; } adjustUntilRoot(work_stack, true); merge(bechanged); } } } template typename T bool LeftIstHeapT::changeNodeVauleForNodeHaveSepecificValue(T* original_node_value, T* change_value) //在左式堆中搜索值为original_node_value的节点将其更改为change_value并恢复左式堆性质 { LeftIstHeapNodeT* cur_ptr root; if (cur_ptr nullptr) { return false; } int d 0; stackStackNodeInfoT work_stack; int interval; while (true) { if ((interval Searchd(cur_ptr, d)) 0) { if (cur_ptr root) { if (d 0) { if (*(root-data_field) *original_node_value) { changeNodeValue(root, change_value, work_stack); return true; } else { return false; } } else { return false; } } else { if (d 0) { if (*(cur_ptr-data_field) *original_node_value) { changeNodeValue(cur_ptr, change_value, work_stack); return true; } } else { work_stack.pop(); } cur_ptr work_stack.top().p; d work_stack.top().direction; } } else { if (d 0) { if (*(cur_ptr-data_field) *original_node_value) //original_node_value小于当前节点值无需向当前节点及其子树搜索直接回溯至上一层 { if (work_stack.empty() true) //original_node_value小于左式堆最小值搜索失败 return false; cur_ptr work_stack.top().p; d work_stack.top().direction; continue; } else if (*(cur_ptr-data_field) *original_node_value) { changeNodeValue(cur_ptr, change_value, work_stack); return true; } work_stack.push(StackNodeInfoT(cur_ptr, interval)); //original_node_value大于当前节点值继续向当前节点子树搜索 if (work_stack.top().direction 1) cur_ptr cur_ptr-left_node_ptr; else cur_ptr cur_ptr-right_node_ptr; } else { work_stack.top().direction 2; cur_ptr cur_ptr-right_node_ptr; } d 0; } } } template typename T void LeftIstHeapT::insert(T* data) { LeftIstHeapNodeT* ptr new LeftIstHeapNodeT(data); merge(ptr); } template typename T T* LeftIstHeapT::removeMinValue() { T* data new T(*(root-data_field)); LeftIstHeapNodeT* ptr_right root-right_node_ptr; LeftIstHeapNodeT* ptr_left root-left_node_ptr; delete root; root ptr_left; merge(ptr_right); return data; } template typename T JudgeResult LeftIstHeapT::isLeftIstHeap(LeftIstHeapNodeT* root) //判断以root为根的二叉树是否为左式堆 { if (root nullptr) { return JudgeResult(); } JudgeResult result; long long zero_road_length -1; if (root-left_node_ptr ! nullptr) { JudgeResult temp isLeftIstHeap(root-left_node_ptr); if (temp.isLeftIstHeap *(root-data_field) *(root-left_node_ptr-data_field)) { zero_road_length temp.zero_road_length; } else { result.isLeftIstHeap false; return result; } } if (root-right_node_ptr ! nullptr) { JudgeResult temp isLeftIstHeap(root-right_node_ptr); if (temp.isLeftIstHeap *(root-data_field) *(root-right_node_ptr-data_field) zero_road_length temp.zero_road_length) { result.zero_road_length temp.zero_road_length 1; } else { result.isLeftIstHeap false; } } else { result.zero_road_length 0; } return result; } int main() { const int N 2000; LeftIstHeapint test_obj; vectorint input(N); for (int i 0; i N; i) { input[i] i 1; } /*for (int i 1; i N; i) { input.push_back(i); }*/ shuffle(input.begin(), input.end(), default_random_engine()); for (const int i : input) { cout 插入关键码 i endl; cout endl; test_obj.insert(new int(i)); if (test_obj.satisfyLeftIstHeapNature()) { cout 当前树为左式堆 endl; cout endl; } else { cout ERROR:当前树不为左式堆 endl; exit(-1); } } /*while (test_obj.empty() false) { shared_ptrint min_value(test_obj.removeMinValue()); cout 删除左式堆中最小关键码 *min_value endl; cout endl; if (test_obj.satisfyLeftIstHeapNature()) { cout 当前树为左式堆 endl; cout endl; } else { cout ERROR:当前树不为左式堆 endl; exit(-1); } } cout 左式堆为空 endl; cout endl; for (const int i : input) { cout 插入关键码 i endl; cout endl; test_obj.insert(new int(i)); }*/ cout 将左式堆中各元素增加到最大值前左式堆的最小关键码为 *(test_obj.getMinValue()) endl; cout endl; /*for (int i : input) { cout 将左式堆中关键码 i 减小为 i / 2 endl; cout endl; int* t new int(i / 2); test_obj.changeNodeVauleForNodeHaveSepecificValue(i, t); if (test_obj.satisfyLeftIstHeapNature()) { cout 当前树为左式堆 endl; cout endl; } else { cout ERROR:当前树不为左式堆 endl; exit(-1); } } cout 现在左式堆的最小关键码为 *(test_obj.getMinValue());*/ for (int i : input) { cout 将左式堆中关键码 i 增大为 i * 2 endl; cout endl; int* t new int(i * 2); test_obj.changeNodeVauleForNodeHaveSepecificValue(i, t); if (test_obj.satisfyLeftIstHeapNature()) { cout 当前树为左式堆 endl; cout endl; } else { cout ERROR:当前树不为左式堆 endl; exit(-1); } } cout 现在左式堆的最小关键码为 *(test_obj.getMinValue()); return 0; }