C++堆排序
时间：2010-04-18 来源：ispexceed
堆排序堆排序是使用堆这个数据结构作为基础的，是一种在最坏情况下时间复杂度可以达到O(nlogn)的排序算法，堆是优先队列的基础，应用情况很广泛，比如可以把爬虫URL队列存放在一个优先队列中，每次计算每个URL的权值，下一次抓取的网页对应的是当前队列中权值最大的URL。
为了简单起见，本文只对整型数处理，其它的可以通过模板进行扩展。这里实现的是最大堆，最小堆同理。
/*************************** 头文件 Heap.h ***************************/
#ifndef _HEAP_H
#define _HEAP_H
#include <memory.h>
class CHeap
{
public:
CHeap(int heapCapacity) : _mHeapCapacity(heapCapacity)
{
_mHeap = new int[_mHeapCapacity];
memset(_mHeap, 0, _mHeapCapacity);
}
~CHeap() { delete _mHeap; }
void BuildMaxHeap(const char *filePath);
void MaxHeapify(int i);
void HeapSort();
void PrintResult();
private:
int _mHeapSize;
int _mRealSize;
int _mHeapCapacity;
int *_mHeap;
int LeftChild(int i) { return 2 * i + 1; }
int RightChild(int i) { return 2 * (i + 1); }
void Swap(int &a, int &b) { int tmp = a; a = b; b = tmp; }
};
#endif
/*********************** Heap.cpp ***********************/
#include "Heap.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int main()
{
const char *filePath = "data.txt";
CHeap heap(20);
heap.BuildMaxHeap(filePath);
heap.HeapSort();
heap.PrintResult();
return 0;
}
void CHeap::BuildMaxHeap(const char *filePath)
{
ifstream infile(filePath);
if (infile)
{
//cout << "Open file succeed." << endl;
string line;
int i = 0;
while (infile >> line)
{
_mHeap[i] = atoi(line.c_str());
++i;
if (i > _mHeapCapacity)
break;
}
_mHeapSize = _mRealSize = i;
infile.close(); // close the file descriptor
for (i = (_mHeapSize - 2) / 2; i >= 0; --i)
{
MaxHeapify(i);
}
}
}
void CHeap::MaxHeapify(int i)
{
int left = LeftChild(i);
int right = RightChild(i);
int max = i;
if (left < _mHeapSize && _mHeap[max] < _mHeap[left])
{
max = left;
}
if (right < _mHeapSize && _mHeap[max] < _mHeap[right])
{
max = right;
}
if (max != i)
{
Swap(_mHeap[i], _mHeap[max]);
MaxHeapify(max);
}
}
void CHeap::HeapSort()
{
for (int i = _mHeapSize - 1; i > 0; --i)
{
Swap(_mHeap[0], _mHeap[i]);
--_mHeapSize;
MaxHeapify(0);
}
}
void CHeap::PrintResult()
{
cout << "Total number of digits is: " << _mRealSize << endl;
for (int i = 0; i < _mRealSize; ++i)
{
cout << _mHeap[i] << endl;
}
}
/////////////////// data.txt //////////////////
23
34
56
...
...
堆排序的算法原理很简单，但实际应用却很广泛。
相关阅读 更多 +
