堆排序的思想是利用数据结构--
堆。具体的实现细节:
1. 构建一个最大堆。对于给定的包含有n个元素的数组A[n],构建一个最大堆(最大堆的特性是,某个节点的值最多和其父节点的值一样大。这样,堆中的最大元素存放在根节点中;并且,在以某一个节点为根的子树中,各节点的值都不大于该子树根节点的值)。从最底下的子树开始,调整这个堆结构,使其满足最大堆的特性。当为了满足最大堆特性时,堆结构发生变化,此时递归调整对应的子树。
2. 堆排序算法,每次取出该最大堆的根节点(因为根节点是最大的),同时,取最末尾的叶子节点来作为根节点,从此根节点开始调整堆,使其满足最大堆的特性。
3. 重复上一步操作,直到堆的大小由n个元素降到2个。
4. gif 演示:
http://upload.wikimedia.org/wikipedia/commons/4/4d/Heapsort-example.gif (来自wikipedia)
public class HeapSort {
public static void sort(Comparable[] data) {
// 构建最大堆
buildMaxHeap(data);
// 循环,每次把根节点和最后一个节点调换位置
for (int i = data.length; i > 1; i--) {
Comparable tmp = data[0];
data[0] = data[i - 1];
data[i - 1] = tmp;
// 堆的长度减少1,排除置换到最后位置的根节点
maxHeapify(data, 1, i - 1);
}
}
// 根据输入数组构建一个最大堆
private static void buildMaxHeap(Comparable[] data) {
for (int i = data.length / 2; i > 0; i--) {
maxHeapify(data, i, data.length);
}
}
//堆调整,使其生成最大堆
private static void maxHeapify(Comparable[] data, int parentNodeIndex, int heapSize) {
// 左子节点索引
int leftChildNodeIndex = parentNodeIndex * 2;
// 右子节点索引
int rightChildNodeIndex = parentNodeIndex * 2 + 1;
// 最大节点索引
int largestNodeIndex = parentNodeIndex;
// 如果左子节点大于父节点,则将左子节点作为最大节点
if (leftChildNodeIndex <= heapSize && data[leftChildNodeIndex - 1].compareTo(data[parentNodeIndex - 1]) > 0) {
largestNodeIndex = leftChildNodeIndex;
}
// 如果右子节点比最大节点还大,那么最大节点应该是右子节点
if (rightChildNodeIndex <= heapSize && data[rightChildNodeIndex - 1].compareTo(data[largestNodeIndex - 1]) > 0) {
largestNodeIndex = rightChildNodeIndex;
}
// 最后,如果最大节点和父节点不一致,则交换他们的值
if (largestNodeIndex != parentNodeIndex) {
Comparable tmp = data[parentNodeIndex - 1];
data[parentNodeIndex - 1] = data[largestNodeIndex - 1];
data[largestNodeIndex - 1] = tmp;
// 交换完父节点和子节点的值,对换了值的子节点检查是否符合最大堆的特性
maxHeapify(data, largestNodeIndex, heapSize);
}
}
}
- 大小: 644.6 KB
分享到:
相关推荐
java的堆排序算法实现程序,含测试,可直接运行。java的堆排序算法实现程序,含测试,可直接运行。
主要介绍了Java实现堆排序(Heapsort)实例代码,有需要的朋友可以参考一下
heapSort 方法实现了堆排序算法。它使用以下步骤进行排序: 构建最大堆:从非叶子节点开始向上调整,使得父节点的值大于等于子节点的值。 排序阶段:依次从堆顶(最大值)开始,将堆顶元素与末尾元素交换,然后...
主要介绍了java 数据结构之堆排序(HeapSort)详解及实例的相关资料,需要的朋友可以参考下
Java 写得最大堆排序代码,给大家参考下,自己刚写的。
用java实现的常用排序,都可以编译运行。 包括shellSort, quickSort, mergeSort, heapSort
堆排序Java中的堆排序实现
java写的八大经典排序算法(win7 jdk 1.6 下运行) ...堆排序 HeapSort 插入排序 InsSort 快速排序 QuickSort 归并排序 MergeSort 基数排序 BucketSort 简单选择排序 SelectSort 希尔排序 ShellSort
ED2-堆排序 堆排序算法的实现
将待排序序列构造成一个大顶堆 此时,整个序列的最大值就是堆顶的根节点。 将其与末尾元素进行交换,此时末尾就为最大值。 然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行...
堆排序 执行 3 向堆排序
:thinking_face: 算法 ...堆排序-HeapSort :lion:搜索算法-搜索 与搜索相关的数据结构:二叉查找树,平衡查找树,散列表 线性查找-LinearSearch 二分查找-BinarySearch 广度优先搜索 深度优先搜索
常用排序算法总结,包括插入排序(InsertionSort),冒泡排序(BubbleSort),选择排序(SelectionSort),快速排序(QuickSort... * 二路归并排序(MergeSort),堆排序(HeapSort)。有每一种排序算法的复杂度分析以及实现思路~
目录 02.字符串 03.树 04.哈希表 05.栈和队列 06.图 07.位运算 08.链表 程序基本输入输出 基础算法 返回目录 # English Title ...Java ...Java ...Java ...Java ...Java ...Java ...Java ...Java ...Java ...Java ...HeapSort 堆排序 Java 1
汉诺塔java源码 ForPower 一些个人的学习笔记的归档,相关目录内容如下: Arithmetic Atoi.java,实现 atoi,将字符串转为整数 BackPack.java,背包算法。 BasicSort.java,基数排序。...堆排序。 InsertionS
leetcode切割分组 java_algorithm this is a sorting algorithm demo. created by ...堆排序 QuickSort 快速排序 平均时间复杂度 O(n + k) 空间复杂度 O(k) CountingSort | 计数排序 | 用一个计算器
堆排序及有关方法。 2,BitTree.Java ;二叉树的遍历 3,DataSort.Java;排序算法 4,堆排的第二种思路 LeetCode322 :给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的...
数据结构与算法 对于Hacktoberfest 2018... 以上几点示例:Java中的堆排序应进入java/heapsort.java 您可以选择仅包含算法的功能或整个程序。 如果您所用语言的文件夹不存在,请创建一个新文件夹。 不要害怕进行公关
主题包括联合查找,二进制搜索,堆栈,队列,包,插入排序,选择排序,shellsort,quicksort,3向quicksort,mergesort,heapsort,binary堆,binary搜索树,red-black树,分离链和线性探测哈希表,Graham扫描和kd...