?

constint maxheapsize=100;
staticint currentsize=0;

//從上到下調(diào)整堆
void siftDown(int* heap,int currentPos,int m)
{
??? int i=currentPos;
??? int j=currentPos*2+1;//i's leftChild
int temp=heap[i];
??? while(j<=m)
??? {
??????? if(j<m&&heap[j]>heap[j+1]) j++;// j points to minChild
if(temp<=heap[j]) break;
??????? else
??????? {
??????????? heap[i]=heap[j];
??????????? i=j;
??????????? j=2*i+1;
??????? }
??? }
??? heap[i]=temp;
}

//從下向上調(diào)整堆
void siftUp(int* heap, int start)
{
??? int i=start,j=(i-1)/2;
??? int temp=heap[i];

??? while(i>0)
??? {
??????? if(heap[j]>temp)
??????? {
??????????? heap[i]=heap[j];
??????????? i=j;
??????????? j=(i-1)/2;
??????? }
??????? elsebreak;
??? }
??? heap[i]=temp;
}

//構(gòu)建堆
int* Heap(int*arr, int size)
{
??? int i;
??? currentsize=size;
??? int* heap =newint[maxheapsize];
??? assert(heap!=NULL);
??? for(i=0;i<currentsize;i++) heap[i]=arr[i];
??? int currentPos=(currentsize-2)/2;
??? while(currentPos>=0)
??? {
??????? siftDown(heap,currentPos,currentsize-1);
??????? currentPos--;
??? }
??? return heap;
}

//增加一個元素
void insert(int* heap,int value)
{
??? if(currentsize>=maxheapsize)
??? {
??????? cout<<"Heap is full!"<<endl;
??????? return ;
??? }
??? heap[currentsize]=value;
??? siftUp(heap,currentsize);
??? currentsize++;
}

//刪除一個元素,并返回刪除前的堆頂元素
int removemin(int* heap)
{
??? assert(currentsize>=0);
??? int removeValue=heap[0];
??? heap[0]=heap[currentsize-1];
??? currentsize--;
??? siftDown(heap,0,currentsize-1);
??? return removeValue;
}

int main()
{
??? constint size=10;
??? int arr[size]={2,1,3,0,8,1,6,9,7,10};
??? int* heap=Heap(arr,size);
??? //堆排序
for(int i=0;i<size;i++)
??? {
??????? arr[i]=removemin(heap);
??????? cout<<arr[i]<<endl;
??? }
??? delete []heap;
??? return0;

?
?

}