二叉堆(3)SkewHeap

2020-02-20 16:00:50来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

二叉堆(3)SkewHeap

斜堆。

 

测试文件 main.cpp:

#include <iostream>
#include "SkewHeap.h"

using std::cout;
using std::endl;

int main()
{
    SkewHeap<int> lh(SkewHeap<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;
}

 

头文件 "SkewHeap":

#pragma once
#ifndef __SKEWHEAP_H__
#define __SKEWHEAP_H__


#include "BinaryTreeOperations.h"
template<typename _Ty>
class SkewHeap
{
    struct Node
    {
        _Ty key;
        Node* left = nullptr;
        Node* right = nullptr;
        Node(const _Ty& _key) :key(_key) {}
    };

public:
    enum class HeapType :bool { MINIMEM = 0, MAXIMEM };

public:
    SkewHeap() = default;
    SkewHeap(HeapType _heapType) { heapType = _heapType; }
    ~SkewHeap() { 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(SkewHeap<_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 SkewHeap<_Ty>::pop()
{
    if (root == nullptr) throw std::exception("SkewHeap is empty!");
    Node* leftT = root->left;
    Node* rightT = root->right;
    delete root;
    root = merge(leftT, rightT);
    --size_n;
}

template<typename _Ty>
_Ty& SkewHeap<_Ty>::top() const
{
    if (root == nullptr) throw std::exception("SkewHeap is empty!");
    return root->key;
}

template<typename _Ty>
void SkewHeap<_Ty>::push(const _Ty& _key)
{
    Node* temp = new Node(_key);
    root = merge(root, temp);
    temp = nullptr;
    ++size_n;
}

template<typename _Ty>
void SkewHeap<_Ty>::merge(SkewHeap<_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 SkewHeap<_Ty>::Node* SkewHeap<_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);
    std::swap(_n1->left, _n1->right);

    return _n1;
}


#endif // !__SKEWHEAP_H__

 


原文链接:https://www.cnblogs.com/teternity/p/SkewHeap.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C++ Primer 抄书笔记(一)

下一篇:STL中_Rb_tree的探索