最小堆

#ifndef _MIN_HEAP_H_
#define _MIN_HEAP_H_

#include <iostream>
#include <vector>

//最小堆节点类

template < class Type > class Node
{
  public:
    Node (const int p = 0);
    Node (const Node < Type > &node);
    ~Node ();
    void SetData (const Type * d);
    Type *GetData () const;
    int GetPriority () const;
    void SetPriority (const int p);
    bool operator> (const Node < Type > &node) const
    {
        return priority > node.priority;
    }
    bool operator< (const Node < Type > &node) const
    {
        return priority < node.priority;
    }
    bool operator== (const Node < Type > &node) const
    {
        return priority == node.priority;
    }
    bool operator>= (const Node < Type > &node) const
    {
        return priority >= node.priority;
    }
    bool operator<= (const Node < Type > &node) const
    {
        return priority <= node.priority;
    }
    const Node < Type > &operator = (const Node < Type > &node)
    {
        SetPriority (node.GetPriority ());
        SetData (node.GetData ());
        return (*this);
    }
  private:
    int priority;
    Type *data;
};

template < class Type > Node < Type >::Node (const int p):
priority (p),
data (NULL)
{
    data = new Type ();
}

template < class Type > Node < Type >::Node (const Node < Type > &node):
priority (node.GetPriority ())
{
    data = new Type (*(node.data));
}

template < class Type > Node < Type >::~Node ()
{
    if (!data)
    {
        delete data;
    }
}

template < class Type > void Node < Type >::SetData (const Type * d)
{
    if (!data)
    {
        delete data;
    }
    data = new Type (*d);
}

template < class Type > Type * Node < Type >::GetData ()const
{
    return new Type (*data);
}

template < class Type > int Node < Type >::GetPriority () const
{
    return priority;
}

template < class Type > void Node < Type >::SetPriority (const int p)
{
    priority = p;
}

//======================================================================================//


template < class Type > class MinHeap
{
  public:
    MinHeap (const int c = 10);
    ~MinHeap ();
    bool Add (const int p, const Type * data);
    Node < Type > *Delete ();
    Type *DeleteData ();        //Get the data pointer from the node of the minimum priority.

    int DeleteBiggerThan (int minValueOfPriority);    //Delete the node that priority is bigger than minValueOfPriority.

    bool IsEmpty ();
    void print ();
    int Size ();                //MinHeap's current size;

  private:
    void FilterUp (const int start);
    void FilterDown (const int start, const int endOfMinHeap);
    int capacity;
    int size;
    std::vector < Node < Type > >arr;
};

template < class Type > MinHeap < Type >::MinHeap (const int c):
capacity (c),
size (0)
{
    capacity = capacity > 0 ? capacity : 1;
    arr.resize (capacity);
}

template < class Type > MinHeap < Type >::~MinHeap ()
{
}

template < class Type > bool MinHeap < Type >::Add (const int p, const Type * data)
{
    if (size >= capacity)
    {
        capacity *= 2;
        arr.resize (capacity);
    }
    arr[size].SetData (data);
    arr[size].SetPriority (p);
    if (++size > 1)
    {
        FilterUp (size - 1);
    }
    return true;
}

template < class Type > void MinHeap < Type >::print ()
{
    std::cout << "MinHeap:\nCapacity is ";
    std::cout << capacity << " , Size is ";
    std::cout << size << std::endl;
    for (int i = 0; i < size; i++)
    {
        std::cout << arr[i].GetPriority () << "\t";
        Type* d=arr[i].GetData ();
        if(d!=NULL)
        {
            std::cout << *d << "\n";
            delete d;
        }
    }
    if (1 > size)
    {
        std::cout << "The MinHeap is Empty.";
    }
    std::cout << std::endl;
}

template < class Type > Node < Type > *MinHeap < Type >::Delete ()
{
    if (IsEmpty ())
    {
        return NULL;
    }
    Node < Type > *node = new Node < Type > (arr[0]);
    arr[0] = arr[--size];
    FilterDown (0, size - 1);
    return node;
}

template < class Type > Type * MinHeap < Type >::DeleteData ()
{
    Node < Type > *node = Delete ();
    if (node == NULL)
    {
        return NULL;
    }
    Type *rv = node->GetData ();
    delete node;
    return rv;
}

//删除优先级大于某个数的节点（双端优先队列）

template < class Type > int MinHeap < Type >::DeleteBiggerThan (int minValueOfPriority)
{
    int rv = 0;                    //删除节点的个数

    for (int i = 0; i < size; i++)
    {
        if (arr[i].GetPriority () > minValueOfPriority)
        {
            rv++;
        }
    }
    if (0 == rv)
    {
        return rv;
    }

    std::vector < Node < Type > >vector;
    vector.resize (size);
    vector.assign (arr.begin (), arr.begin () + size);
    size = 0;
    for (unsigned int i = 0; i < vector.size (); i++)
    {
        if (vector[i].GetPriority () <= minValueOfPriority)
        {
            Add (vector[i].GetPriority (), vector[i].GetData ());
        }
    }
    return rv;
}

template < class Type > bool MinHeap < Type >::IsEmpty ()
{
    return size <= 0;
}

template < class Type > void MinHeap < Type >::FilterUp (const int start)
{
    int i = start, j = (i - 1) / 2;
    Node < Type > *temp = new Node < Type > (arr[i]);
    while (i > 0)
    {
        if (*temp >= arr[j])
        {
            break;
        }
        else
        {
            arr[i] = arr[j];
            i = j;
            j = (i - 1) / 2;
        }
    }
    arr[i] = *temp;
    delete temp;
}

template < class Type > void MinHeap < Type >::FilterDown (const int start, const int endOfMinHeap)
{
    int i = start, j = i * 2 + 1;
    Node < Type > *temp = new Node < Type > (arr[i]);
    while (j <= endOfMinHeap)
    {
        if (j < endOfMinHeap && arr[j] > arr[j + 1])
        {
            j++;
        }
        if (*temp < arr[j])
        {
            break;
        }
        else
        {
            arr[i] = arr[j];
            i = j;
            j = 2 * i + 1;
        }
    }
    arr[i] = *temp;
    delete temp;
}

//MinHeap's current size;

template < class Type > int MinHeap < Type >::Size ()
{
    return size;
}
#endif