最小堆模板类实现

MinHeap.hpp

#include <iostream>

template <class type>
class MinHeap
{
public:
    MinHeap(int maxsize);
    MinHeap(type* arr, int n);
    ~MinHeap(){clear();}

    int getHeapSize(){ return m_heapSize;}
    type getHeapTop(){ return m_heapArr[0];}
    void deleteTop();
    void resize(int newsize);
    bool isEmpty(){ return (m_heapSize == 0);}
    bool isFull(){ return (m_heapSize == m_maxSize);}
    void insertNode(const type& data);
    void show();
private:
    int        m_heapSize;
    int        m_maxSize;
    type*    m_heapArr;
    void filterDown(int p);
    void filterUp(int p);
    void clear(){ if(m_heapArr) delete []m_heapArr;}
};


template <class type>
void swap(type* a, type* b)
{
    type t;
    t = *a;
    *a = *b;
    *b = t;
}

template <class type>
MinHeap<type>::MinHeap(int maxsize)
    :m_maxSize(maxsize)
    ,m_heapSize(0)
{
    m_heapArr = new type[m_maxSize];
}

template <class type>
MinHeap<type>::MinHeap(type* arr, int n)
    :m_maxSize(n)
    ,m_heapSize(n)
{
    m_heapArr = new type[m_maxSize];
    for(int i = 0; i < n; ++i)
    {
        m_heapArr[i] = arr[i];
    }

    int i = m_heapSize - 1;
    while(i >= 0)
    {
        filterDown(i);
        i--;
    }
}

template <class type>
void MinHeap<type>::resize(int newsize)
{
    if(newsize <= m_maxSize)
    {
        std::cout << "the new size is small than before, ignored!" << std::endl;
        return;
    }
    m_maxSize = newsize;
    type* temp = new type[m_maxSize];
    for(int i = 0; i < m_heapSize; i++)
    {
        temp[i] = m_heapArr[i];
    }

    delete []m_heapArr;
    m_heapArr = temp;
}

template <class type>
void MinHeap<type>::filterDown(int p)
{
    int j, i = p;
    j = i * 2 + 1;

    while(j < m_heapSize)
    {
        if( (j < m_heapSize -1) && (m_heapArr[j + 1] < m_heapArr[j]))
            j++;
        if(m_heapArr[i] <= m_heapArr[j]) break;
        else
        {
            swap(&(m_heapArr[i]), &(m_heapArr[j]));
            i = j;
            j = j * 2 + 1;
        }
    }
}

template <class type>
void MinHeap<type>::filterUp(int p)
{
    int i, j = p;
    i = (j - 1)/2;

    while( i >= 0)
    {
        if(m_heapArr[i] <= m_heapArr[j]) break;
        else
        {
            swap(&(m_heapArr[i]), &(m_heapArr[j]));
            j = i;
            i = (i -1)/2;
        }
    }
}

template <class type>
void MinHeap<type>::deleteTop()
{
    if(m_heapSize == 0)
    {
        std::cout << "the heap is empty, ignore this operation!" << std::endl;
        return;
    }

    m_heapArr[0] = m_heapArr[m_heapSize - 1];
    m_heapSize--;

    filterDown(0);
}

template <class type>
void MinHeap<type>::insertNode(const type& data)
{
    if(m_heapSize == m_maxSize)
    {
        std::cout << "the heap is already full, ignore this operation!" << std::endl;
        return;
    }

    m_heapArr[m_heapSize] = data;

    filterUp(m_heapSize);

    ++m_heapSize;
}

template <class type>
void MinHeap<type>::show()
{
    for(int i = 0; i < m_heapSize; ++i)
        std::cout << m_heapArr[i] << " ";
    std::cout << std::endl;

}

test.cpp

#include "MinHeap.hpp"

int main()
{
    int a[10] = {10, 1, 4, 2, 3, 5, 9, 8, 6, 7};

    MinHeap<int> heap(a, 10);

    heap.show();

    heap.resize(15);

    heap.insertNode(2);

    heap.show();

    heap.deleteTop();

    heap.show();

    system("pause");
    return 0;
}