www.pudn.com > OPENCV_SIFT_VC6.rar > MinHeap.cpp

// MinHeap.cpp: implementation of the CMinHeap class. 
// 
////////////////////////////////////////////////////////////////////// 
 
#include "stdafx.h" 
#include "TestSIFT.h" 
#include "MinHeap.h" 
 
#ifdef _DEBUG 
#undef THIS_FILE 
static char THIS_FILE[]=__FILE__; 
#define new DEBUG_NEW 
#endif 
 
////////////////////////////////////////////////////////////////////// 
// Construction/Destruction 
////////////////////////////////////////////////////////////////////// 
 
CMinHeap::CMinHeap() 
{ 
 
} 
 
CMinHeap::~CMinHeap() 
{ 
 
} 
 
void CMinHeap::insert (CMatchInfo info) 
{ 
	m_infos.push_back (info); 
	percolateup (m_infos.size()-1); 
} 
 
CMatchInfo CMinHeap::deleteMin () 
{ 
	CMatchInfo min = m_infos[0]; 
	m_infos[0] = m_infos[m_infos.size()-1]; 
	m_infos.pop_back(); 
	percolatedown (0); 
	return min; 
} 
 
int CMinHeap::getSize () 
{ 
	return m_infos.size(); 
} 
 
void CMinHeap::percolatedown (int i) 
{ 
	while (i*2 < m_infos.size()) 
	{ 
		int downi = i*2; 
		if (downi+1 < m_infos.size()) 
			if (m_infos[downi+1].m_distance < m_infos[downi].m_distance) 
				downi++; 
		if (m_infos[i].m_distance > m_infos[downi].m_distance) 
		{ 
			CMatchInfo tmp = m_infos[i]; 
			m_infos[i] = m_infos[downi]; 
			m_infos[downi] = tmp; 
			i = downi; 
		} 
		else 
			break; 
	} 
} 
 
void CMinHeap::percolateup (int i) 
{ 
	while (i > 0) 
	{ 
		if (m_infos[i].m_distance < m_infos[i/2].m_distance) 
		{ 
			CMatchInfo tmp = m_infos[i]; 
			m_infos[i] = m_infos[i/2]; 
			m_infos[i/2] = tmp; 
			i /= 2; 
		} 
		else 
			break; 
	} 
} 
 
double CMinHeap::get2ndMin() 
{ 
	double secondMin = 1e10; 
	if (m_infos.size() >= 2) 
	{	 
		secondMin = m_infos[1].m_distance; 
		if (m_infos.size() > 2 && secondMin > m_infos[2].m_distance) 
			secondMin = m_infos[2].m_distance;			 
	} 
	return secondMin; 
}