《算法导论》第六章 堆排序 C++实现

1.）和第一部分的实现不同，这次用类来实现，毕竟类才是C++的精华。

使用类相对面向过程有不少好处：

• 函数的参数简化不少，类成员的隐含this指针使得vector容器的应用传递作参数全部可以省去。
• 将elemQueue， priQueue，heapSize作为PriorityQueue的数据成员后，特别是heapSize，在其间的数值关系上简单不少。
  2.）同样使用vector做容器，其实vector本身已经支持insert,sort等操作，这里只是将其做容器使用，除了迭代器，push_back，size外不使用其它成员。另外，使用vector而不是底层的数组，可能会对算法的时间有影响，不过说到算法分析我就头痛，就不考虑那么多了==！

3.）这章分为堆排序和优先级队列两部分，综合后，堆排序部分也是在元素+优先级的数据结构下进行的排序，而非纯数组排序。

4.)《算法导论》书中的伪代码有些需要注意的地方：

• 所有的下标都是从1开始，而实际编程时数组下标是从0开始的，这点差异造成了不少麻烦。
• 伪代码中的downto和to在不同的前后环境下，循环上界和下届可能为>=,>,<=,<，是否=具体情况需具体分析，属于一个容易中枪的地方。

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <string>
#include <limits>
using namespace std;
class PriorityQueue
{
public:
truePriorityQueue() { };
true~PriorityQueue() { };
trueint getParent(int i) { return (i - 1) / 2; } // 数组下标由0开始与书中从1开始不同！
trueint getLeftChild(int i) { return i * 2 + 1; }
trueint getRightChild(int i) { return i * 2 + 2; }
trueinline void addElem(string, int); // 由输入初始化队列
truevoid swapTwoElem(int, int);
truevoid iniHeapSize() { heapSize = elemQueue.size() - 1; }
truevoid display();

truevoid maxHeapify(int); // 使以参数为根的子树成为最大堆
truevoid buildMaxHeap(); // 构建最大堆

truevoid heapSort(); // 堆排序

true// 优先级队列
trueconst string getElemVal(int elemIndex) { return elemQueue[elemIndex]; }
trueconst int getElemPriVal(int elemIndex) { return priQueue[elemIndex]; }

trueconst string maximum() { return getElemVal(0); } // 返回具有最大优先级的元素
truevoid extractMax(); // 去掉并返回具有最大优先级的元素
truevoid increaseKey(int, int); // 提升优先级的值
truevoid heapInsert(string, int); // 插入优先级为num的元素
truevoid heapDelete(int); // 通过下标删除元素（练习6.5-7）
truevoid heapDelete(string); // 通过元素值删除元素（练习6.5-7）

private:
truevector<string> elemQueue; // 时间队列
truevector<int> priQueue; // 事件优先级队列
truevector<int>::size_type heapSize; // 堆中元素个数
};
void PriorityQueue::addElem(string elem, int key)
{
trueelemQueue.push_back(elem);
truepriQueue.push_back(key);
}
void PriorityQueue::swapTwoElem(int i, int j)
{
trueint temp1 = priQueue[i];
truepriQueue[i] = priQueue[j];
truepriQueue[j] = temp1;
truestring temp2 = elemQueue[i];
trueelemQueue[i] = elemQueue[j];
trueelemQueue[j] = temp2;
}
void PriorityQueue::display()
{
truecout << "----------------------------------" << endl;
truefor (unsigned int i = 0; i <= heapSize; i++)
truetruecout << getElemVal(i) << "\t";
truecout << endl;
truefor (unsigned int i = 0; i <= heapSize; i++)
truetruecout << getElemPriVal(i) << "\t";
truecout << endl;
truecout << "----------------------------------" << endl;
}

