数据结构与算法系列之一：八大排序之堆排序

---

• 转载请注明作者和出处：http://blog.csdn.net/u011475210
• 个人博客：https://wordzzzz.github.io/ && https://wordzzzz.gitee.io/
• 代码地址：https://github.com/WordZzzz/Note/tree/master/DS-A
• 博客作者：WordZzzz，一只热爱技术的文艺青年

---

[toc]

堆排序

前言

  建议先看排序综述，传送门：数据结构与算法系列之一：八大排序综述。

简介

  堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

  通常堆是通过一维数组来实现的。在数组起始位置为0的情形中：

• 父节点i的左子节点在位置 ${\displaystyle (2i+1)}$。
• 父节点i的右子节点在位置 ${\displaystyle (2i+2)}$。
• 子节点i的父节点在位置 ${\displaystyle floor((i-1)/2)}$。

  在堆的数据结构中，堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作：

• 最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。
• 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序。
• 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。

步骤

  基于以上堆相关的操作，我们可以很容易的定义堆排序。例如，假设我们已经读入一系列数据并创建了一个堆，一个最直观的算法就是反复的调用del_max()函数，因为该函数总是能够返回堆中最大的值，然后把它从堆中删除，从而对这一系列返回值的输出就得到了该序列的降序排列。真正的原地堆排序使用了另外一个小技巧。堆排序的过程是：

• 创建一个堆 ${\displaystyle H[0..n-1]}$。
• 把堆首（最大值）和堆尾互换。
• 把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置。
• 重复步骤2，直到堆的尺寸为1。

演示

  wikipedia的大数据规模演示：

代码

递归版

/*
* 堆排序递归版
*/

template <typename T>
void MaxHeapifyRecursive(T *array, int i, int heapSize) {
	int sonl = 2 * i + 1;
	int sonr = 2 * i + 2;
	int dad = i;
	if (sonl <= heapSize && array[sonl]>array[i]){					//如果左子结点大于父结点，则父结点指向子结点
		dad = sonl;
	}
	if (sonr <= heapSize && array[sonr]>array[dad]){				//如果右子结点大于父结点，则父结点指向子结点
		dad = sonr;
	}
	if (dad != i){													//如果dad != i则说明父结点不是最大值，交换后递归执行MaxHeapifyRecursive
		swap(array[i], array[dad]);
		MaxHeapifyRecursive(array, dad, heapSize);
	}
}

template <typename T>
void HeapSort(T *array, const int length) {
	if (array == NULL)
		throw invalid_argument("Array must not be empty");
	if (length <= 0)
		return;

	//初始化，i从最后一个父结点开始调整
	for (int i = length / 2 - 1; i >= 0; --i){
		//构建最大堆 
		MaxHeapifyRecursive(array, i, length - 1);
//		MaxHeapifyIteration(array, i, length - 1);
	}
	//先将第一个元素和已经排好的元素前一位做交换，再从新调整（刚调整的元素之前的元素），直到排序完毕
	for (int i = length - 1; i >= 0; --i){
		swap(array[0], array[i]);
		MaxHeapifyRecursive(array, 0, i - 1);
//		MaxHeapifyIteration(array, 0, i - 1);
	}
}

迭代版

/*
* 堆排序迭代版
*/

template <typename T>
void MaxHeapifyIteration(T *array, int left, int right) {
	//建立父结点指针和子结点指针
	int dad = left;
	int son = dad * 2 + 1;
	while (son <= right) {											//若子结点指针在范围内才做比较
		if (son + 1 <= right && array[son] < array[son + 1])		//先比较两个子结点的大小，选择最大的
			son++;
		if (array[dad] > array[son])								//如果父结点大于子结点代表调整完毕，直接跳出循环
			return;
		else {														//否则交换父子内容在继续子结点和孙结点的比较
			swap(array[dad], array[son]);
			dad = son;
			son = dad * 2 + 1;
		}
	}
}

template <typename T>
void HeapSort(T *array, const int length) {
	if (array == NULL)
		throw invalid_argument("Array must not be empty");
	if (length <= 0)
		return;

	//初始化，i从最后一个父结点开始调整
	for (int i = length / 2 - 1; i >= 0; --i){
		//构建最大堆 
//		MaxHeapifyRecursive(array, i, length - 1);
		MaxHeapifyIteration(array, i, length - 1);
	}
	//先将第一个元素和已经排好的元素前一位做交换，再从新调整（刚调整的元素之前的元素），直到排序完毕
	for (int i = length - 1; i >= 0; --i){
		swap(array[0], array[i]);
//		MaxHeapifyRecursive(array, 0, i - 1);
		MaxHeapifyIteration(array, 0, i - 1);
	}
}

算法复杂度

• 数据结构 数组
• 最坏时间复杂度 ${\displaystyle O(n\log n)}$
• 最优时间复杂度 ${\displaystyle O(n\log n)}$
• 平均时间复杂度 ${\displaystyle O(n\log n)}$
• 空间复杂度 ${\displaystyle O(n)}$ total, ${\displaystyle O(1)}$ auxiliary

分析

  原地堆排序已经是空间优化版本了，因为它不再需要申请额外的空间。

  整个算法的过程分为建堆和排序两个过程，首先对现有数组建立最大堆，然后一边提取堆顶的最大值，一边减小堆的尺寸，最后堆尺寸为1时，排序也就完成了。如果大家对整个算法的执行过程不太了解，可以看一下下面这两张图，第一张是建堆的过程示意图，第二张是排序的过程示意图。图片来自：http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/

系列教程持续发布中，欢迎订阅、关注、收藏、评论、点赞哦～～(￣▽￣～)～

完的汪(∪｡∪)｡｡｡zzz