heapif.txt

常见算法

#define N 10
#include <iostream>
#include<math.h>
using std::cout;
using std::cin;
using std::endl;

main()
{
	int A[N];                                   //建立一个数组
	int i;

    void heapify(int [],int);                    //保持堆的性质函数的声明
	cout<<"input the array please:"<<endl;       //输入数组
    for(i=0;i<N;i++)
	{
		cin>>A[i];
	}
    for (i=(N-1)/2;i>=0;i--)                         //建堆过程
    {
        heapify(A,i);
    }
	cout<<"the array heap is:"<<endl;             //堆的输出
	for(i=0;i<N;i++)
	{cout<<A[i]<<"  ";}
	cout<<endl;
    return 0;
}
void heapify(int B[],int i)                           //保持堆的性质定义
{
    int l,r,largest,key;                           //设置左子节点、右子节点、和其父节点
	int left(int);                              //取左子节点和右子结点   
	int right(int);
	l=left(i);
	r=right(i);
    int heapsize=N-1;
	if ((l<=heapsize)&&(B[l]>B[i]))
		largest=l;
	else 
		largest=i;
	
    if((r<=heapsize)&&(B[r]>B[largest]))
		largest=r;
	if (largest!=i)
	{
		key=B[i];
		B[i]=B[largest];
		B[largest]=key;
	    heapify(B,largest);
	}
	 
}  
int left(int i)
{
	return 2*i+1;
}
int right(int i)
{
	return 2+2*i;
}