/*
true保持堆的最大化
true运行时间：O(lgn)
true（练习6.2-5）使用循环取代了递归
*/
void PriorityQueue::maxHeapify(int i)
{
trueint largest = i;
trueint isHeapify = 0; // 设置是否处理完成的标志
truewhile (isHeapify == 0) {
truetrueunsigned int l = getLeftChild(i);
truetrueunsigned int r = getRightChild(i);
truetrueif (l <= heapSize && priQueue[l] > priQueue[largest])
truetruetruelargest = l;
truetrueif (r <= heapSize && priQueue[r] > priQueue[largest])
truetruetruelargest = r;
truetrueif (largest != i) {
truetruetrueswapTwoElem(i, largest);
truetruetruei = largest;
truetrue} else
truetruetrueisHeapify = 1; // largest等于i时处理完成
true}
}
/*
true在无序的输入数组基础上构造出最大堆
true线性时间运行
*/
void PriorityQueue::buildMaxHeap()
{
truefor (int i = heapSize / 2; i >= 0; i--) // 《算法导论》上的downto都是<= to是<
truetruemaxHeapify(i);
}
/*
true对一个数组进行原地排序
true运行时间：O(nlgn)
*/

void PriorityQueue::heapSort()
{
truebuildMaxHeap();
truefor (int i = heapSize; i >= 1; i--) {
truetrueswapTwoElem(0, i);
truetrue--heapSize;
truetruemaxHeapify(0);
true}
}
void PriorityQueue::extractMax()
{
trueif (heapSize < 0)
truetruethrow "heap underflow";
truecout << "被移除的元素是： "<< getElemVal(0) << " 优先级: " << getElemPriVal(0) << endl;
truepriQueue[0] = priQueue[heapSize];
trueelemQueue[0] = elemQueue[heapSize];
true--heapSize;
truemaxHeapify(0);
}
void PriorityQueue::increaseKey(int elemIndex, int newKey)
{
trueif (newKey < priQueue[elemIndex])
truetruethrow "new key is smaller than current key";
truepriQueue[elemIndex] = newKey;
truewhile (elemIndex > 0 && priQueue[getParent(elemIndex)] < priQueue[elemIndex]) {
truetrueswapTwoElem(elemIndex, getParent(elemIndex));
truetrueelemIndex = getParent(elemIndex);
true}
}
void PriorityQueue::heapInsert(string elem, int key)
{
true++heapSize;
truepriQueue[heapSize] = INT_MIN;
trueelemQueue[heapSize] = elem;
trueincreaseKey(heapSize, key);
}
void PriorityQueue::heapDelete(int elemIndex)
{
trueelemQueue[elemIndex] = elemQueue[heapSize];
truepriQueue[elemIndex] = priQueue[heapSize];
true--heapSize;
truemaxHeapify(elemIndex);
}
void PriorityQueue::heapDelete(string elem)
{
trueunsigned int elemIndex;
truefor (elemIndex = 0; elemIndex <= heapSize; elemIndex++)
truetrueif (elemQueue[elemIndex] == elem) {
truetruetruebreak;
truetrue}
trueelemQueue[elemIndex] = elemQueue[heapSize];
truepriQueue[elemIndex] = priQueue[heapSize];
true--heapSize;
truemaxHeapify(elemIndex);
}

int main()
{
truePriorityQueue queue;
truestring elem;
trueint key;
truewhile (cin >> elem >> key)
truetruequeue.addElem(elem, key);

true// 堆排序演示
truequeue.iniHeapSize();
truequeue.heapSort();
truequeue.iniHeapSize(); // heapSort后heapSize将为0
truecout << "堆排序：" << endl;
truequeue.display();

true// 优先级队列演示
truecout << "构建最大优先级队列：" << endl;
truequeue.buildMaxHeap();
truequeue.display();

truecout << "返回最大优先级元素/移除元素/提升某元素优先级/插入新元素：" << endl;
truecout <<"堆中优先级最高的元素是： " << queue.maximum() << "优先级： " << queue.getElemPriVal(0) << endl;
truequeue.extractMax();
truequeue.increaseKey(2, 99);
truequeue.heapInsert("shit", 999); // 插入优先级为num的元素str
truequeue.heapDelete("music");
truequeue.display();

truesystem("pause");
truereturn 0;
}