堆排序(简单的最大优先队列).txt

最大堆的生成、堆排序

//最大堆的调整
{逻辑结构：树状结构--完全二叉树}
{存储结构：顺序表--数组即可反映逻辑结构}
算法思想：
1。前置条件：当前结点i的左子树和右子树都已经是最大堆；设堆的大小为n。
2。结点i左结点的下标l=2*i；结点i右结点的下标r=2*i+1。
3。在l<=n和r<=n的情况下考虑以下操作。
4。如果l结点的值大于i结点的值，则把largest记为l，否则记为i。
5。如果r结点的值大于i结点的值，则把largest记为r。
6。如果largest不等于i，则把i和largest指向的值进行交换，然后对largest指向的结点递归调用本算法，
即重复跳转至步骤2。


//算法描述
AdjustHeap( HeapList, i )  // HeapList为最大堆（顺序表），i为要调整的子树的根结点
	n = HeapSize(heapList);
	l = 2 * i;
	r = 2 * i + 1;
	if l <= n and HeapList[l] > HeapList[i]
		largest = l;
	else  largest = i;
	if r <= n and HeapList[r] > HeapList[largest]
		largest = r;
	if largest != i
	[
		exchange(largest, i);
		AdjustHeap(HeapList, largest);
	]	
{AdjustHeap end}

//算法时间复杂度（最坏）
O(lgn)

//代码实现
// kernel_code
template< typename T >
void	AdjustHeap( 
				   T heapList[], 
				   int nCurrentNodePos, 
				   int nHeapLength 
				   )
{
	int  nSubLeftNodePos = 2 * nCurrentNodePos + 1;
	int  nSubRightNodePos = 2 * nCurrentNodePos + 2;
	int  nLargestNodePos = -1;

	if ( nSubLeftNodePos < nHeapLength && heapList[nSubLeftNodePos] > 
		heapList[nCurrentNodePos] )
	{
		nLargestNodePos = nSubLeftNodePos;
	}
	else  
		nLargestNodePos = nCurrentNodePos;

	if ( nSubRightNodePos < nHeapLength && heapList[nSubRightNodePos] > 
		heapList[nLargestNodePos] )
	{
		nLargestNodePos = nSubRightNodePos;
	}

	if ( nLargestNodePos != nCurrentNodePos )
	{
		T  tempElement = heapList[nLargestNodePos];  // T 要支持拷贝
		heapList[nLargestNodePos] = heapList[nCurrentNodePos];
		heapList[nCurrentNodePos] = tempElement;

		AdjustHeap( heapList, nLargestNodePos, nHeapLength );
	}
}

//测试代码
void	testAdjustHeap( )
{
	const int nLen = 6;
	int  srcArray[nLen] = {2, 56, 4, 8, 30, 42};
	
	// 从底向上,对非叶子结点进行调整
	int  nMidNodeAmount = nLen / 2;
	for ( int nPos = nMidNodeAmount-1; nPos >= 0; nPos -- )
	{
		AdjustHeap<int>( srcArray, nPos, nLen );
	}

	for ( int nPos = 0; nPos < nLen; nPos ++ )
		cout << srcArray[nPos] << " ";

	cout << endl;
}


//建最大堆
{逻辑结构：树状结构--完全二叉树}
{存储结构：顺序表}
算法思想：
从右往左、从底向上，对每个非叶子结点调用调整最大堆算法。

//算法描述
CreateHeap( HeapList )  // HeapList为顺序表
	n = HeapSize(heapList);
	k = LowInt(n/2);  // 向下取整
	for i=k DOWNTO 1
		AdjustHeap(HeapList, i);	
{CreateHeap end}

//算法时间复杂度（最坏）
O(nlgn)

//代码实现
// kernel code
template< typename T >
void	CreateHeap( 
				   T heapList[], 
				   int nHeapLen
				   )
{
	int  nMidNodeMaxPos = nHeapLen / 2;
	for ( int nPos = nMidNodeMaxPos-1; nPos >= 0; nPos -- )
	{
		AdjustHeap<T>( heapList, nPos, nHeapLen );
	}
}


