堆的定义如下:
n个元素的序列{k0,k1,...,ki,…,k(n-1)}当且仅当满足下关系时,称之为堆。
" ki<=k2i,ki<=k2i+1;或ki>=k2i,ki>=k2i+1.(i=1,2,…,[n/2])"
若将和此次序列对应的一维数组(即以一维数组作此序列的存储结构)看成是一个完全二叉树,
则完全二叉树中每一个节点的值的都大于或等于任意一个字节的值(如果有的话),称之为大顶堆。
则完全二叉树中每一个节点的值的都小于或等于任意一个字节的值(如果有的话),称之为小顶堆。
由此,若序列{k0,k1,…,k(n-1)}是堆,则堆顶元素(或完全二叉树的根)必为序列中n个元素的最小值(或最大值)。
倘若给堆中每一个节点都赋予一个整数值标签,根节点被标记为0,对于每一个标记为i的节点,其左子节点(若存在的话)被标记为2*i+1,其右子节点(若存在的话)被标记为2*i+2,对于一个标记为i的非根节点,其父节点被标记为(i-1)/2。使用这个标记,我们能够将堆存储在数组中,节点存储在数据中的位置就使其标签。
排序包含两个过程:
(1)初建堆
(2)调整堆
调整堆:对于第二个过程,描述如下,第一次,取出堆顶元素与R[n]进行交换,然后从根结点开始调整堆,根结点与左右孩子中较大者交换,这样,左右子树的堆会被破坏,继续进行上述操作,直到叶子结点为止。第二次,取出堆顶元素与R[n-1]交换,然后调整堆。
初建堆:从非终端结点开始一直到根结点,执行调整堆的过程。这样,就会建立一个大顶堆。
堆的调整 实际上简单理解就是 确保是一颗完全二叉树,即所有的父节点必须大于等于左右孩子。
堆调整之后,再进行堆排序。
如 数组 [2 7 3 5 6 9] 二叉树为
2
7 3
5 6 9
9 是大于 父节点 3 的,所以需要调整
堆排序算法的JAVA实现:
/**
* 堆排序包括两个步骤 (1)初始堆(堆的定义:(1)堆是一个完全二叉树(2)根结点的值或者大于左右子树的值或者小于左右子树的值(3)左右子树也是一个堆)
* (2)调整堆(当初始小顶堆之后,堆顶元素是最小的元素,取出最小的元素与最后一个元素相交换,再把剩下n-1个元素调整成堆,依次调整直到1为止)
* 非终端节点调整 初始堆时从n/2向上调整成堆 把第一个元素与最后一个元素交换之后从第1个元素开始调整成新堆
*
package collections;
public class HeapSorter {
public static void heapSort(int[] array){
buildHeap(array);//构建堆
int n = array.length;
int i=0;
for(i=n-1;i>=1;i--){
swap(array,0,i);
heapify(array,0,i);
}
}
public static void buildHeap(int[] array){
int n = array.length;//数组中元素的个数
for(int i=n/2-1;i>=0;i--)
heapify(array,i,n);
}
public static void heapify(int[] A,int idx,int max){
int left = 2*idx+1;// 左孩子的下标(如果存在的话)
int right =2*idx+2;// 左孩子的下标(如果存在的话)
int largest = 0;//寻找3个节点中最大值节点的下标
if(left<max && A[left]>A[idx])
largest = left;
else
largest = idx;
if(right<max && A[right]>A[largest])
largest = right;
if(largest!=idx){
swap(A,largest,idx);
heapify(A,largest,max);
}
}
public static void swap(int[] array,int i,int j){
int temp =0;
temp=array[i];
array[i]=array[j];
array[j]=temp;
}
public static void main(String[] args) {
int[] a = {1,2,3,4,5,6,7,16,9,10,11,12,13,14,15,8};
System.out.println("排序前..........................");
for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
System.out.println();
heapSort(a);
System.out.println("排序后..........................");
for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
}
}
分享到:
相关推荐
java堆排序、快速排序、冒泡排序、顺序排序等等
java堆排序和几种排序方法实现代码.pdf
java堆排序和几种排序方法实现代码文.pdf
Java实现堆排序不是C,Java实现堆排序不是C,Java实现堆排序不是C,Java实现堆排序不是C
Java 写得最大堆排序代码,给大家参考下,自己刚写的。
堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆...
本篇文章主要介绍了堆排序的简介,定义,算法实现以及堆排序的性质。想要了解的朋友可以参考下
主要介绍了java堆排序原理与实现方法,结合实例形式分析了java堆排序的相关原理、实现方法与操作注意事项,需要的朋友可以参考下
堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用...
堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆...
堆排序算法的java实现,采用大根堆。时间复杂度为O(nlogn).
本文对经典的堆排序非递归算法进行了详细的分析,并用JAVA实现。用过该问题的JAVA实现,可使学习者清晰的观测到解决该问题的全过程。
java的堆排序算法实现程序,含测试,可直接运行。java的堆排序算法实现程序,含测试,可直接运行。
堆排序算法 java
堆排序算法Java实现
主要为大家详细介绍了Java堆排序算法的相关代码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
在本篇文章里我们给大家分享了关于java堆排序的概念原理相关知识点内容,有需要的朋友们可以学习下。
主要介绍了JAVA堆排序算法的知识点,文中代码非常详细,配合上图片讲解,帮助大家更好的参考和学习,感兴趣的朋友可以了解下
下面小编就为大家分享一篇Java 堆排序实例(大顶堆、小顶堆),具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