import java.util.Scanner;
public class Heap {
private int[] data;
/*输入数组元素,数组下标从1开始*/
public void input() {
System.out.println("请输入数组大小");
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
data = new int[n + 1];
System.out.println("输入数组元素");
for (int i = 1; i <= data.length-1; i++) {
data[i] = scanner.nextInt();
}
System.out.println("输入完成");
}
//测试数据:
//第一组:1 7 9 3 10 16 4 14 2 8
//第二组:17 8 84 2 45 94
//第三组:10 32 1 9 5 7 12 0 4
public static void main(String args[]){
Heap h=new Heap();
h.input();
System.out.println("堆排序前:");
h.print();
h.heapSort();
System.out.println("堆排序后:");
h.print();
}
/**
* 调整堆,使其满足堆得定义
* @param i
* @param n
*/
public void adjust(int i, int n) {
int child;
for (; i <= n / 2; ) {
child = i * 2;
// System.out.println("child="+child);
if(child+1<=n&&data[child]<data[child+1])
child+=1;/*使child指向值较大的孩子*/
if(data[i]<data[child]){
swap(i, child);
/*交换后,以child为根的子树不一定满足堆定义,所以从child处开始调整*/
i = child;
} else break;
}
}
public void heapSort() {
/*根据树的性质建堆,树节点前一半一定是分支节点,所以我们从这里开始调整出初始堆*/
for (int i = data.length / 2; i > 0; i--)
adjust(i, data.length-1);
System.out.println("调整后的初始堆:");
print();
for (int i = data.length-1; i > 0; i--) {
/*把根节点跟最后一个元素交换位置,调整剩下的n-1个节点,即可排好序*/
swap(1, i);
adjust(1, i - 1);
}
}
public void swap(int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
public void print() {
for (int i = 1; i < data.length; i++) {
System.out.print(data[i]+" ");
}
System.out.println();
}
}
运行:
请输入数组大小
10
输入数组元素
1 7 9 3 10 16 4 14 2 8
输入完成
堆排序前:
1 7 9 3 10 16 4 14 2 8
调整后的初始堆:
16 14 9 7 10 1 4 3 2 8
堆排序后:
1 2 3 4 7 8 9 10 14 16
下载源码:
- 大小: 30 KB
- 大小: 23.6 KB
- 大小: 71.7 KB
- 大小: 14.8 KB
分享到:
相关推荐
该资源包括实用练习,让读者可以练习在Java中实现堆排序,并提供解决方案以帮助读者检查自己的工作并深入理解所学内容。 无论您是Java编程的初学者还是有经验的程序员,该资源都将为您提供有价值的指导和支持,帮助...
对于堆排序的java实现的理解,是初学数据结构的人的入门资源
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
如果将堆理解为二叉树,那么树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字,堆排序的时间复杂度为O(N*logN),这里我们就来详解堆排序算法原理及Java版的代码实现
1.5.1 编辑Java源代码 12 1.5.2 编译Java程序 13 学生提问:当我们使用编译C程序时,不仅需要指定存放目标文件的位置,也需要指定目标文件的文件名,这里使用javac编译Java程序时怎么不需要指定目标文件的文件名呢...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
基于Java 8实现的代码片段集合,可以在之上的同步理解这些算法代码片段。博客地址: :fox:排序算法-排序 与排序相关的数据结构:优先权(二叉堆) 冒泡排序-BubbleSort | | 插入排序-InsertionSort | 插入排序优化...
b.10 个算法:递归,排序,二分查找,搜索,哈希算法,贪心算法,分治算法,回溯算法,动态规划,字符串匹配算法。 四。学习技巧 1.边学边练,适度刷题。保持每周花 1 到 2 个小时把相关内容用代码实现。 2.多问,...
leetcode题库 Leetcode Java解法 与 算法练习题 简要说明 leetcode题目的java解决方案还有...添加了domain包,更新了最大堆和控制台打印最大堆的数据结构,更新了堆排序,与堆排序构建的heapify优化,稍稍优化了工具类SortU
堆排序 小结 问题 实验 编程作业 第13章 图 图简介 搜索 最小生成树 有向图的拓扑排序 有向图的连通性 小结 问题 实验 编程作业 第14章 带权图 带权图的最小生成树 最短路径问题 每一对顶点...
介绍 这些文章是我的编程学习笔记。 它们大多数与书籍或网络结合在一起。 别人是我自己的作品。 它们不仅介绍如何获取...10-- 算法#10--用简单的思维理解堆排序 算法# 用简单的思维理解归并排序和三向快速排序 12--
得对数据的访问可按照统一的方式进行,那些能比较容易地产生更为强壮的代码。 OOP 语言提出一种(或称为协议),以保证对数据进行统一的操作。通常的做法是:程 序和对象数据的交互作用通过一个公开的接口进行,而不...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
堆排序 小结 问题 实验 编程作业 第13章 图 图简介 搜索 最小生成树 有向图的拓扑排序 有向图的连通性 小结 问题 实验 编程作业 第14章 带权图 带权图的最小生成树 最短路径问题 每一对顶点...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
用JAVA实现一个快速排序。 40 59. 请对以下在J2EE中常用的名词进行解释(或简单描述) 40 59.1. web 容器 40 59.2. EJB容器 40 59.3. JNDI 40 59.4. JMS 41 59.5. JTA 41 59.6. JAF 41 59.7. RMI/IIOP 41 60. JAVA语言...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...