`
lotusyu
  • 浏览: 34351 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
文章分类
社区版块
存档分类
最新评论

算法导论中堆相关算法的java实现

阅读更多
转自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实现

    在Java中实现《算法导论》中的算法,首先需要理解算法的基本思想和逻辑结构。这包括排序算法(如冒泡排序、选择排序、插入排序、快速排序、归并排序等)、查找算法(如线性查找、二分查找等)、图算法(如Dijkstra...

    算法导论-java

    《算法导论-Java》是计算机科学领域的重要教材,它深入浅出地介绍了算法的设计、分析和实现。这本书对于任何想要提升编程技能,尤其是Java程序员来说,都是不可或缺的资源。算法是解决复杂问题的关键,它们是程序的...

    Java 算法导论 电子书

    《Java算法导论》是一本深入探讨如何在Java编程环境中应用算法的重要著作。这本书的目标是帮助读者理解并掌握算法的设计、分析以及实现,通过使用Java编程语言,使学习过程更为直观和实用。以下是对该书内容的一些...

    算法导论第四版 英文

    《算法导论第四版》系统地介绍了多种排序算法,如冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序等。书中不仅解释了每种算法的工作原理和性能特性,还对比了它们在不同情况下的应用效果。此外,作者还...

    算法导论部分实现代码Java版

    《算法导论》是计算机科学领域的一本经典著作,它深入浅出地介绍了各种重要的算法,并...通过研究这个Java版本的《算法导论》实现,开发者可以加深对算法的理解,提高编程技能,并能够灵活运用这些算法解决实际问题。

    算法导论_java_

    《算法导论》是计算机科学领域的一本经典著作,它深入浅出地介绍了算法的设计、分析和实现。这本书广泛应用于大学计算机科学课程中,对于学习和理解算法有着极高的价值。在Java编程环境下,我们可以利用Java语言来...

    算法导论、算法

    《算法导论》和《算法》是两本深入探讨计算机科学中算法理论和技术的重要书籍,对于任何想要在IT领域特别是软件开发和数据处理方面深化理解的个人来说,都是不可或缺的资源。 《算法导论》是一本广泛认可的经典之作...

    读书笔记:算法导论中基本算法 java 实现.zip

    读书笔记:算法导论中基本算法 java 实现

    算法导论及算法导论答案

    《算法导论》的第二版特别强调了实际编程实现,书中提供了C语言的代码示例,同时,这些算法也可以轻松地转换为其他编程语言,如Python或Java。这使得理论知识与实践应用之间建立了紧密的联系,帮助读者提高编程技能...

    算法导论习题解答 4-4

    《算法导论》是计算机科学领域的一本经典教材,它深入浅出地介绍了各种重要的算法,并提供了详尽的分析和实现。题目中的“4-4”可能指的是书中的第四章第四个习题,通常涉及图算法或者动态规划等主题。由于具体描述...

    算法导论第九章习题解答

    《算法导论》是计算机科学领域的一本经典教材,它深入浅出地介绍了各种重要的算法,并提供了详尽的分析和实现。第九章通常涉及到图算法,这是计算机科学中一个非常关键的话题,因为图模型可以广泛应用于网络、社交...

    算法导论学习资料共享

    《算法导论学习资料共享》是一份集合了多种算法实现的学习资源,主要针对《算法导论》这本书中的经典问题和算法。这份资料包含了Java语言实现的常见排序算法、装配线问题、最长公共子序列问题、矩阵连乘问题、优先...

    山东大学 算法导论实验1-7完整代码 Java

    【算法导论】是计算机科学领域的一本经典教材,它深入浅出地介绍了各种重要的算法,包括图算法。在山东大学的算法导论实验...通过这个实验,学生不仅能深入理解算法导论中的核心概念,还能提升Java编程和问题解决能力。

    我们学校的算法导论实验要求

    本实验旨在通过实际编程实践,加深对《算法导论》中核心概念的理解,尤其是排序算法和树结构的性能比较。实验分为必做题和选做题,涵盖排序算法的实现与性能比较、红黑树与二叉搜索树的实现与性能分析,以及最长递增...

    算法导论第二版 C++ java 习题

    算法导论C++实现代码.rar 算法导论Java代码.rar 算法导论习题乱解.pdf 算法导论教师参考.pdf 算法导论第二版习题答案_Philip Bille.pdf 算法导论讲义.zip 算法导论第二版大部分算法的Java实现.zip

    算法导论第五章习题解答

    《算法导论》是计算机科学领域的一本经典教材,它深入浅出地介绍了各种重要的算法,并提供了详尽的分析和实现。第五章通常涵盖了图算法,这是计算机科学中至关重要的一部分,因为图可以用来模型化各种实际问题,如...

    算法导论中文版第二版(书+课后习题答案)

    《算法导论》是计算机科学领域的一本经典著作,它深入浅出地介绍了算法的设计、分析和实现。这本书的中文版第二版对于中国读者来说,无疑是理解和掌握算法知识的重要资源。书中涵盖了各种基础和高级算法,包括排序、...

    算法导论第1-16章编程题答案

    《算法导论》是计算机科学领域的一本经典著作,它深入浅出地介绍了各种重要的算法,并配以详尽的分析和实例。这份压缩包文件包含了该书第1至16章的部分编程题目的Java实现,对于学习算法和提高编程技能来说,是一个...

    读书笔记:算法导论Java实现.zip

    读书笔记:算法导论Java实现

    算法导论(含原书图片)

    《算法导论》是一本广泛认可的计算机科学经典教材,其深入浅出地介绍了各种算法的设计、分析和实现。这本书的电子版包含了原书的图片,使得读者在阅读过程中能够更好地理解和掌握复杂的算法示意图。"含数学符号"的...

Global site tag (gtag.js) - Google Analytics