優先級隊列及小頂堆排序

優先級隊列及小頂堆排序實現

/** @file          HeapSort.h

*  @copyright     personal

*  @brief         優先級隊列及堆排序

*  @version       V1.0.0

*  @author        fangyuan

*  @date          2015/12/31

*  @note          測試版本

*/

#include "iostream"

using namespace std;

template<class T>

class CPriQueue

{

private:

int m_iIndex;

int m_iMaxsize;

T* m_pArray;

void swap(int i ,int j)

{

T t;

t = m_pArray[i];

m_pArray[i] = m_pArray[j];

m_pArray[j] = t;

}

void siftup()

{

int p;

for(int i = m_iIndex; i > 1 && m_pArray[p=i/2] > m_pArray[i]; i = p)

{

swap(p,i);

}

}

void siftdown()

{

int c;

for(int i = 1; (c=2*i) <= m_iIndex; i = c)//循環條件，有左結點

{

if(c+1 <= m_iIndex && m_pArray[c+1] < m_pArray[c])//右結點存在，且值比左結點小

{

c++;

}

if(m_pArray[i] <= m_pArray[c]) //當前結點值不大于左結點值，跳出循環

{

break;

}

swap(c,i);

}

}

public:

CPriQueue(int m)

{

m_iMaxsize = m;

m_pArray = new T[m_iMaxsize+1];

m_iIndex = 0;

}

void insert(T t)

{

if(m_iIndex >= m_iMaxsize)

{

cout << "堆大小超過最大值" << endl;

return;

}

m_pArray[++m_iIndex] = t;

siftup();//保持堆性質

}

T extract()

{

T value;

if(m_iIndex < 1)

{

cout << "此堆為空" << endl;

}

else

{

value = m_pArray[1];

m_pArray[1] = m_pArray[m_iIndex--];

siftdown();

}

return value;

}

//在原空間上進行排序，只使用一個單位額外空間

void heapSort()

{

int n = m_iIndex;//為了重用siftdown()

while(m_iIndex > 1)

{

swap(1,m_iIndex--);

siftdown();

}

m_iIndex = n;

}

void print()

{

for(int i = 1; i <= m_iIndex; ++i)

{

cout << m_pArray[i] << "\t";

}

cout << endl;

}

};

//優先級隊列及堆排序測試

void priqueueTest()

{

CPriQueue<int> cp(100);

int value;

cout << "請輸入需要插入堆的整數" << endl;

while(cin>>value)

{

cp.insert(value);

}

cp.print();

cout << cp.extract() << endl;

cp.print();

cp.heapSort();

cp.print();

}

int main()

{

//優先級隊列

priqueueTest();

system("pause");

return 0;

}

//不足之處，歡迎指正。