转自
http://topic.csdn.net/u/20110518/09/6021fd63-3084-4fda-a4b6-da2fe58de367.html?seed=1655503227&r=73523235#r_73523235
对原贴的代码进行整理并做一些修改
import java.util.Comparator;
/**
* 将堆调整成最大堆
*
* @author Administrator
*
*/
public class Heap {
/**
* 返回值为i/2
* @param i
* @return
*/
public static int parent(int i) {
return (i - 1) >> 1;
}
/**
* 返回值为2*i
* @param i
* @return
*/
public static int left(int i) {
return ((i + 1) << 1) - 1;
}
/**
* 返回值为2*i+1
* @param i
* @return
*/
public static int right(int i) {
return (i + 1) << 1;
}
public static <T> void heapify(T[] a, int i, Comparator<? super T> c) {
heapify(a, i, c, a.length);
}
public static <T> void heapify(T[] a, int i, Comparator<? super T> c, int size) {
int l = left(i);
int r = right(i);
int next = i;
if (l < size && c.compare(a[l], a[i]) > 0)
next = l;
if (r < size && c.compare(a[r], a[next]) > 0)
next = r;
if (i == next)
return;
swap(a, i, next);
heapify(a, next, c, size);
}
/**
* 对堆进行排序
* @param <T>
* @param a
* @param c
*/
public static <T> void heapSort(T[] a, Comparator<? super T> c) {
buildHeap(a, c);
for (int i = a.length - 1; i > 0; i--) {
swap(a, 0, i);
heapify(a, 0, c, i);
}
}
/**
* 交换数组值
* @param arr
* @param i
* @param j
*/
private static void swap(Object[] arr, int i, int j) {
Object tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
/**
* 创建堆
* @param <T>
* @param a
* @param c
*/
public static <T> void buildHeap(T[] a, Comparator<? super T> c) {
for (int i = (a.length ) / 2 - 1; i >= 0; i--) {
heapify(a, i, c);
}
}
/**
* @param args
*/
public static void main(String[] args) {
// heapify test
Integer[] temp = null;
temp = new Integer[] { 5, 2, 4, 6, 1, 3, 2, 6 };
temp = new Integer[] { 16, 14, 8, 7, 9, 3, 2, 4,1 };
Comparator<Integer> comp = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
};
buildHeap(temp, comp);
for (int i : temp) {
System.out.print(i + " ");
}
System.out.println();
heapSort(temp, comp);
for (int i : temp) {
System.out.print(i + " ");
}
System.out.println();
}
}
分享到:
相关推荐
在Java中实现《算法导论》中的算法,首先需要理解算法的基本思想和逻辑结构。这包括排序算法(如冒泡排序、选择排序、插入排序、快速排序、归并排序等)、查找算法(如线性查找、二分查找等)、图算法(如Dijkstra...
《算法导论-Java》是计算机科学领域的重要教材,它深入浅出地介绍了算法的设计、分析和实现。这本书对于任何想要提升编程技能,尤其是Java程序员来说,都是不可或缺的资源。算法是解决复杂问题的关键,它们是程序的...
《Java算法导论》是一本深入探讨如何在Java编程环境中应用算法的重要著作。这本书的目标是帮助读者理解并掌握算法的设计、分析以及实现,通过使用Java编程语言,使学习过程更为直观和实用。以下是对该书内容的一些...
《算法导论第四版》系统地介绍了多种排序算法,如冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序等。书中不仅解释了每种算法的工作原理和性能特性,还对比了它们在不同情况下的应用效果。此外,作者还...
《算法导论》是计算机科学领域的一本经典著作,它深入浅出地介绍了各种重要的算法,并...通过研究这个Java版本的《算法导论》实现,开发者可以加深对算法的理解,提高编程技能,并能够灵活运用这些算法解决实际问题。
《算法导论》是计算机科学领域的一本经典著作,它深入浅出地介绍了算法的设计、分析和实现。这本书广泛应用于大学计算机科学课程中,对于学习和理解算法有着极高的价值。在Java编程环境下,我们可以利用Java语言来...
《算法导论》和《算法》是两本深入探讨计算机科学中算法理论和技术的重要书籍,对于任何想要在IT领域特别是软件开发和数据处理方面深化理解的个人来说,都是不可或缺的资源。 《算法导论》是一本广泛认可的经典之作...
读书笔记:算法导论中基本算法 java 实现
《算法导论》的第二版特别强调了实际编程实现,书中提供了C语言的代码示例,同时,这些算法也可以轻松地转换为其他编程语言,如Python或Java。这使得理论知识与实践应用之间建立了紧密的联系,帮助读者提高编程技能...
《算法导论》是计算机科学领域的一本经典教材,它深入浅出地介绍了各种重要的算法,并提供了详尽的分析和实现。题目中的“4-4”可能指的是书中的第四章第四个习题,通常涉及图算法或者动态规划等主题。由于具体描述...
《算法导论》是计算机科学领域的一本经典教材,它深入浅出地介绍了各种重要的算法,并提供了详尽的分析和实现。第九章通常涉及到图算法,这是计算机科学中一个非常关键的话题,因为图模型可以广泛应用于网络、社交...
《算法导论学习资料共享》是一份集合了多种算法实现的学习资源,主要针对《算法导论》这本书中的经典问题和算法。这份资料包含了Java语言实现的常见排序算法、装配线问题、最长公共子序列问题、矩阵连乘问题、优先...
【算法导论】是计算机科学领域的一本经典教材,它深入浅出地介绍了各种重要的算法,包括图算法。在山东大学的算法导论实验...通过这个实验,学生不仅能深入理解算法导论中的核心概念,还能提升Java编程和问题解决能力。
本实验旨在通过实际编程实践,加深对《算法导论》中核心概念的理解,尤其是排序算法和树结构的性能比较。实验分为必做题和选做题,涵盖排序算法的实现与性能比较、红黑树与二叉搜索树的实现与性能分析,以及最长递增...
算法导论C++实现代码.rar 算法导论Java代码.rar 算法导论习题乱解.pdf 算法导论教师参考.pdf 算法导论第二版习题答案_Philip Bille.pdf 算法导论讲义.zip 算法导论第二版大部分算法的Java实现.zip
《算法导论》是计算机科学领域的一本经典教材,它深入浅出地介绍了各种重要的算法,并提供了详尽的分析和实现。第五章通常涵盖了图算法,这是计算机科学中至关重要的一部分,因为图可以用来模型化各种实际问题,如...
《算法导论》是计算机科学领域的一本经典著作,它深入浅出地介绍了算法的设计、分析和实现。这本书的中文版第二版对于中国读者来说,无疑是理解和掌握算法知识的重要资源。书中涵盖了各种基础和高级算法,包括排序、...
《算法导论》是计算机科学领域的一本经典著作,它深入浅出地介绍了各种重要的算法,并配以详尽的分析和实例。这份压缩包文件包含了该书第1至16章的部分编程题目的Java实现,对于学习算法和提高编程技能来说,是一个...
读书笔记:算法导论Java实现
《算法导论》是一本广泛认可的计算机科学经典教材,其深入浅出地介绍了各种算法的设计、分析和实现。这本书的电子版包含了原书的图片,使得读者在阅读过程中能够更好地理解和掌握复杂的算法示意图。"含数学符号"的...