简介

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

堆排序算法原理和动态图解

将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走(其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值)，然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次最大值。如此反复执行，就能得到一个有序序列了。这个过程其实就是先构建一个最大/最小二叉堆，然后不停的取出最大/最小元素（头结点），插入到新的队列中，以此达到排序的目的。

堆的定义以及堆的数据模型图

堆的典型数据模型就是一个二叉堆， 如下图，是一个最大二叉堆：

最大二叉堆的定义：

1、最顶端的肯定是最大的值

2、父节点的值总是大于子节点的值。

3、是一个完全二叉树，它的层高相差不超过1，叶子结点总是从左向右依次填满。

相应的，如果根节点是最小值，就是最小二叉堆。只要满足上面三个条件即可，在上图中，13的层级比17要高一层，这并没有违反规则，是可以的。

为什么使用堆这种数据结构

优先队列是一种很常用的队列，比如在游戏中，游戏角色在自动模式下，如何在周围一堆小怪中自动攻击某一个小怪？可能是判断这一群小怪哪一个比较近，就攻击哪一个，或者哪一个等级低，就攻击哪一个。总之，是会动态的计算周围小怪的优先级，然后攻击优先级最高的那一个小怪。

堆 这一种数据结构，就是典型的动态优先队列。

另外，如果要从1000000个元素中选出排序前100的元素，如何选出来呢？从N个元素中取出前M个元素？如果用前面介绍到的算法，只能先排序（时间复杂度为NlogN）,然后取出前一百元素，如果使用堆排序，那么时间复杂度将降为NlogM. 时间效率将极大提升。

堆排序动态示例图数据的添加

在堆中添加一个元素，相当于在数组的末尾添加了一个元素，这个元素的位置暂时是最后一个，然后判断是否满足最大堆的定义，如果它比父节点要大，则需要把这个数和父节点交换。交换以后，如果在当前位置还要比父节点大，则继续向上交换，直到合适的位置，所以我们需要定义一个向上移动的函数shiftUp();

