`
hongjn
  • 浏览: 56513 次
  • 性别: Icon_minigender_1
  • 来自: 火星
社区版块
存档分类
最新评论

堆排序(HeapSort) Java实现

阅读更多
堆排序的思想是利用数据结构--。具体的实现细节:
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
1
0
分享到:
评论
2 楼 LSQ6063 2012-02-14  
这个图显示的有待商确
1 楼 javaeye官理员 2011-12-14  

相关推荐

    堆排序的Java实现最大堆方法HeapSort

    堆排序的Java实现最大堆方法HeapSort,堆排序是一种树形选择排序,sort方法首先构建最大堆,然后将根节点与最后一个节点交换,并重新构建最大堆,然后再次交换根节点与倒数第二个节点,以此类推,直到整个数组排序...

    堆排序之Java实现

    以下是Java实现堆排序的基本步骤: 1. 构建大顶堆:从最后一个非叶子节点(即最后一个元素的父节点)开始,自底向上、自右向左进行调整,确保每个节点都大于或等于其子节点。 2. 交换堆顶元素与末尾元素:将最大...

    堆排序算法(java)

    java的堆排序算法实现程序,含测试,可直接运行。java的堆排序算法实现程序,含测试,可直接运行。

    堆排序 java实现

    堆排序是一种基于比较的排序算法,它...总之,这个Java实现的堆排序示例提供了理解堆排序算法和实践编程技巧的机会。通过对随机数据的不断测试,我们可以确信这个实现是可靠的,并且能够在各种输入条件下正确地工作。

    Java实现堆排序(Heapsort)实例代码

    堆排序(Heapsort)是一种基于比较的排序算法,它利用了数据结构中的二叉堆特性。在Java中,我们可以通过编写相应的代码来实现堆排序。以下是对标题和描述中涉及的知识点的详细说明: 1. **二叉堆**: - 二叉堆是一...

    堆排序JAVA实现代码

    以下将详细介绍堆排序的原理、步骤以及Java实现。 **堆排序的原理** 堆排序的核心思想是构建一个完全二叉树,即堆,然后通过调整堆结构,使得根节点(最大元素或最小元素)总能处于正确的位置。这个过程分为两个...

    Java实现堆排序.rar

    本文件“Java实现堆排序.rar”可能包含了用Java语言编写的堆排序算法的源代码示例。下面我们将深入探讨堆排序的基本原理、步骤以及如何在Java中实现。 堆排序的核心是构建一个大顶堆或小顶堆。在大顶堆中,每个节点...

    堆排序 Java代码示例

    附件是堆排序Java代码示例,文件绿色安全,请大家放心下载,仅供交流学习使用,无任何商业目的! 堆排序是一种高效的比较类排序算法,它利用了二叉堆的数据结构来实现排序。堆排序可以分为两个主要步骤:建堆(将...

    堆排序Java代码示例

    附件是堆排序Java代码示例,文件绿色安全,请大家放心下载,仅供交流学习使用,无任何商业目的! 堆排序是一种高效的比较类排序算法,它利用了二叉堆的数据结构来实现排序。堆排序可以分为两个主要步骤:建堆(将...

    堆排序算法详解及其 Java 实现

    ### 堆排序算法详解及其Java实现 #### 一、堆排序概述 堆排序是一种非常高效的排序算法,它利用了二叉堆的数据结构来完成排序的过程。二叉堆可以分为最大堆和最小堆两种类型。最大堆指的是父节点的值总是大于或...

    堆排序介绍和java代码实现

    在 Java 语言中,堆排序可以通过构建最大堆,然后不断地取出堆顶元素并重新调整堆结构来实现。下面是一个简单的 Java 实现代码: ```java public class HeapSort { public static void heapSort(int[] arr) { int...

    Java实现堆排序

    Java实现堆排序分为两个主要步骤: 1. **建立堆**: - 首先,将待排序的数组视为一个大根堆(或小根堆)。对于数组中的每个非叶子节点,如果其值小于其子节点的值,则交换它们,这样可以确保从根节点到叶节点的每...

    java实现的shell排序快速排序归并排序堆排序

    `shellsort.java`文件应该包含了这个过程的Java实现。 2. **快速排序**: 快速排序是由C.A.R. Hoare在1960年提出的,它是基于分治策略的一种高效排序算法。快速排序的基本思想是选择一个基准元素,然后将数组分为...

    堆排序算法Java面向对象实现源码

    下面我们将深入探讨堆排序算法以及如何用Java面向对象的方式实现它。 首先,我们需要理解堆的数据结构。堆是一种特殊的树形数据结构,每个节点都有一个值,且满足以下性质:对于大顶堆,父节点的值总是大于或等于其...

    容易理解的堆排序代码(JAVA)

    在这个主题中,我们将深入探讨堆排序的概念、工作原理以及如何用Java实现它。首先,我们需要理解堆是什么。 堆是一个近似完全二叉树的结构,并同时满足堆的性质:即父节点的键值或索引总是大于或小于(在最大堆和...

    堆排序,和其他排序 java 实现

    在Java中实现堆排序时,我们通常会采用大顶堆或者小顶堆来组织数据。堆排序的时间复杂度为O(n log n),空间复杂度为O(1)。 #### 二、堆排序的步骤 1. **构建初始堆**:将无序序列构造成一个大顶堆或小顶堆。 2. **...

    Java实现堆排序算法(源代码)

    下面是一个使用Java实现的堆排序示例,其中包含了一个用于调整堆的辅助方法 `adjustHeap` 和排序方法 `heapSort`。 ```java public class HeapSort { // 调整堆 private static void adjustHeap(int[] arr, int i...

    堆排序的原理和代码实现

    在提供的代码中,`heapSort`方法是堆排序的主要实现。它首先调用`buildMaxHeap`来构建大顶堆,然后通过`swap`方法交换堆顶元素和数组末尾元素,并打印出最大元素。随着数组长度的减少,继续调用`buildMaxHeap`来重建...

    java堆排序

    根据提供的信息,我们可以深入探讨Java中的堆排序以及几种常见的排序算法。这包括堆排序、快速排序、冒泡排序和选择排序等。 ### 堆排序 堆排序是一种基于比较的排序算法,它利用了二叉堆的数据结构。二叉堆可以是...

Global site tag (gtag.js) - Google Analytics