#include“SeqHeap.h“

template
SeqHeap::SeqHeap（）
{
	size?=?0;
}

template
SeqHeap::SeqHeap（DataType?arr[]?int?n）
{
	for?（int?i?=?0;?i?		heap[i+1]=arr[i];
	}
	size?=?n;
}

template
SeqHeap::~SeqHeap（）
{
}

template
void?SeqHeap::MakeMaxSeqHeap（SeqHeap?*h）
{
	h->MaxHeapSort（h）;//構建最大頂堆
}

template
void?SeqHeap::MakeMinSeqHeap（SeqHeap?*h）
{
	h->MinHeapSort（h）;//構建最小頂堆
}

template
void?SeqHeap::PrintSeqHeap（SeqHeap?h）
{
	for?（int?i?=?1;?i?<=?size;?i++）?{
		cout?<		if?（i%20?==?0）
			cout?<	}
	cout?<}

template
void?SeqHeap::MaxHeapSort（SeqHeap?*?h）
{
	int?N?=?h->size;
	for?（int?k?=?N?/?2;?k?>=?1;?k--）?{
		SinkConversely（h->heap?k?N）;//此步是堆的構造：構造的結果是部分堆有序，即頭結點的值是最小的。
	}
	while?（N?>?1）
	{
		Swap（h->heap?1?N--）;
		SinkConversely（h->heap?1?N）;
	}
}

template
void?SeqHeap::MinHeapSort（SeqHeap?*h）
{
	int?N?=?h->size;
	for?（int?k?=?N?/?2;?k?>=?1;?k--）?{
		Sink（h->heap?k?N）;//此步是堆的構造：構造的結果是部分堆有序，即頭結點的值是最大的。
	}
	while?（N?>?1）
	{
		Swap（h->heap?1?N--）;
		Sink（h->heap?1?N）;
	}
}

/*
??arr[]：即?h->heap
??????k：把位置為k的結點下沉
????????【該結點的特點：heap[k]???????N：堆里（即heap[]）有N個元素，即?h->size的值
*/
template
void?SeqHeap::Sink（DataType?arr[]?int?k?int?N）
{
	while?（2*k?<=?N）?//當結點k?的子結點2*k?不超過當前數組元素的最大下標時【結點?2*k?是?結點?k?的子結點】，才有機會繼續下沉
	{
		int?j?=?2?*?k;
		if?（j?			j++;
		if?（Less（arr[j]?arr[k]））?break;//also?could?be?!Less（arr[k]?arr[j]）即當?arr[k]>arr[j]時跳出循環體
		Swap（arr?k?j）;
		k?=?j;
	}
}

/*
??arr[]：即?h->heap
??????k：把位置為k的結點上浮【該結點的特點：heap[k]?>?heap[k/2]，即該結點值比其父結點值大?】
??????N：堆里（即heap[]）有N個元素，即?h->size的值
*/
template
void?SeqHeap::Swin（DataType?arr[]?int?k?int?N）
{
	while?（?k>1?&&?Less（arr[k/2]arr[k]）?）//若結點?k?不是根結點、且其值比其父結點大時，循環體進行，結點k上浮
	{
		Swap（arr?k?/?2?k）;
		k?=?k?/?2;
	}
}

template
void?SeqHeap::SinkConversely（DataType?arr[]?int?k?int?N）
{
	while?（2?*?k?<=?N）?//當結點k?的子結點2*k?不超過當前數組元素的最大下標時【結點?2*k?是?結點?k?的子結點】，才有機會繼續下沉
	{
		int?j?=?2?*?k;
		if?（j?			j++;
		if?（Less（arr[k]?arr[j]））?break;//also?could?be?!Less（arr[k]?arr[j]）即當?arr[k]		Swap（arr?k?j）;
		k?=?j;
	}
}

template
void?SeqHeap::SwinConversely（DataType?arr[]?int?k?int?N）
{
	while?（k>1?&&?Less（arr[k?/?2]?arr[k]））//若結點?k?不是根結點、且其值比其父結點小時，循環體進行，結點k上浮
	{
		Swap（arr?k?/?2?k）;
		k?=?k?/?2;
	}
}

template
void?SeqHeap::Swap（DataType?arr[]?int?i?int?j）
{
	DataType?temp?=?arr[i];
	arr[i]?=?arr[j];
	arr[j]?=?temp;
}

template