데이터 구조 - 더미 의 기본 조작 과 응용

(1) 모방 함수 로 많은 작은 무 더 기 를 실현 한다.
데이터 쌓 기 구 조 는 일종 의 배열 대상 으로 완전 이 진 트 리 구조 로 볼 수 있다.
더미 구조의 이 진 트 리 저장 소 는?
최대 더미: 모든 부모 노드 는 아이 노드 보다 크다.
최소 더미: 모든 부모 노드 는 아이 노드 보다 작 습 니 다.
모방 함수 (functor) 는 하나의 종류의 사용 을 하나의 함수 처럼 보이 게 하 는 것 이다.그 실현 은 바로 클래스 에서 하나의 operator () 를 실현 하 는 것 이다. 이런 유형 은 유사 한 함수 의 행 위 를 하 는데 바로 모방 함수 류 이다.크 고 작은 무 더 기 를 실현 하 는 과정 에서 일부 기능 의 코드 는 서로 다른 구성원 함수 에서 사용 되 는데 이 코드 를 다시 사용 하려 면 두 가지 경로 가 있다.
 1) 공공 함수, 이것 은 해결 방법 이지 만 함수 에 사용 되 는 일부 변 수 는 공공 전역 변수 가 될 수 있 습 니 다. 그리고 이런 코드 를 재 활용 하기 위해 서 는 함수 만 세 워 야 합 니 다. 유지 하기 도 쉽 지 않 습 니 다.
 2) 모방 함수, 간단 한 클래스 를 작성 합 니 다. 하나의 클래스 를 유지 하 는 구성원 함 수 를 제외 하고 하나의 operator () 만 실현 합 니 다. 클래스 를 예화 할 때 사용 할 '비 매개 변수 요소' 를 클래스 에 전달 합 니 다.
C + + 에서 우 리 는 하나의 클래스 에서 괄호 연산 자 를 다시 불 러 오 는 방법 을 통 해 일반 함수 가 아 닌 함수 대상 을 사용 합 니 다.

Heap.h

#include <iostream>  
#include <algorithm>  
  
using namespace std;  
template<typename T>  
class display  
{  
public:  
    void operator()(const T &x)  
    {  
        cout<<x<<" ";   
    }   
};   
  
  
int main()  
{  
    int ia[]={1,2,3,4,5};  
    for_each(ia,ia+5,display<int>());   
      
    return 0;   
}

모방 함수 로 큰 무더기, 작은 무더기 의 기본 구 조 를 실현 하 다.

#include<iostream>
#include<vector>
using namespace std;

template<class T>
struct Less//  
{
	bool operator()(const T&l,const T&r)
	{
	return l<r;
	}
};

template<class T>
struct Greater
{
	bool operator()(const T&l,const T&r)
	{
	return l>r;
	}
};
template<class T,class Comper=Greater<T>>//     
class Heap
{
private:
	vector<T> _a;
public:

	Heap(const T* a,size_t size)
	{
		assert(a);
		//           
		for(i=0;i<size;i++)
		{
		_a.push_back(a[i]);
		}
		//   
		for(int i=(_a.size()-2)/2;i>=0;i--)
		{
		//    
		_AdjustDown(i);
		}
	}
	//       
	void push(const T& x)
	{
	_a.push_back (x);
	_Adjustup(_a.size()-1)
	}
/********************
            
                      ，
         ,       
************************/
	void pop()
	{
	swap(_a[0],_a[_a.size()-1]);
	_a.pop_back ();
	_AdjustDown(0);
	}
	size_t Size()//     
	{
	  return _a.size();
	}

	bool Empty()//     
	{
	return _a.empty();
	}
protected:
	void _AdjustDown(size_t parent)
	{
		size_t child=2*parent+1;
		while(child<_a.size())
		{
			Comper com;
			//            
			if(com(_a[child+1],_a[child]) && child+1<_a.size())//                  
			{
			child=child+1;
			}
			//                 
			if(com(_a[child],_a[parent]))
			{
			swap(_a[child],_a[parent]);
			parent=child;
			child=2*parent+1;
			}
			//       ，    
			else
			{
			break;
			}
		}
	
	}

	//    
	void _Adjustup(size_t child)
	{
		 size_t parent=(child-1)/2;
		 while(child>0)//    while(parent>0),  child size_t   ，      
		 {
			 Comper com;
			 //             ，   
			 if(com(_a[child],_a[parent]))
			 {
			 swap(_a[child],_a[parent]);
			 child=parent;
			 parent=(child-1)/2;
			 }
			 //      ，    
			 else
			 {
			 break;
			 }
		 }
	}
};

                                     (2) 더미 정렬 

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<assert.h>
using namespace std;

//   ，  
void AdjustDown(int a[],int n,int parent)
{
	int child=parent*2+1;
	while(child<n)
	{
		if(child+1<n&&a[child]<a[child+1])
		{
		++child;
		}

		if(a[child]>a[parent])
		{
		swap(a[child],a[parent]);
		parent=child;
		child=parent*2+1;
		}
		else
		{
		break;
		}
	}
}

void HeapSort(int a[],int n)
{
	assert(a);
	//   
	for(int i=(n-2)/2;i>=0;i--)
	{
	AdjustDown(a,n,i);
	}
	//           ,       N-i            
	for(int i=n-1;i>0;i--)
	{
	swap(a[0],a[i]);
	AdjustDown(a,i,0);
	}

}

void test()
{
	int a[8]={98,77,35,62,55,14,35,48};
	int size=sizeof(a)/sizeof(a[0]);
	HeapSort(a,size);
	for(int i=0;i<size;i++)
	{
	cout<<a[i]<<" ";

	}
	cout<<endl;
}
int main()
{
	test();
	system("pause");
	return 0;

}