MergeableHeap.h

Go to the documentation of this file.

#ifndef   dsa_MergeableHeap_H__
#define   dsa_MergeableHeap_H__

#include <cstdlib>
#include <algorithm>

namespace meow {

template<class Element>
class MergeableHeap { // maximum-heap
private:
  struct Node {
    Element  value_;
    Node*   lChild_;
    Node*   rChild_;
    size_t  weight_;
    Node(Element const& value):
    value_(value), lChild_(NULL), rChild_(NULL), weight_(1){
    }
  };

  Node* root_;

  void clear(Node* node) {
    if (node != NULL) {
      clear(node->lChild_);
      clear(node->rChild_);
      delete node;
    }
  }
  Node* dup(Node* node) {
    if (node == NULL) return NULL;
    Node* ret = new Node(node->value_);
    ret->lChild_ = dup(node->lChild_);
    ret->rChild_ = dup(node->rChild_);
    ret->weight_ = 1;
    ret->weight_ += (ret->lChild_ == NULL ? 0 : ret->lChild_->weight_);
    ret->weight_ += (ret->rChild_ == NULL ? 0 : ret->rChild_->weight_);
    return ret;
  }
  Node* merge(Node* left, Node* right) {
    if (left  == NULL) return right;
    if (right == NULL) return left;
    if (left->value_ < right->value_) {
      std::swap(left, right);
    }
    left->rChild_ = merge(left->rChild_, right);
    size_t lw = (left->lChild_ == NULL ? 0 : left->lChild_->weight_);
    size_t rw = (left->rChild_ == NULL ? 0 : left->rChild_->weight_);
    if (lw < rw) {
      std::swap(left->lChild_, left->rChild_);
    }
    left->weight_ = 1 + lw + rw;
    return left;
  }
public:
  MergeableHeap(): root_(NULL){
  }

  MergeableHeap(MergeableHeap const& heap2): root_(dup(heap2.root_)) {
  }

  ~MergeableHeap(){
    clear(root_);
  }

  MergeableHeap& copyFrom(MergeableHeap const& heap2) {
    delete root_;
    root_ = dup(heap2.root_);
    return *this;
  }

  void moveTo(MergeableHeap* heap2){
    heap2->clear();
    heap2->root_ = root_;
    root_ = NULL;
  }

  Element const& top() const {
    return root_->value_;
  }

  size_t size() const {
    return (root_ == NULL ? 0 : root_->weight_);
  }

  bool empty() const {
    return (size() == 0);
  }

  void push(Element const& value) {
    root_ = merge(root_, new Node(value));
  }

  void pop() {
    Node* l = root_->lChild_;
    Node* r = root_->rChild_;
    delete root_;
    root_ = merge(l, r);
  }

  void clear() {
    clear(root_);
    root_ = NULL;
  }

  void merge(MergeableHeap* heap2) {
    root_ = merge(root_, heap2->root_);
    heap2->root_ = NULL;
  }

  MergeableHeap& operator=(MergeableHeap const& heap2) {
    return copyFrom(heap2);
  }
};

}

#endif // dsa_MergeableHeap_H__