本片内容：
最大堆：
二叉堆是完全二叉树或者是近似完全二叉树，
当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。（父节点大于任何一个子节点）
算法思想：
重复以上步骤，直到把最后两个元素建成最大堆并进行交换，得到的序列就是排序后的有序序列。
代码实现：
我要评论/**
*
*/
package com.cherish.sortingalgorithm;
/**
* @author acer
*
*/
public class chapter_7_堆排序 extends arraybase {
/**
* @param args
*/
public static void main(string[] args) {
// todo 自动生成的方法存根
int[] array = new int[] {3,4,7,9,2,5,1,8,6};
heapsorting(array);
printarray(array);
}
//堆排序
public static void heapsorting(int[] array)
{
int arraylength = array.length;
//循环建堆
for(int i = 0;i < arraylength-1;i++)
{
//建堆，建一次最大堆，寻找一个待排序列的最大数
buildmaxheap(array,arraylength-1-i);
//交换堆顶元素（带排序序列的最大数）和最后一个元素 array[0]是堆顶
swap(array,0,arraylength-1-i);
}
}
//建最大堆
public static void buildmaxheap(int[] array,int lastindex)
{
//从最后一个节点（index）的父节点开始
for(int i = (lastindex-1)/2 ; i >= 0; i--)
{
//k 保存正在判断的节点
int k = i;
//如果当前k节点的子节点存在
while(k*2+1 <= lastindex)
{
//k节点的左子节点的索引
int biggerindex = 2*k + 1;
//如果k节点的左子节点biggerindex小于index,即biggerindex+1代表的k节点的右子节点存在
if(biggerindex < lastindex)
{
//若右子节点的值较大
if(array[biggerindex]<array[biggerindex + 1])
{
//biggerindex总是记录较大子节点的索引
biggerindex = biggerindex + 1;
}
}
//如果k节点的值小于其较大的子节点的值，交换他们
if(array[k] < array[biggerindex])
{
swap(array,k,biggerindex);
//将biggerindex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
k = biggerindex;
}else
{
//当前判断节点k(父节点)大于他的两个子节点时，跳出while循环
break;
}
}
}
}
}
实现结果：
由上图可以看到，每次建立最大堆时，最大的数都在array[0],下一次建堆时，上一个最大的数已经移到数组尾部了。
如对本文有疑问， 点击进行留言回复！！
网友评论