堆排序

C++堆排序

    堆排序堆排序是使用堆这个数据结构作为基础的，是一种在最坏情况下时间复杂度可以达到O(nlogn)的排序算法，堆是优先队列的基础，应用情况很广泛，比如可以把爬虫URL队列存放在一个优先队列中，每次计算每个URL的权值，下一次抓取的网页对应的是当前队列中权值最大的URL。

 

为了简单起见，本文只对整型数处理，其它的可以通过模板进行扩展。这里实现的是最大堆，最小堆同理。

 

/*************************** 头文件 Heap.h ***************************/

#ifndef _HEAP_H

#define _HEAP_H

#include 

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 

#include 

#include 

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

...

...

 

堆排序的算法原理很简单，但实际应用却很广泛。