데이터 구조 -- 최소 더미

최소 더미
총체 적 서술

    ，             。
                 。
                ，
         ：
 V[i]   i    
1.     n   ，        1-n     
2.    i，
   2*i <= n， V[i] <= V[2*i]，
   2*i+1 <= n， V[i] <= V[2*i+1]。
             。

인터페이스 디자인

template 
class MinHeap
{
public:
	MinHeap();
	MinHeap(const Array::DynArray& arrElements_);
	~MinHeap();
	MinHeap(const MinHeap& mhA_);
	MinHeap operator=(const MinHeap& mhA_);

	void Add(const T& nT_);
	void Delete(int nIndex_);
	void Set(int nIndex_, const T& nV_);
	T Get(int nIndex_);
	int Find(std::function fun_);
	int GetSize();
private:
	void BuildHeap(const Array::DynArray& arrElements_);
	void Adjust(int nIndex_);
	void Smaller(int nPos_);
	void Bigger(int nPos_);

private:
	Array::DynArray m_arrElements;
};

이루어지다
구조
MinHeap()

template 
MinHeap::MinHeap()
{
}

MinHeap(const Array::DynArray& arrElements_)

template 
MinHeap::MinHeap(const Array::DynArray& arrElements_)
{
	BuildHeap(arrElements_);
}

template 
void MinHeap::BuildHeap(const Array::DynArray& arrElements_)
{
	m_arrElements.DeleteAll();
	m_arrElements.Add(T());
	int _nSize = arrElements_.GetSize();
	for (int _i = 0; _i < _nSize; _i++)
	{
		m_arrElements.Add(arrElements_[_i]);
	}
	
	for (int _i = _nSize; _i >= 1; _i--)
	{
		Adjust(_i);
	}
}

template 
void MinHeap::Adjust(int nIndex_)
{
	T _nV = m_arrElements[nIndex_];
	int _nL = nIndex_ * 2;
	int _nR = _nL + 1;
	T _nMin = m_arrElements[nIndex_];
	int _nMinPos = nIndex_;
	if (_nL < m_arrElements.GetSize()
		&& m_arrElements[_nL] < _nMin)
	{
		_nMin = m_arrElements[_nL];
		_nMinPos = _nL;
	}

	if (_nR < m_arrElements.GetSize()
		&& m_arrElements[_nR] < _nMin)
	{
		_nMin = m_arrElements[_nR];
		_nMinPos = _nR;
	}

	if (_nMinPos == nIndex_)
	{
		// do nothing
	}
	else
	{
		m_arrElements[nIndex_] = _nMin;
		m_arrElements[_nMinPos] = _nV;
		Adjust(_nMinPos);
	}
}

복사 구조

template 
MinHeap::MinHeap(const MinHeap& mhA_)
{
	m_arrElements = mhA_.m_arrElements;
}

값 을 부여 하 다

template 
typename MinHeap MinHeap::operator=(const MinHeap& mhA_)
{
	if (this == &mhA_)
	{
		return *this;
	}

	m_arrElements = mhA_.m_arrElements;
	return *this;
}

분석 하여 구성 하 다

template 
MinHeap::~MinHeap()
{
}

덧붙이다

template 
void MinHeap::Add(const T& nT_)
{
	//       
	int _nSize = m_arrElements.GetSize() - 1;
	if (_nSize < 0)
	{
		m_arrElements.Add(T());
		m_arrElements.Add(nT_);
		return;
	}

	if (_nSize == 0)
	{
		m_arrElements.Add(nT_);
		return;
	}

	//      
	if ((_nSize + 1) % 2 == 0)
	{
		T _nPV = m_arrElements[(_nSize + 1) % 2];
		m_arrElements.Add(_nPV);//          
	}
	else
	{
		m_arrElements.Add(m_arrElements[_nSize]);//          
	}

	//              
	if (nT_ < m_arrElements[_nSize + 1])
	{
		m_arrElements[_nSize + 1] = nT_;
		Smaller(_nSize + 1);
	}
	else if (nT_ > m_arrElements[_nSize + 1])
	{
		m_arrElements[_nSize + 1] = nT_;
		Bigger(_nSize + 1);
	}
	else
	{
		// do nothing
	}
}

