?? 堆排序(簡(jiǎn)單的最大優(yōu)先隊(duì)列).txt
字號(hào):
//最大堆的調(diào)整
{邏輯結(jié)構(gòu)：樹(shù)狀結(jié)構(gòu)--完全二叉樹(shù)}
{存儲(chǔ)結(jié)構(gòu)：順序表--數(shù)組即可反映邏輯結(jié)構(gòu)}
算法思想：
1。前置條件：當(dāng)前結(jié)點(diǎn)i的左子樹(shù)和右子樹(shù)都已經(jīng)是最大堆；設(shè)堆的大小為n。
2。結(jié)點(diǎn)i左結(jié)點(diǎn)的下標(biāo)l=2*i；結(jié)點(diǎn)i右結(jié)點(diǎn)的下標(biāo)r=2*i+1。
3。在l<=n和r<=n的情況下考慮以下操作。
4。如果l結(jié)點(diǎn)的值大于i結(jié)點(diǎn)的值，則把largest記為l，否則記為i。
5。如果r結(jié)點(diǎn)的值大于i結(jié)點(diǎn)的值，則把largest記為r。
6。如果largest不等于i，則把i和largest指向的值進(jìn)行交換，然后對(duì)largest指向的結(jié)點(diǎn)遞歸調(diào)用本算法，
即重復(fù)跳轉(zhuǎn)至步驟2。
//算法描述
AdjustHeap( HeapList, i ) // HeapList為最大堆（順序表），i為要調(diào)整的子樹(shù)的根結(jié)點(diǎn)
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}
//算法時(shí)間復(fù)雜度（最壞）
O(lgn)
//代碼實(shí)現(xiàn)
// 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 );
}
}
//測(cè)試代碼
void testAdjustHeap( )
{
const int nLen = 6;
int srcArray[nLen] = {2, 56, 4, 8, 30, 42};
// 從底向上,對(duì)非葉子結(jié)點(diǎn)進(jìn)行調(diào)整
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;
}
//建最大堆
{邏輯結(jié)構(gòu)：樹(shù)狀結(jié)構(gòu)--完全二叉樹(shù)}
{存儲(chǔ)結(jié)構(gòu)：順序表}
算法思想：
從右往左、從底向上，對(duì)每個(gè)非葉子結(jié)點(diǎn)調(diào)用調(diào)整最大堆算法。
//算法描述
CreateHeap( HeapList ) // HeapList為順序表
n = HeapSize(heapList);
k = LowInt(n/2); // 向下取整
for i=k DOWNTO 1
AdjustHeap(HeapList, i);
{CreateHeap end}
//算法時(shí)間復(fù)雜度（最壞）
O(nlgn)
//代碼實(shí)現(xiàn)
// 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 );
}
}
//堆排序
{邏輯結(jié)構(gòu)：樹(shù)狀結(jié)構(gòu)--完全二叉樹(shù)}
{存儲(chǔ)結(jié)構(gòu)：順序表}
// 算法思想：
1。創(chuàng)建最大堆。
2。設(shè)i=HeapSize()。
3。當(dāng)i>=2時(shí)，執(zhí)行以下操作：
4。把順序表第一個(gè)元素跟第i個(gè)元素互換。{第一個(gè)元素的左右子樹(shù)都是最大堆}
5。調(diào)用最大堆調(diào)整算法：AdjustHeap(heapList, 1)，對(duì)第一個(gè)元素進(jìn)行調(diào)整。
6。i = i -1，轉(zhuǎn)到步驟3。
//算法描述：
{采用順序存儲(chǔ)結(jié)構(gòu)}
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}
//算法時(shí)間復(fù)雜度（最壞）
O(nlgn)
//代碼實(shí)現(xiàn)：
// 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 --;
}
}
///////////////////////////////////////////////
//最大優(yōu)先隊(duì)列--數(shù)據(jù)類型
{使用最大堆數(shù)據(jù)結(jié)構(gòu)}
//基本操作：
1。返回優(yōu)先級(jí)最高的元素GetMaximumElement。
2。返回優(yōu)先級(jí)最高的元素并從隊(duì)列中刪除ExtractMaxElement。
3。提高隊(duì)列中某一元素的優(yōu)先級(jí)InCreaseKey。
4。插入新元素到隊(duì)列InsertElement。
//GetMaximumElement
//算法思想：取得最大堆的第一個(gè)元素即可。
//算法描述：
{使用順序表存儲(chǔ)}
GetMaximumElement( heapList )
return heapList[1];
{GetMaximumElement end}
//算法時(shí)間復(fù)雜度（最壞）
O(1)
//ExtractMaxElement
//算法思想：
1。取得第一個(gè)元素并保存，作為返回值。
2。把最后一個(gè)元素賦給第一個(gè)元素。
3。堆長(zhǎng)度減1。
4。對(duì)第一個(gè)元素調(diào)用最大堆調(diào)整算法。
//算法描述：
{使用順序表存儲(chǔ)}
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}
//算法時(shí)間復(fù)雜度（最壞）
O(lgn)
//InCreaseKey
//算法思想：
1。設(shè)要提升key的元素的位序?yàn)閕，i的父結(jié)點(diǎn)記為parent(i)。
2。List[i] = key。 // key為提升后的key值
2。當(dāng)i>1 and List[parent(i)]<List[i] 時(shí)，進(jìn)行如下操作：
3。交換parent(i)和i對(duì)應(yīng)的元素。
4。i = parent(i)。轉(zhuǎn)到步驟2。
//算法描述：
{使用順序表存儲(chǔ)}
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}
//算法時(shí)間復(fù)雜度（最壞）
O(lgn)
//InsertElement
算法思想：
1。堆長(zhǎng)度加1。
2。在堆最后加一個(gè)值無(wú)窮小的元素。
3。對(duì)堆最后一個(gè)元素調(diào)用InCreaseKey算法：InCreaseKey(List, n, key)。//n為堆長(zhǎng)度,key為新元素的key值
//算法描述：
{使用順序表存儲(chǔ)}
InsertElement( heapList, key )
n = HeapSize( heapList );
n = n + 1;
SetHeapSize( n );
heapList[n] = SMALL_VALUE;
InCreaseKey(heapList, n, key);
{InsertElement end}
//算法時(shí)間復(fù)雜度（最壞）
O(lgn)
//代碼實(shí)現(xiàn)一個(gè)簡(jiǎn)陋的最大優(yōu)先隊(duì)列：
//MaxPriorityList.h
#pragma once
#include <cassert>
template< typename T >
void AdjustHeap_ptrArray(
T* heapList[], // 傳遞的是指針數(shù)組
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; // 指針數(shù)組初始大小
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 // 目標(biāo)元素
)
{
assert( nTargetPos >= 0 && nTargetPos < m_maxHeapSize );
if ( nTargetPos < 0 || nTargetPos >= m_maxHeapSize )
return false;
if ( *(m_pMaxHeapList[nTargetPos]) > element ) // 實(shí)際比較的是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;
// 調(diào)整
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 測(cè)試代碼
#include "stdafx.h"
#include "MaxPriorityList.h"
#include <iostream>
using namespace std;
// 假設(shè)數(shù)據(jù)元素包含兩個(gè)域: 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;
}
//****************************************
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -