heap.cpp

一个基于MFC的SIFT图像配准算法代码。好用

// Heap.cpp: implementation of the CHeap class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "disparity 200712.h"
#include "Heap.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CHeap::CHeap()
{
	data = new CSeed [600*400+1];	//分配空间，并没有把堆设为二叉树的形式，而是用线性表来表示
	pt = 1;	
}

CHeap::~CHeap()
{
   delete []data;
}

//由下向上构造小顶堆（插入元素时使用）
void CHeap::CheckUp(long n)
{
	if (n==1)		//如果已到达顶端，返回
	{
		return;
	}
	else			//如果没有到达顶端
	{
		if ( data[n].diff < data[n/2].diff )	//如果子节点比父节点小，则交换位置
		{
			CSeed temp;
			temp = data[n];
			data[n] = data[n/2];
			data[n/2] = temp;
		}
		CheckUp(n/2);		//继续检查父节点
		return;
	}
}


//在堆的底端插入一个新元素
void CHeap::Insert(CSeed s)
{
	data[pt] = s;	//插入元素
	CheckUp(pt);	//由下向上构造小顶堆
	pt++;			//指针加一
}


//由上向下构造小顶堆（提取最大元素时使用）
void CHeap::CheckDown(long n)
{
	if ( 2*n>=pt )//如果两子树都为空，直接返回
	{
		return;
	}
	else if ( 2*n+1>=pt )//如果右子树为空，继续判断
	{
		if ( data[n].diff  > data[2*n].diff)	//如果父节点大于子节点，则交换位置
		{
			CSeed temp = data[n];
			data[n] = data[2*n];
			data[2*n] = temp;
		}
		return;
	}
	else //如果两子树都不空……
	{
		//如果父节点小于两个子节点，不改变位置
		if ( data[n].diff <= data[2*n].diff && data[n].diff <= data[2*n+1].diff )
		{
			return;
		}

		//如果左子节点比较小，则交换父节点和左子的位置
		else if ( data[2*n].diff < data[n].diff && data[2*n].diff <= data[2*n+1].diff )
		{
			CSeed temp;
			temp = data[n];
			data[n] = data[n*2];
			data[n*2] = temp;
			CheckDown( 2*n );
			return;
		}

		//如果右子节点比较小，则交换父节点和右子的位置
		else if ( data[2*n+1].diff < data[n].diff && data[2*n+1].diff < data[2*n].diff ) 
		{
			CSeed temp;
			temp = data[n];
			data[n] = data[n*2+1];
			data[n*2+1] = temp;
			CheckDown( 2*n+1 );
			return;
		}
	}
	return;
}


//提取最小的元素
CSeed CHeap::PullMin(void)
{
	CSeed min = data[1];	//记录最小的元素
	pt--;					//指针减一
	data[1] = data[pt];		//将最后一个元素提到顶端
	CheckDown(1);			//由上向下构造小顶堆
	return min;				//返回最小元素
}


//指示堆是否为空
bool CHeap::IsEmpty(void)
{
	if ( pt == 1 )
	{
		return 1;
	}
	else
	{
		return 0;
	}
}