优先级队列及小顶堆排序

优先级队列及小顶堆排序实现

/** @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;

}

//不足之处，欢迎指正。