template 
void MinHeap::Smaller(int nPos_)
{
	//   nPos      ，nPos  ，                     。
	if (nPos_ == 1)
	{
		return;
	}

	int _nP = nPos_ / 2;
	if (m_arrElements[_nP] <= m_arrElements[nPos_])
	{
		return;
	}
	else
	{
		T _nV = m_arrElements[_nP];
		m_arrElements[_nP] = m_arrElements[nPos_];//       。
		m_arrElements[nPos_] = _nV;// nPos       。             。  nPos                 。
		
		Smaller(_nP);
	}
}

template 
void MinHeap::Bigger(int nPos_)
{
	int _nL = 2 * nPos_;
	int _nR = _nL + 1;
	T _nV = m_arrElements[nPos_];
	T _nMin = m_arrElements[nPos_];
	int _nMinPos = nPos_;
	if (_nL < m_arrElements.GetSize()
		&& m_arrElements[_nL] < _nMin)
	{
		_nMin = m_arrElements[_nL];
		_nMinPos = _nL;
	}

	if (_nR < m_arrElements.GetSize()
		&& m_arrElements[_nR] < _nMin)
	{
		_nMin = m_arrElements[_nR];
		_nMinPos = _nR;
	}

	if (_nMinPos == nPos_)
	{
		return;
	}
	else
	{
		m_arrElements[nPos_] = _nMin;// nPos          。      nPos           。
		m_arrElements[_nMinPos] = _nV;// _nMinPos        
		
		Bigger(_nMinPos);
	}
}

삭제

template 
void MinHeap::Delete(int nIndex_)
{
	int _nSize = m_arrElements.GetSize() - 1;
	if (nIndex_ > _nSize
		|| nIndex_ < 1)
	{
		return;
	}

	if (_nSize == 1)
	{
		m_arrElements.DeleteByIndex(nIndex_);
		return;
	}

	m_arrElements[nIndex_] = m_arrElements[1] - 1;//        
	Smaller(nIndex_);//    ， nIndex          1  
	m_arrElements[1] = m_arrElements[_nSize];
	m_arrElements.DeleteByIndex(_nSize);
	Bigger(1);
}

수색 하 다.

template 
int MinHeap::Find(std::function fun_)
{
	int _nSize = m_arrElements.GetSize();
	for (int _i = 1; _i < _nSize; _i++)
	{
		if (fun_(m_arrElements[_i]))
		{
			return _i;
		}
	}

	return -1;
}

정확성 증명
MinHeap(const Array::DynArray& arrElements_)

  ：    n      
    ：
     n                 m_arrElements   1,...,n 
     ：
            ，                  

for (int _i = _nSize; _i >= 1; _i--)
{
	Adjust(_i);
}
     ：
   [_i+1, _nSize]        ，
        k   ，       
 2*k      ，  V[k] <= V[2*k]
 2*k+1      ，  V[k] <= V[2*k+1]

  ：
   ，   [_nSize+1, _nSize]     ，       
 _i = k   
       【             ，        】
  _i > k      ，        

    ：Adjust(nIndex_)
 [nIndex_+1, nSize]                  ，
    [nIndex_, nSize]       ，
   [nIndex_, nSize]                    。
       ， ，       。

  ：Adjust(nIndex_)      
1.  k               ，     
    。
  ，      ，      。
2.  k          ，     
            k        
   ， k  ，      
   k       t，              
        
 [t+1, nSize]                  ，
    [t, nSize]       ，
   [t, nSize]                    。
               。

  ， Adjust   ，
        。             。
      ，             ，             ，     ，     Θ(lg(n)) ，   ，             。
  ，    。

MinHeap::Add

               ，       
Smaller，Bigger

MinHeap::Smaller

    /  ：
    [1, nSize]            
  nPos       ，              
    ：
   [1, nSize]          ，
   [1, nSize]            

1.  nPos_ == 1，    
2.   m_arrElements[_nP] <= m_arrElements[nPos_]，    
3. m_arrElements[_nP] > m_arrElements[nPos_]，
  _nP nPos_    。
       ：
    [1, nSize]            
  _nP       ，              
     [1, nSize]          ，   [1, nSize]            
            

  ， Smaller   ，        。             。
      ，             ，             ，     ，     Θ(lg(n)) ，   ，             。

MinHeap::Bigger

  MinHeap::Smaller

시간 복잡 도

            n

구조
MinHeap()

     Θ(1)

MinHeap(const Array::DynArray& arrElements_)

     Θ(nlg(n))

복사 구조

	     Θ(n)

값 을 부여 하 다

     Θ(n)

분석 하여 구성 하 다

     Θ(1)

덧붙이다

     O(lg(n))

삭제

     O(lg(n))

수색 하 다.

     O(n)