堆　　　堆元素的插入　　最小堆　　堆元素的移除

稍微改动过的版本：

#pragma once#include<iostream>using namespace std;template<class Type>class MinHeap{public:    MinHeap(int sz = DEFAULT_HEAP_SIZE)    {        capacity = sz > DEFAULT_HEAP_SIZE ? sz : DEFAULT_HEAP_SIZE;        heap = new Type[capacity];        size = 0;    }    MinHeap(Type ar[], int n)    {        capacity = n>DEFAULT_HEAP_SIZE?n:DEFAULT_HEAP_SIZE;        heap = new Type[capacity];        for(int i=0; i<n; ++i)        {            heap[i] = ar[i];        }        size = n;        int curpos = n/2-1;        while(curpos >= 0)        {            siftDown(curpos,size-1);            curpos--;        }    }    ~MinHeap()    {        delete []heap;        capacity = size = 0;    }public:    bool IsFull()const    {        return size >= capacity;    }    bool IsEmpty()const    {        return size == 0;    }public:    void ShowHeap()const    {        for(int i=0; i<size;++i)        {            cout<<heap[i]<<" ";        }        cout<<endl;    }public:    void Insert(Type x)    {        if(!IsFull())        {            heap[size] = x;            siftUp(size);            size++;        }    }    Type Remove()    {        Type val;        if(!IsEmpty())        {            val = heap[0];            heap[0] = heap[size-1];            size--;            siftDown(0,size-1);        }        return val;    }private:    void siftDown(int start, int m);    void siftUp(int start);private:    enum{DEFAULT_HEAP_SIZE=20};    Type *heap;    int capacity;    int size;};template<class Type>void MinHeap<Type>::siftDown(int start, int m)//非递归版本的{    int i = start;    int j = 2*i+1;    while(j <= m)    {        if(j+1<=m && heap[j]>heap[j+1])            j = j+1;        if(heap[j] < heap[i])        {            Type tmp = heap[j];            heap[j] = heap[i];            heap[i] = tmp;        }        else            break;        i = j;        j = 2*i+1;    }}template<class Type>void MinHeap<Type>::siftUp(int start){    int j = start; //    int i = (j-1)/2; //    while(j > 0)    {        if(heap[i] < heap[j])            break;        else        {            Type tmp = heap[i];            heap[i] = heap[j];            heap[j] = tmp;        }        j = i;        i = (j-1)/2;    }}