//堆排序
{逻辑结构：树状结构--完全二叉树}
{存储结构：顺序表}
// 算法思想：
1。创建最大堆。
2。设i=HeapSize()。
3。当i>=2时，执行以下操作：
4。把顺序表第一个元素跟第i个元素互换。{第一个元素的左右子树都是最大堆}
5。调用最大堆调整算法：AdjustHeap(heapList, 1)，对第一个元素进行调整。
6。i = i -1，转到步骤3。

//算法描述：
{采用顺序存储结构}
HeapSort( HeapList )  // HeapList为顺序表
	CreateHeap( HeapList );  // HeapList建成最大堆
	i = HeapSize( HeapList );
	while i>=2
	[
		exchange( HeapList[1], HeapList[i] );
		AdjustHeap( HeapList, 1 );
		i = i - 1;
	]
{HeapSort end}

//算法时间复杂度（最坏）
O(nlgn) 

//代码实现：
// kernel code
template< typename T >
void	HeapSort( 
				 T heapList[], 
				 int nHeapLen
				 )
{
	CreateHeap<T>( heapList, nHeapLen );
	
	int  nPos = nHeapLen - 1;
	while ( nPos >= 1 )
	{
		T  temp = heapList[nPos];
		heapList[nPos] = heapList[0];
		heapList[0] = temp;
		
		AdjustHeap<T>( heapList, 0, nPos );

		nPos --;
	}
}

///////////////////////////////////////////////

//最大优先队列--数据类型
{使用最大堆数据结构}
//基本操作：
1。返回优先级最高的元素GetMaximumElement。
2。返回优先级最高的元素并从队列中删除ExtractMaxElement。
3。提高队列中某一元素的优先级InCreaseKey。
4。插入新元素到队列InsertElement。

//GetMaximumElement
//算法思想：取得最大堆的第一个元素即可。
//算法描述：
{使用顺序表存储}
GetMaximumElement( heapList )
	return  heapList[1];
{GetMaximumElement end}
//算法时间复杂度（最坏）
O(1)

//ExtractMaxElement
//算法思想：
1。取得第一个元素并保存，作为返回值。
2。把最后一个元素赋给第一个元素。
3。堆长度减1。
4。对第一个元素调用最大堆调整算法。

//算法描述：
{使用顺序表存储}
ExtractMaxElement( heapList )
	n = HeapSize( heapList );
	if n < 1
		Error("heap underflow");
	max = heapList[1];
	heapList[1] = heapList[n];
	n = n - 1;
	SetHeapListSize( n );
	AdjustHeap( HeapList, 1 );
{ExtractMaxElement end}

//算法时间复杂度（最坏）
O(lgn)

//InCreaseKey
//算法思想：
1。设要提升key的元素的位序为i，i的父结点记为parent(i)。
2。List[i] = key。 // key为提升后的key值
2。当i>1 and List[parent(i)]<List[i] 时，进行如下操作：
3。交换parent(i)和i对应的元素。
4。i = parent(i)。转到步骤2。

//算法描述：
{使用顺序表存储}
InCreaseKey( heapList, i, key )
	if heapList[i] > key
		Error("new key is smaller than current key");
	heapList[i] = key;
	while i>1 and heapList[parent(i)]<heapList[i]
	[
		exchange( heapList[i], heapList[parent(i)] );
		i = parent(i);
	]
{InCreaseKey end}

//算法时间复杂度（最坏）
O(lgn)

//InsertElement
算法思想：
1。堆长度加1。
2。在堆最后加一个值无穷小的元素。
3。对堆最后一个元素调用InCreaseKey算法：InCreaseKey(List, n, key)。//n为堆长度,key为新元素的key值

//算法描述：
{使用顺序表存储}
InsertElement( heapList, key )
	n = HeapSize( heapList );
	n = n + 1;
	SetHeapSize( n );
	heapList[n] = SMALL_VALUE;
	InCreaseKey(heapList, n, key);
{InsertElement end}

//算法时间复杂度（最坏）
O(lgn)


//代码实现一个简陋的最大优先队列：
//MaxPriorityList.h
#pragma  once
#include <cassert>

