二叉堆(2)LeftistHeap
2020-02-19 16:00:56来源:博客园 阅读 ()
二叉堆(2)LeftistHeap
左倾堆,用于堆的快速合并。
规则:
① 节点的键值小于或等于它的左右子节点的键值。
② 节点的左孩子的NPL >= 右孩子的NPL。
③ 节点的NPL = 它的右孩子的NPL + 1。
测试文件 main.cpp:
#include <iostream> #include "LeftistHeap.h" using std::cout; using std::endl; int main() { LeftistHeap<int> lh(LeftistHeap<int>::HeapType::MINIMEM); auto il = { 1,2,3,4,5,5,6,7,8,9 }; for (auto& x : il) lh.push(x); cout << "Element:\n\t"; lh.levelTraversal(); cout << endl << endl; cout << "Pop: " << lh.top() << endl << endl; lh.pop(); cout << "Element:\n\t"; lh.levelTraversal(); cout << endl; return 0; }
头文件 "LeftistHeap.h":
#pragma once #ifndef __LEFTISTHEAP_H__ #define __LEFTISTHEAP_H__ #include "BinaryTreeOperations.h" template<typename _Ty> class LeftistHeap { struct Node { _Ty key; int NPL = 0; Node* left = nullptr; Node* right = nullptr; Node(const _Ty& _key) :key(_key) {} }; public: enum class HeapType :bool { MINIMEM = 0, MAXIMEM }; public: LeftistHeap() = default; LeftistHeap(HeapType _heapType) { heapType = _heapType; } ~LeftistHeap() { BTO::clear(root); size_n = 0; } void clear() noexcept { BTO::clear(root); size_n = 0; } void preorderTraversal() { BTO::preorderTraversal(root, drawData); } void inorderTraversal() { BTO::inorderTraversal(root, drawData); } void postorderTraversal() { BTO::postorderTraversal(root, drawData); } void iterativePreorderTraversal() { BTO::iterativePreorderTraversal(root, drawData); } void iterativeInorderTraversal() { BTO::iterativeInorderTraversal(root, drawData); } void iterativePostorderTraversal() { BTO::iterativePostorderTraversal(root, drawData); } void levelTraversal() { BTO::levelTraversal(root, drawData); } size_t size() const { return size_n; } void pop(); _Ty& top() const; void push(const _Ty&); void merge(LeftistHeap<_Ty>&); private: static void drawData(const Node* _node) { std::cout << _node->key << " "; } bool compare(const _Ty& _a, const _Ty& _b) { return (heapType == HeapType::MAXIMEM) ? (_a > _b) : (_a < _b); } Node* merge(Node*&, Node*&); private: Node* root = nullptr; size_t size_n = 0; HeapType heapType = HeapType::MAXIMEM; }; template<typename _Ty> void LeftistHeap<_Ty>::pop() { if (root == nullptr) throw std::exception("LeftistHeap is empty!"); Node* leftT = root->left; Node* rightT = root->right; delete root; root = merge(leftT, rightT); --size_n; } template<typename _Ty> _Ty& LeftistHeap<_Ty>::top() const { if (root == nullptr) throw std::exception("LeftistHeap is empty!"); return root->key; } template<typename _Ty> void LeftistHeap<_Ty>::push(const _Ty& _key) { Node* temp = new Node(_key); root = merge(root, temp); temp = nullptr; ++size_n; } template<typename _Ty> void LeftistHeap<_Ty>::merge(LeftistHeap<_Ty>& _lh) { if (heapType != _lh.heapType) throw std::exception("Bad heapType"); root = merge(root, _lh.root); _lh.root = nullptr; size_n += _lh.size_n; _lh.size_n = 0; } template<typename _Ty> typename LeftistHeap<_Ty>::Node* LeftistHeap<_Ty>::merge(Node*& _n1, Node*& _n2) { if (_n1 == nullptr && _n2 == nullptr) return nullptr; else if (_n1 == nullptr) return _n2; else if (_n2 == nullptr) return _n1; if (!compare(_n1->key, _n2->key)) std::swap(_n1, _n2); _n1->right = merge(_n1->right, _n2); if (_n1->left == nullptr || _n1->left->NPL < _n1->right->NPL) std::swap(_n1->left, _n1->right); if (_n1->right == nullptr || _n1->left == nullptr) _n1->NPL = 0; else _n1->NPL = _n1->right->NPL + 1; return _n1; } #endif // !__LEFTISTHEAP_H__
原文链接:https://www.cnblogs.com/teternity/p/12333785.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:序列归并
- 二叉堆(3)SkewHeap 2020-02-20
- 二叉树(四)二叉堆 2020-02-03
- 2977 二叉堆练习1 2018-06-18
- 3110 二叉堆练习3 2018-06-17
- 数据结构和算法(C#实现)系列---二叉堆(数组实现) 2008-02-23
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash