堆排序算法
序言
对于堆排序的学习，实际上就是对于 堆 这一种数据结构的学习，把堆学会了，堆排序自然也就学会了。
1、为什么使用堆这种数据结构
优先队列是一种很常用的队列，比如在游戏中，游戏角色在自动模式下，如何在周围一堆小怪中自动攻击某一个小怪？可能是判断这一群小怪哪一个比较近，就攻击哪一个，或者哪一个等级低，就攻击哪一个。总之，是会动态的计算周围小怪的优先级，然后攻击优先级最高的那一个小怪。
堆 这一种数据结构，就是典型的动态优先队列。
另外，如果要从1000000个元素中选出排序前100的元素，如何选出来呢？从N个元素中取出前M个元素？如果用前面介绍到的算法，只能先排序（时间复杂度为NlogN）,然后取出前一百元素，如果使用堆排序，那么时间复杂度将降为NlogM. 时间效率将极大提升。
2、堆的定义以及堆的数据模型图
堆的典型数据模型就是一个二叉堆， 如下图，是一个最大二叉堆：
最大二叉堆的定义：
- 1、最顶端的肯定是最大的值
- 2、父节点的值总是大于子节点的值。
- 3、是一个完全二叉树，它的层高相差不超过1，叶子结点总是从左向右依次填满。
相应的，如果根节点是最小值，就是最小二叉堆。只要满足上面三个条件即可，在上图中，13的层级比17要高一层，这并没有违反规则，是可以的。
3、堆的基本存储
我们使用堆的规则，将数据存储在数组中。
如上图，是一个堆的示例，在数组中，我们从角标为1的位置开始存放数据，角标0我们并不使用。然后从上往下编号， 最大的数排第一个，然后往下一层从左到右依次排序，我们可以发现，如果父节点的位置是第i个，那么左节点就会是第2i个，右节点是第2i+1个。而子节点如果是第i个，则父节点就是第 i/2 个（如果有父节点）。这个规则很重要，下面写代码将用到。
3.1 数据的添加
我们明白了这个规则，就可以进行数据的插入了。在堆中添加一个元素，相当于在数组的末尾添加了一个元素，这个元素的位置暂时是最后一个，然后判断是否满足最大堆的定义，如果它比父节点要大，则需要把这个数和父节点交换。交换以后，如果在当前位置还要比父节点大，则继续向上交换，直到合适的位置，所以我们需要定义一个向上移动的函数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;
}
3.2 最大数据的取出（数据的删除）
我们刚刚说了，这是一个优先级队列，当需要取出优先级最高的数时，即需要取出二叉堆最顶端的数时，我们通常的操作就是将最顶端（脚标为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;//更新这个值的最新位置
}
}
如果我们循环调用此函数，依次取出最大值，则就完成了优先级从最高到最低的排序。
3.3 堆化（Heapify）
如果我们传入一个整个数组，数组中有一系列数据，那么我们就可以将这个数组形成一个堆的结构，这个过程称为堆化（Heapify）。
传入整个数组Heapify的算法复杂度比直接一个一个插入数据的效率更高
将n个元素逐个插入到一个空堆中，算法复杂度是O(nlogn)
heapify的过程，算法复杂度为O(n),即在一个已知数组上去进行优先级排序，会更快。 具体的证明可以网上找
就算不证明，想一下也会快一点，用heapify，每次n/2,直接减少一半的数据，所以快很多
通过观察可以得到，count/2得到的节点为最后一个父节点（非叶子节点）， 然后它的角标依次减减， 就得到其他的父节点，依次调整每个父节点的子树为一个完全二叉堆，最后就得到一颗新的完全二叉堆树。
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);
}
}
3.4 时间复杂度比较
使用堆排序和使用普通数组的时间复杂度比较
验证结果输出
The max heap size is: 12
Data in the max heap（注意这不是排序，只是数据在堆中的位置）:
84 65 65 64 54 14 16 10 57 27 25 9
84
/ \
65 65
/ \ / \
64 54 14 16
/ \ / \ / \ / \
10 57 27 25 9
max=84
The max heap size is: 11
Data in the max heap（注意这不是排序，只是数据在堆中的位置）:
65 64 65 57 54 14 16 10 9 27 25
65
/ \
64 65
/ \ / \
57 54 14 16
/ \ / \ / \ / \
10 9 27 25
排序结果： 65 65 64 57 54 27 25 16 14 10 9
完整代码
功能验证可以使用printMaxHeap类，它会在控制台打印输出排序完成后的数组的数据，以及整个堆的结构， 完整功能及测试代码如下：
最大堆 MaxHeap：
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;
}
}
功能测试类(测试类只关注功能测试即可，打印堆的方法不用去关注，不是本文重点)：
public class PrintMaxHeap extends MaxHeap<Comparable<integer>> {
public PrintMaxHeap(int capacity) {
super(capacity);
}
public PrintMaxHeap(Comparable[] arr) {
super(arr);
}
// 测试 PrintableMaxHeap
public static void main(String[] args) {
testMaxHeap1() ;
//testMaxHeap2() ;
}
public static void testMaxHeap1() {
PrintMaxHeap maxHeap = new PrintMaxHeap(100);
int N = 12; // 堆中元素个数
int M = 90; // 堆中元素取值范围[0, M)
for( int i = 0 ; i < N ; i ++ )
maxHeap.insert( new Integer((int)(Math.random() * M)) );
maxHeap.treePrint();
Comparable i = maxHeap.extractMax();
System.out.println("max="+i);
maxHeap.treePrint();
}
public static void testMaxHeap2() {
PrintMaxHeap maxHeap = new PrintMaxHeap(randomArray(12));
maxHeap.treePrint();
Comparable i = maxHeap.extractMax();
System.out.println("max="+i);
maxHeap.treePrint();
}
// 以树状打印整个堆结构
public void treePrint(){
if( size() >= 100 ){
System.out.println("This print function can only work for less than 100 integer");
return;
}
System.out.println("The max heap size is: " + size());
System.out.println("Data in the max heap: ");
for( int i = 1 ; i <= size() ; i ++ ){
// 我们的print函数要求堆中的所有整数在[0, 100)的范围内
assert (Integer)data[i] >= 0 && (Integer)data[i] < 100;
System.out.print(data[i] + " ");
}
System.out.println();
System.out.println();
int n = size();
int maxLevel = 0;
int numberPerLevel = 1;
while( n > 0 ){
maxLevel += 1;
n -= numberPerLevel;
numberPerLevel *= 2;
}
int maxLevelNumber = (int)Math.pow(2, maxLevel-1);
int curTreeMaxLevelNumber = maxLevelNumber;
int index = 1;
for( int level = 0 ; level < maxLevel ; level ++ ){
String line1 = new String(new char[maxLevelNumber*3-1]).replace('\0', ' ');
int curLevelNumber = Math.min(count-(int)Math.pow(2,level)+1,(int)Math.pow(2,level));
boolean isLeft = true;
for( int indexCurLevel = 0 ; indexCurLevel < curLevelNumber ; index ++ , indexCurLevel ++ ){
line1 = putNumberinline( (Integer)data[index] , line1 , indexCurLevel , curTreeMaxLevelNumber*3-1 , isLeft );
isLeft = !isLeft;
}
System.out.println(line1);
if( level == maxLevel - 1 )
break;
String line2 = new String(new char[maxLevelNumber*3-1]).replace('\0', ' ');
for( int indexCurLevel = 0 ; indexCurLevel < curLevelNumber ; indexCurLevel ++ )
line2 = putBranchInLine( line2 , indexCurLevel , curTreeMaxLevelNumber*3-1 );
System.out.println(line2);
curTreeMaxLevelNumber /= 2;
}
}
private String putNumberInLine( Integer num, String line, int indexCurLevel, int curTreeWidth, boolean isLeft){
int subTreeWidth = (curTreeWidth - 1) / 2;
int offset = indexCurLevel * (curTreeWidth+1) + subTreeWidth;
assert offset + 1 < line.length();
if( num >= 10 )
line = line.substring(0, offset+0) + num.toString()
+ line.substring(offset+2);
else{
if( isLeft)
line = line.substring(0, offset+0) + num.toString()
+ line.substring(offset+1);
else
line = line.substring(0, offset+1) + num.toString()
+ line.substring(offset+2);
}
return line;
}
private String putBranchInLine( String line, int indexCurLevel, int curTreeWidth){
int subTreeWidth = (curTreeWidth - 1) / 2;
int subSubTreeWidth = (subTreeWidth - 1) / 2;
int offsetleft = indexCurLevel * (curTreeWidth+1) + subSubTreeWidth;
assert offsetLeft + 1 < line.length();
int offsetRight = indexCurLevel * (curTreeWidth+1) + subTreeWidth + 1 + subSubTreeWidth;
assert offsetRight < line.length();
line = line.substring(0, offsetLeft+1) + "/" + line.substring(offsetLeft+2);
line = line.substring(0, offsetRight) + "\\" + line.substring(offsetRight+1);
return line;
}
public static Integer[] randomArray(int length) {
Integer[] arr = new Integer[length];
Random random = new Random();
for(int i=0; i<length; i++) {
arr[i] = random.nextint(100);
}
//自动生成随机数组，先进行一次原始数据打印
System.out.println(Arrays.toString(arr));
return arr;
}
}
相关阅读
一、堆排序算法原理和动态图解 将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走(其实就是将
选择排序的基本思想是：每一趟（例如第i趟）在后面的 n-i+1 个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到第 n-1
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。 算法分析 在学习堆排序之前我们要先