template< typename T >
void	AdjustHeap_ptrArray( 
							T* heapList[],  // 传递的是指针数组
							int nCurrentNodePos, 
							int nHeapLength 
				   )
{
	int  nSubLeftNodePos = 2 * nCurrentNodePos + 1;
	int  nSubRightNodePos = 2 * nCurrentNodePos + 2;
	int  nLargestNodePos = -1;

	if ( nSubLeftNodePos < nHeapLength && *(heapList[nSubLeftNodePos]) > 
		*(heapList[nCurrentNodePos]) )  
	{
		nLargestNodePos = nSubLeftNodePos;
	}
	else  
		nLargestNodePos = nCurrentNodePos;

	if ( nSubRightNodePos < nHeapLength && *(heapList[nSubRightNodePos]) > 
		*(heapList[nLargestNodePos]) )
	{
		nLargestNodePos = nSubRightNodePos;
	}

	if ( nLargestNodePos != nCurrentNodePos )
	{
		T*  tempPtr = heapList[nLargestNodePos];
		heapList[nLargestNodePos] = heapList[nCurrentNodePos];
		heapList[nCurrentNodePos] = tempPtr;

		AdjustHeap_ptrArray( heapList, nLargestNodePos, nHeapLength );
	}
}


const  int nInitSize = 1000;  // 指针数组初始大小
template<typename ElementType>
class MaxPriorityList
{
	typedef  ElementType  _T;
public:
	MaxPriorityList( );
	virtual ~MaxPriorityList( );

public:
	bool	GetMaximumElement( 
		_T & maxElement
		);

	bool	ExtractMaxElement(
		_T * & pMaxElement
		);

	bool	InCreaseKey(
		int nTargetPos,
		_T &  element
		);

	bool	InsertElement(
		_T * pNewElement
		);

private:
	_T **	m_pMaxHeapList;
	int		m_maxHeapSize;
};

template<typename T>
MaxPriorityList<T>::MaxPriorityList(): m_pMaxHeapList( NULL ),
m_maxHeapSize( 0 )
{
	m_pMaxHeapList = new T*[nInitSize];
	assert( m_pMaxHeapList > 0 );
}

template<typename T>
MaxPriorityList<T>::~MaxPriorityList()
{
	if ( m_pMaxHeapList != NULL )
	{
		for ( int nPos = 0; nPos < m_maxHeapSize; nPos ++ )
		{
			T * pElement = m_pMaxHeapList[nPos];
			if ( pElement != NULL )
			{
				delete pElement;
				pElement = NULL;
			}
		}
		m_pMaxHeapList = NULL;
	}
	delete [] m_pMaxHeapList;
	m_pMaxHeapList = NULL;
}

template<typename T>
bool	MaxPriorityList<T>::GetMaximumElement( 
	_T & maxElement
	)
{
	if ( m_maxHeapSize < 1 )
		return false;

	maxElement = *(m_pMaxHeapList[0]);
	return true;
}

template<typename T>
bool	MaxPriorityList<T>::ExtractMaxElement(
	_T * & pMaxElement
	)
{
	if ( m_maxHeapSize < 1 )
		return false;

	pMaxElement = m_pMaxHeapList[0];

	m_pMaxHeapList[0] = m_pMaxHeapList[m_maxHeapSize - 1];
	m_maxHeapSize --;
	AdjustHeap_ptrArray<T>(m_pMaxHeapList, 0, m_maxHeapSize );

	return true;
}

template<typename T>
bool	MaxPriorityList<T>::InCreaseKey(
										int nTargetPos, // 位序
										_T & element  // 目标元素
										)
{
	assert( nTargetPos >= 0 && nTargetPos < m_maxHeapSize );
	if ( nTargetPos < 0 || nTargetPos >= m_maxHeapSize )
		return false;

	if ( *(m_pMaxHeapList[nTargetPos]) > element ) // 实际比较的是key
		return false;

	*(m_pMaxHeapList[nTargetPos]) = element;  // be careful: 拷贝
	int  nCurrentPos = nTargetPos;
	while ( nCurrentPos > 0 && 
		*(m_pMaxHeapList[nCurrentPos/2]) < *(m_pMaxHeapList[nCurrentPos]))
	{
		T  temp = *(m_pMaxHeapList[nCurrentPos/2]);
		*(m_pMaxHeapList[nCurrentPos/2]) = *(m_pMaxHeapList[nCurrentPos]);
		*(m_pMaxHeapList[nCurrentPos]) = temp;

		nCurrentPos = nCurrentPos / 2;
	}

	return true;
}

