java堆排序概念原理介绍

2024-09-28 10:14:00

堆排序介绍：

堆排序可以分为两个阶段。在堆的构造阶段，我们将原始数组重新组织安排进一个堆中；然后在下沉排序阶段，我们从堆中按顺序取出所有元素并得到排序结果。

1.堆的构造，一个有效的方法是从右到左使用sink()下沉函数构造子堆。数组的每个位置都有一个子堆的根节点，sink()对于这些子堆也适用，如果一个节点的两个子节点都已经是堆了，那么在该节点上调用sink()方法可以把他们合并成一个堆。我们可以跳过大小为1的子堆，因为大小为1的不需要sink()也就是下沉操作，有关下沉和上浮操作可以参考我写的优先队列那篇。

2.堆的排序，我们通过第一步操作构造了一个堆，在这个堆中，根节点永远是最大值的节点，所以我们把根节点的值与数组最后的值进行交换，在使用sink()下沉来维护堆的结构即可。

具体代码实现:

public class PQSort{
  public static void main(String[] args){
    int[] a = {9,1,7,5,3,9,12,56,21,45};
    sort(a);
    for(int i=0;i<a.length;i++) {
      System.out.print(a[i]+" ");
    }
  }
  //排序方法
  public static void sort(int[] a){
      int N = a.length-1;
      //通过下沉操作构造堆,因为下标从0开始，所以子节点为2*k+1和2*k+2;
      for(int k = (N-2)/2;k>=0;k--){
        sink(a,k,N);
      }
      //通过不断把堆中最大值放到数组的后面来排序
      while(N>0){
        exch(a,0,N--);
        sink(a,0,N);
      }
  }
  //下沉函数
  private static void sink(int[] a, int i, int n){
    while(2*i+1<=n){
      int j = 2*i+1;
      if(j<n&&a[j]<a[j+1]) j++;
      if(a[i]>a[j]) break;
      exch(a,i,j);
      i=j;
    }
  }
  //交换函数
  private static void exch(int[] a, int i, int j){
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }
}

运行结果:

堆排序实例(Java数组实现)

堆排序:利用大根堆数组全部入堆,再出堆从后向前插入回数组中,数组就从小到大有序了. public class MaxHeap<T extends Comparable<? super T>> { private T[] data; private int size; private int capacity; public MaxHeap(int capacity) { this.data = (T[]) new Comparable[capacity + 1]; size =
Java排序算法总结之堆排序

本文实例讲述了Java排序算法总结之堆排序.分享给大家供大家参考.具体分析如下: 1991年计算机先驱奖获得者.斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd)和威廉姆斯(J．Williams)在1964年共同发明了著名的堆排序算法( Heap Sort ).本文主要介绍堆排序用Java来实现. 堆积排序(Heapsort)是指利用堆积树(堆)这种资料结构所设计的一种排序算法,可以利用数组的特点快速定位指定索引的元素.堆排序是不稳定的排序方法,辅助空间为O(1), 最坏
java 数据结构之堆排序（HeapSort）详解及实例

1 堆排序堆是一种重要的数据结构,分为大根堆和小根堆,是完全二叉树, 底层如果用数组存储数据的话,假设某个元素为序号为i(Java数组从0开始,i为0到n-1),如果它有左子树,那么左子树的位置是2i+1,如果有右子树,右子树的位置是2i+2,如果有父节点,父节点的位置是(n-1)/2取整.最大堆的任意子树根节点不小于任意子结点,最小堆的根节点不大于任意子结点. 所谓堆排序就是利用堆这种数据结构的性质来对数组进行排序,在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的性质可知,最大的
堆排序算法的讲解及Java版实现

堆是数据结构中的一种重要结构,了解了"堆"的概念和操作,可以快速掌握堆排序. 堆的概念堆是一种特殊的完全二叉树(complete binary tree).如果一棵完全二叉树的所有节点的值都不小于其子节点,称之为大根堆(或大顶堆):所有节点的值都不大于其子节点,称之为小根堆(或小顶堆). 在数组(在0号下标存储根节点)中,容易得到下面的式子(这两个式子很重要): 1.下标为i的节点,父节点坐标为(i-1)/2: 2.下标为i的节点,左子节点坐标为2*i+1,右子节点为2*i+2. 堆
java堆排序原理与实现方法分析

本文实例讲述了java堆排序原理与实现方法.分享给大家供大家参考,具体如下: 堆是一个数组,被看成一个近似完全二叉树. 举例说明: 堆的性质: 1.已知元素在数组中的序号为i 其父节点的序号为 i/2的整数其左孩子节点的序号为2*i 其右孩子节点的序号为2*i+1 2.堆分为最大堆和最小堆在最大堆中,要保证父节点的值大于等于其孩子节点的值在最小堆中,要保证父节点的值小于等于其孩子节点的值 java实现堆排序 public class MyHeapSort { public void Hea
Java排序算法之堆排思想及代码实现

在介绍堆排序前,我们需要了解一下一种数据结构 -- 顶堆. 什么是顶堆? 它是一颗完全二叉树,顶堆有大顶堆和小顶堆两种.所谓大顶堆就是在这颗完全二叉树中,任何一颗子树都满足:父结点的值 > 孩子结点的值:小顶堆则相反. 如图: 什么是堆排序(Heapsort)? 利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种.可以利用数组的特点快速定位指定索引的元素. 现在给我们一个无序数组,我们将其从小到大排序,使用堆排序的实现步骤和思想如下: 1.让这个数组变成一个大根堆 2.将最后一
java 实现最小二叉树堆排序的实例

java 实现最小二叉堆排序的实例写在前面: 一觉醒来,我就突然有灵感了...... 最小二叉堆定义: 二叉堆是完全二元树或者是近似完全二元树,最小二叉堆是父结点的键值总是小于或等于任何一个子节点的键值的堆堆. 存储: 二叉堆一般用数组来表示. 根节点在数组中的位置是0,第n个位置的子节点分别在2n+1和 2n+2: 位置k的叶子的父节点位置为(k-1)/2: 实现: /** * @description 元素添加到末尾,和它的父节点比,如果比它小就交换 * @param array * *
Java实现堆排序(Heapsort)实例代码

复制代码代码如下: import java.util.Arrays; public class HeapSort { public static void heapSort(DataWraper[] data){ System.out.println("开始排序"); int arrayLength=data.length; //循环建堆 for(int i=0;i<arrayLength-1;i++){
Java 堆排序实例(大顶堆、小顶堆)

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法.堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点. 堆排序的平均时间复杂度为Ο(nlogn) . 算法步骤: 1. 创建一个堆H[0..n-1] 2. 把堆首(最大值)和堆尾互换 3. 把堆的尺寸缩小1,并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置 4. 重复步骤2,直到堆的尺寸为1 堆: 堆实际上是一棵完全二叉树,其任何一非叶节点满足性质:
详解堆排序算法原理及Java版的代码实现

概述堆排序是一种树形选择排序,是对直接选择排序的有效改进. 堆的定义如下:具有n个元素的序列(k1,k2,...,kn), 当且仅当满足: 时称之为堆.由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)或最大项(大顶堆). 若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点(有子女的结点)的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的. (a)大顶堆序列:(96, 83, 27, 38, 11, 09) (b)小顶堆序列:(12, 36,

java堆排序概念原理介绍

相关推荐

随机推荐