public void insert(Item item) {	if(count == capcity) {		return;//已经填满了，无法再填入数据了	}	data[count+1] = item;	count ++;//记录总共有多少个数据	ShiftUp(count);//执行向上移动}/** * 将k这个位置的元素 调整到堆的合适位置, *  * 最大堆的特点，父节点大于子节点 * 完全二叉树特点，总是从左到右，依次填满二叉树的子节点 */private void ShiftUp(int k) {	//用数组存储完全二叉堆，如果根节点的序列化声明为1，则左节点的序号都是父节点的二倍，看图理解，右节点是父节点的二倍+1	//父节点如果小于子节点，就要交换位置, 注意边界问题，所以k>1	while(k > 1 && data[k/2].compareTo(data[k]) < 0) {		swap( k, k/2);		k /= 2;	}}/** * 交换数组中两个值的位置 */private void swap(int i, int j) {	Item temp = data[i];	data[i] = data[j];	data[j] = temp;}

当需要取出优先级最高的数时，即需要取出二叉堆最顶端的数时，我们通常的操作就是将最顶端（脚标为1的数）和数组中最后一个数交换位置，然后移除左后一个元素即可。但是，此时，就不满足最顶端的数时最大数这个规则了，因此此时需要把顶端这个数向下移动（shiftDown）, 它需要和左右两个孩子比较，和最大的孩子进行交换，如果交换位置后，它的子孩子还要大于它，则继续和左右孩子中的最大值进行交换，直到移动到合适位置。

/** * 取出最大元素 */public Item extractMax() {	if(count == 0) {		return null;	}	Item item = data[1];//堆中第一个元素就是最大值	swap(1, count);//将最后一个元素放到第一个位置	count --;//总的数量减一	shiftDown(1);//重新调整整个堆，成为一个新的最大二叉堆	return item;}/** * 将元素向下移动，直到找到合适的位置 */private void shiftDown(int i) {	while(i*2 <= count) {//说明有左孩子		int j = i*2;//左孩子的脚标位置		if(j+1 <= count && data[j+1].compareTo(data[j]) > 0) {			//如果有右孩子，并且，右孩子比左孩子的值大			j = j+1;		}		if(data[i].compareTo(data[j]) > 0) {			break;//如果父节点大于 最大的子节点，则已经是新的最大二叉堆		}		swap(i, j);//否则，则交换父节点和最大子节点的位置，继续向下比较		i = j;//更新这个值的最新位置	}	}

果我们传入一个整个数组，数组中有一系列数据，那么我们就可以将这个数组形成一个堆的结构，这个过程称为堆化（Heapify）。

传入整个数组Heapify的算法复杂度比直接一个一个插入数据的效率更高

public MaxHeap(Item[] arr) {	this.capcity = arr.length;	//warnningValue = (n * 10) / 9;	data = (Item[]) new Comparable[capcity + 1];	System.arraycopy(arr, 0, data, 1, arr.length);	count = arr.length;		for(int i = count/2; i >= 1; i --) {		shiftDown(i);	}}

import java.util.Arrays;

/**

* 最大堆， 此处使用了泛型，

* @author admin

*

*/

public class MaxHeap<Item extends Comparable> {

protected Item[] data;

protected int count;

private int capcity;

private int warnningValue;

private byte[] lock = new byte[0];

public MaxHeap(int capcity){

this.capcity = capcity;

warnningValue = (capcity * 10) / 9;

//java不允许直接创建泛型数组，否则编译报错，所以通过强转来通过编译

//第0个位置不存储，从第一个位置开始存储,所以空一个位置

data= (Item[]) new Comparable[capcity+1];

count = 0;

}

public MaxHeap(Item[] arr) {

this.capcity = arr.length;

// warnningValue = (n * 10) / 9;

data = (Item[]) new Comparable[capcity + 1];

System.arraycopy(arr, 0, data, 1, arr.length);

count = arr.length;

for(int i = count/2; i >= 1; i --) {

shiftDown(i);

}

}

public int size() {

return count;

}

public boolean isEmpty() {

return count == 0;

}

public void destory() {

data = null;

count = 0;

}

//此方法可以学习时可以忽略，是insert方法的改良版， 参考了ArrayList插入数据的扩容功能。

public void insert2(Item item) {

//如果数量大于警戒值了，就是快要满了，此时扩容，考虑到多线程，没有使用 == capcity来判断

if(count >= warnningValue) {

synchronized (lock) {

if(count >= warnningValue) {

capcity = capcity * 2;

warnningValue = (capcity * 10) / 9;

//第0个位置不存储，从第一个位置开始存储,所以空一个位置

Item[] temp = (Item[]) new Comparable[capcity+1];

//方法二： System.arraycopy(src, srcPos, dest, destPos, length)

//src: 源数组

//srcPos: 从源数组复制数据的起始位置

//dest: 目标数组

//destPos: 复制到目标数组的起始位置

//length:数组的元素个数

System.arraycopy(data, 0, temp, 0, data.length);

data = temp;

}

}

}

data[count+1] = item;

count ++;

ShiftUp(count);

}

public void insert(Item item) {

if(count == capcity) {

return;//已经填满了，无法再填入数据了

}

data[count+1] = item;

count ++;

ShiftUp(count);

}

/**

* 取出最大元素

*/

public Item extractMax() {

if(count == 0) {

return null;

}

Item item = data[1];//堆中第一个元素就是最大值

swap(1, count);//将最后一个元素放到第一个位置

count --;//总的数量减一

shiftDown(1);//重新调整整个堆，成为一个新的最大二叉堆

return item;

}

/**

* 将元素向下移动，直到找到合适的位置

*/

private void shiftDown(int i) {

while(i*2 <= count) {//说明有左孩子

int j = i*2;//左孩子的脚标位置

if(j+1 <= count && data[j+1].compareTo(data[j]) > 0) {

//如果有右孩子，并且，右孩子比左孩子的值大

j = j+1;

}

if(data[i].compareTo(data[j]) > 0) {

break;//如果父节点大于 最大的子节点，则已经是新的最大二叉堆

}

swap(i, j);//否则，则交换父节点和最大子节点的位置，继续向下比较

i = j;//更新这个值的最新位置

}

}

/**

* 将k这个位置的元素 调整到堆的合适位置,

*

* 最大堆的特点，父节点大于子节点

* 完全二叉树特点，总是从左到右，依次填满二叉树的子节点

*/

private void ShiftUp(int k) {

//用数组存储完全二叉堆，如果根节点的序列化声明为1，则左节点的序号都是父节点的二倍，看图理解，右节点是父节点的二倍+1

//父节点如果小于子节点，就要交换位置, 注意边界问题，所以k>1

while(k > 1 && data[k/2].compareTo(data[k]) < 0) {

swap( k, k/2);

k /= 2;

}

}

/**

* 交换数组中两个值的位置

*/

private void swap(int i, int j) {

Item temp = data[i];

data[i] = data[j];

data[j] = temp;

}

}

堆排序C语言代码实现

#include <stdio.h>#include <stdlib.h> void swap(int* a, int* b) { int temp = *b; *b = *a; *a = temp;} void max_heapify(int arr[], int start, int end) { //建立父节点指标和子节点指标 int dad = start; int son = dad * 2 + 1; while (son <= end) { //若子节点指标在范围内才做比较 if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点大小，选择最大的 son++; if (arr[dad] > arr[son]) //如果父节点大於子节点代表调整完毕，直接跳出函数 return; else { //否则交换父子内容再继续子节点和孙节点比较 swap(&arr[dad], &arr[son]); dad = son; son = dad * 2 + 1; } }} void heap_sort(int arr[], int len) { int i; //初始化，i从最後一个父节点开始调整 for (i = len / 2 - 1; i >= 0; i--) max_heapify(arr, i, len - 1); //先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕 for (i = len - 1; i > 0; i--) { swap(&arr[0], &arr[i]); max_heapify(arr, 0, i - 1); }} int main() { int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 }; int len = (int) sizeof(arr) / sizeof(*arr); heap_sort(arr, len); int i; for (i = 0; i < len; i++) printf("%d ", arr[i]); printf("\n"); return 0;}

def big_endian(arr, start, end): root = start while True: child = root * 2 + 1 # 左孩子 if child > end: # 孩子比最后一个节点还大 也就意味着最后一个叶子节点了 就得跳出去一次循环已经调整完毕 break if child + 1 <= end and arr[child] < arr[child + 1]: # 为了始终让其跟子元素的较大值比较 如果右边大就左换右，左边大的话就默认 child += 1 if arr[root] < arr[child]: # 父节点小于子节点直接换位置 同时坐标也得换这样下次循环可以准确判断是否为最底层是不是调整完毕 arr[root], arr[child] = arr[child], arr[root] root = child else: # 父子节点顺序正常 直接过 break  def heap_sort(arr): # 无序区大根堆排序 first = len(arr) // 2 - 1 for start in range(first, -1, -1): # 从下到上，从右到左对每个节点进调整 循环得到非叶子节点 big_endian(arr, start, len(arr) - 1) # 去调整所有的节点 for end in range(len(arr) - 1, 0, -1): arr[0], arr[end] = arr[end], arr[0] # 顶部尾部互换位置 big_endian(arr, 0, end - 1) # 重新调整子节点的顺序 从顶开始调整 return arr  def main(): l = [3, 1, 4, 9, 6, 7, 5, 8, 2, 10] print(heap_sort(l)) # 原地排序 if __name__ == "__main__": main() 

#include <iostream>#include <algorithm>using namespace std; void max_heapify(int arr[], int start, int end) { //建立父节点指标和子节点指标 int dad = start; int son = dad * 2 + 1; while (son <= end) { //若子节点指标在范围内才做比较 if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点大小，选择最大的 son++; if (arr[dad] > arr[son]) //如果父节点大於子节点代表调整完毕，直接跳出函数 return; else { //否则交换父子内容再继续子节点和孙节点比较 swap(arr[dad], arr[son]); dad = son; son = dad * 2 + 1; } }} void heap_sort(int arr[], int len) { //初始化，i从最後一个父节点开始调整 for (int i = len / 2 - 1; i >= 0; i--) max_heapify(arr, i, len - 1); //先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完毕 for (int i = len - 1; i > 0; i--) { swap(arr[0], arr[i]); max_heapify(arr, 0, i - 1); }} int main() { int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 }; int len = (int) sizeof(arr) / sizeof(*arr); heap_sort(arr, len); for (int i = 0; i < len; i++) cout << arr[i] << ' '; cout << endl; return 0;}