序
本文主要介绍堆排序算法（HeapSort），堆排序像合并排序而不像插入排序，堆排序的运行时间为O(nlgn)；像插入排序而不像合并排序，它是一种原地(in place)排序算法。在任何时候，数组中只有常数个元素存储在输入数组以外，这样，堆排序就把插入排序和合并排序的优点结合起来。
堆排序还引入了另外一种算法设计技术，利用某种数据结构(在此算法中为“堆”)来管理算法执行中的信息。堆数据结构不只在堆排序算法中有用，还可以构成一个有效的优先队列。堆数据结构是一种数组对象，它可以被视为一颗完全二叉树，树种每个结点与数组中存放该结点值的那个元素对应。树的每一层都是填满的，最后一层除外(最后一层从一个结点的左子树开始填)。
堆数据结构在最大（最小）优先级队列中得到有效的应用，本文以大顶堆为例，详细给出堆排序算法的实现以及最大级优先队列的算法实现。
git代码
GitHub chapter 6 程序代码下载
堆数据结构
堆数据结构是一种数组抽象，它可以被看做一颗完全二叉树，树中每个结点与数组中存放该结点值的那个元素对应。除了堆顶根节点之外，所有树结点都有父节点，同理，除了叶子结点外，所有树结点都至少有一个儿子结点。
//求左儿子结点
int Left(int i)
{
return 2 * i;
}
//求右儿子结点
int Right(int i)
{
return 2 * i + 1;
}
//求父节点
int Parent(int i)
{
return i / 2;
}在堆排序算法中，有以下几个关键步骤：
MaxHeapify过程，其运行时间为O(logn)，是保持最大堆性质的关键；
BuildMaxHeap过程，建立大顶堆，在无序的原始数组中构造出一颗大顶堆；
HeapSort过程，对大顶堆从最后一个叶子结点开始处理排序，得到一组升序排列的序列。
堆排序算法实现
(1) MaxHeap.h
#ifndef MAX_HEAP_H
#define MAX_HEAP_H
/*
* 大顶堆 MaxHeap 数据结构
*/
#include <iostream>
using namespace std;
class MaxHeap
{
public:
MaxHeap(int *data, int size);
~MaxHeap();
void maxHeapSort();
void displayList(int size)
{
for (int i = 0; i < size; i++)
cout << m_dataList[i] << " ";
cout << endl;
}
private:
int *m_dataList;
int m_heapSize;
void buildMaxHeap(int *data);
void maxHeapify(int *data, int i);
int Left(int i)
{
return 2 * i;
}
int Right(int i)
{
return 2 * i + 1;
}
void swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
};
#endif(2)MaxHeap.cpp
#include "MaxHeap.h"
#include <iostream>
using namespace std;
MaxHeap::MaxHeap(int *data, int size) :m_dataList(data), m_heapSize(size)
{}
MaxHeap::~MaxHeap()
{
delete m_dataList;
}
void MaxHeap::buildMaxHeap(int *data)
{
for (int i = m_heapSize / 2; i >= 1; i--)
{
maxHeapify(data, i);
}
}
void MaxHeap::maxHeapify(int *data, int i)
{
int largest;
int left = Left(i);
int right = Right(i);
if (left <= m_heapSize && data[left-1] > data[i-1])
largest = left;
else
largest = i;
if (right <= m_heapSize && data[right-1] > data[largest-1])
largest = right;
if (largest != i)
{
swap(data[i - 1], data[largest - 1]);
maxHeapify(data, largest);
}
}
void MaxHeap::maxHeapSort()
{
buildMaxHeap(m_dataList);
int length = m_heapSize;
for (int i = length; i >= 1; i--)
{
swap(m_dataList[i - 1], m_dataList[0]);
m_heapSize--;
maxHeapify(m_dataList, 1);
}
}(3)main.cpp
#include "MaxHeap.h"
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
const int N = 10;
int main()
{
//声明一个待排序数组
int array[N];
//设置随机化种子，避免每次产生相同的随机数
srand(time(0));
for (int i = 0; i<N; i++)
{
array[i] = rand() % 101;//数组赋值使用随机函数产生1-100之间的随机数
}
//调用堆排序函数对该数组进行排序
MaxHeap *maxHeap = new MaxHeap(array, N);
cout << "排序前：" << endl;
maxHeap->displayList(N);
maxHeap->maxHeapSort();
cout << endl << "排序后：" << endl;
maxHeap->displayList(N);
system("pause");
return 0;
}测试结果：
最大优先级队列
优先级队列是一种用来维护一组元素构成的集合元素的数据结构，这一组元素中的每一个都有关键字key，分为最大优先级队列和最小优先级队列两种。
本章集中讨论了基于最大堆实现的最大优先级队列。
一个最大优先级队列有以下关键操作：
Insert(x) : 将关键字x插入集合，并保持集合的性质；
MaxiMum()：返回集合中最大关键字的元素，对于最大优先级队列，队头元素即是最大关键字元素；
ExtractMax() ： 去掉并返回队列集合中最大关键字的元素；
IncreaseKey(x , k) : 将元素位置x处的关键字值增加到k ， k 本值不可小于x位置元素的初始值；
算法实现：
（1） MaxPriQueue.h
#ifndef _MAXPRIQUEUE_H_
#define _MAXPRIQUEUE_H_
/*
* 最大堆实现的最大优先级队列数据结构
*/
#include <iostream>
using namespace std;
class MaxPriQueue{
public:
MaxPriQueue(int *data, int size);
~MaxPriQueue();
//将元素x插入该优先级队列
void insert(int x);
//去掉并返回队列中具有最大关键字的元素
int extractMax();
//将元素x的关键字的值增加到k
void increaseKey(int x, int k);
void maxHeapify(int *data, int i);
int MaxiMum()
{
return m_dataList[0];
}
void displayList()
{
for (int i = 0; i < m_queueSize; i++)
cout << m_dataList[i] << " ";
cout << endl;
}
private:
int *m_dataList;
int m_queueSize; //优先级当前长度
//求左儿子结点
int Left(int i)
{
return 2 * i;
}
//求右儿子结点
int Right(int i)
{
return 2 * i + 1;
}
//求父节点
int Parent(int i)
{
return i / 2;
}
void swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
void buildMaxHeap(int *data);
};
#endif(2) MaxPriQueue.cpp
#include "MaxPriQueue.h"
#include <iostream>
using namespace std;
//构造函数
MaxPriQueue::MaxPriQueue(int *data, int size) :m_dataList(data), m_queueSize(size)
{
//构建大顶堆
buildMaxHeap(m_dataList);
}
MaxPriQueue::~MaxPriQueue()
{
delete m_dataList;
}
void MaxPriQueue::buildMaxHeap(int *data)
{
//从最后一个根元素自底向上调整
for (int i = m_queueSize / 2; i >= 1; i--)
maxHeapify(data, i);
}
int MaxPriQueue::extractMax()
{
if (m_queueSize < 1)
return -1;
int max = m_dataList[0];
m_dataList[0] = m_dataList[m_queueSize - 1];
m_queueSize--;
maxHeapify(m_dataList, 1);
return max;
}
void MaxPriQueue::increaseKey(int x, int k)
{
if (k < m_dataList[x-1])
return;
m_dataList[x-1] = k;
//自底向上调整大顶堆
while (x > 1 && m_dataList[Parent(x)-1] < m_dataList[x-1])
{
swap(m_dataList[Parent(x)-1], m_dataList[x-1]);
x = Parent(x);
}
}
void MaxPriQueue::insert(int x)
{
m_queueSize++;
m_dataList[m_queueSize - 1] = x-1;
increaseKey(m_queueSize, x);
}
void MaxPriQueue::maxHeapify(int *data, int i)
{
int largest;
int left = Left(i);
int right = Right(i);
if (left <= m_queueSize && data[left - 1] > data[i - 1])
largest = left;
else
largest = i;
if (right <= m_queueSize && data[right - 1] > data[largest - 1])
largest = right;
if (largest != i)
{
swap(data[i - 1], data[largest - 1]);
maxHeapify(data, largest);
}
}(3) main.cpp
#include "MaxPriQueue.h"
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
const int N = 10;
int main()
{
//声明一个待排序数组
int array[N];
//设置随机化种子，避免每次产生相同的随机数
srand(time(0));
for (int i = 0; i<N; i++)
{
array[i] = rand() % 101;//数组赋值使用随机函数产生1-100之间的随机数
}
//调用堆排序函数对该数组进行排序
MaxPriQueue *maxPriQueue = new MaxPriQueue(array, N);
cout << "大顶堆：" << endl;
maxPriQueue->displayList();
cout << "堆顶元素" << maxPriQueue->MaxiMum() << endl;
cout << "删除最大元素" << maxPriQueue->extractMax() << endl;
cout << "新的大顶堆：" << endl;
maxPriQueue->displayList();
cout << "将队头元素增加至100." << endl;
maxPriQueue->increaseKey(1, 100);
cout << "新的大顶堆：" << endl;
maxPriQueue->displayList();
system("pause");
return 0;
}测试结果：