template<typename T>
bool	MaxPriorityList<T>::InsertElement(
	_T * pNewElement
	)
{
	m_maxHeapSize ++;
	const double	MIN_VALUE = -35698.23;
	m_pMaxHeapList[m_maxHeapSize - 1] = pNewElement;
	// 调整
	int nCurrentPos = m_maxHeapSize - 1;
	while ( nCurrentPos > 0 &&
		*(m_pMaxHeapList[nCurrentPos/2]) < *(m_pMaxHeapList[nCurrentPos]) )
	{
		T  temp = *(m_pMaxHeapList[nCurrentPos/2]);
		*(m_pMaxHeapList[nCurrentPos/2]) = *(m_pMaxHeapList[nCurrentPos]);
		*(m_pMaxHeapList[nCurrentPos]) = temp;

		nCurrentPos = nCurrentPos / 2;
	}

	return true;
}

// .cpp 测试代码
#include "stdafx.h"

#include "MaxPriorityList.h"  
#include <iostream>
using namespace std;

// 假设数据元素包含两个域: double key; int handle;
class	ElementNode
{
public:
	ElementNode( )
	{
		m_key = 0.0;
		m_realObjectHandle = 0;
	}

	ElementNode( double key, int nRealObjectHandle ):
	m_key( key ), m_realObjectHandle( nRealObjectHandle )
	{
	}

	virtual ~ElementNode( ){};

public:
	bool	operator<( const ElementNode & otherElementNode ) const
	{
		return m_key < otherElementNode.m_key;
	}

	bool	operator>( const ElementNode & otherEelmentNode ) const
	{
		return m_key > otherEelmentNode.m_key;
	}

	bool	operator<( double key )
	{
		return m_key < key;
	}

	void	operator=( double key )
	{
		m_key = key;
	}

	double	GetKey( ) 
	{
		return m_key;
	}

	int		GetHandle( )
	{
		return m_realObjectHandle;
	}

private:
	double  m_key;
	int		m_realObjectHandle;
};

void	testMaxPriorityList()
{
	MaxPriorityList<ElementNode>  maxPriorityList;

	const int  nCount = 10;
	for ( int nPos = 1; nPos <= nCount; nPos ++ )
	{
		ElementNode * pNewElement = new ElementNode( nPos * 4.35, nPos );
		assert( pNewElement != NULL );
		if ( pNewElement == NULL )
			return;
		maxPriorityList.InsertElement( pNewElement );
	}

	const int  nExtractAmount = 5;
	for ( int nPos = 1; nPos <= nExtractAmount; nPos ++ )
	{
		ElementNode * pTempElement = NULL;
		bool bIsOk = maxPriorityList.ExtractMaxElement( pTempElement );
		if ( bIsOk )
		{
			assert( pTempElement != NULL );
			if ( pTempElement != NULL )
			{
				cout << pTempElement->GetKey() << " " << pTempElement->GetHandle() << endl;
				delete pTempElement;
				pTempElement = NULL;
			}
		}
		else
		{
			cout << nPos << " no extract" << endl;
		}
	}
	cout << "*******************" << endl;

	// add new node
	const int nNewAddAmount = 6;
	for ( int nPos = 1; nPos <= nNewAddAmount; nPos ++ )
	{
		ElementNode * pNewElement = new ElementNode( nPos * 10.23, nPos*10 );
		assert( pNewElement != NULL );
		if ( pNewElement == NULL )
			return;
		maxPriorityList.InsertElement( pNewElement );
	}

	// extract again
	const int  nExtractAmountTwice = nNewAddAmount + nCount - nExtractAmount;
	for ( int nPos = 1; nPos <= nExtractAmountTwice; nPos ++ )
	{
		ElementNode * pTempElement = NULL;
		bool bIsOk = maxPriorityList.ExtractMaxElement( pTempElement );
		if ( bIsOk )
		{
			assert( pTempElement != NULL );
			if ( pTempElement != NULL )
			{
				cout << pTempElement->GetKey() << " " << pTempElement->GetHandle() << endl;
				delete pTempElement;
				pTempElement = NULL;
			}
		}
		else
		{
			cout << nPos << " no extract" << endl;
		}
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	testMaxPriorityList( );

	return 0;
}

//****************************************