一聚教程网:一个值得你收藏的教程网站

热门教程

java 数据结构之堆排序(HeapSort)详解及实例

时间:2022-06-29 01:32:50 编辑:袖梨 来源:一聚教程网

1 堆排序

堆是一种重要的数据结构,分为大根堆和小根堆,是完全二叉树,  底层如果用数组存储数据的话,假设某个元素为序号为i(Java数组从0开始,i为0到n-1),如果它有左子树,那么左子树的位置是2i+1,如果有右子树,右子树的位置是2i+2,如果有父节点,父节点的位置是(n-1)/2取整。最大堆的任意子树根节点不小于任意子结点,最小堆的根节点不大于任意子结点。

所谓堆排序就是利用堆这种数据结构的性质来对数组进行排序,在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的性质可知,最大的值一定在堆顶。堆排序一种不稳定的排序算法,其时间复杂度为O(nlogn)。

2 算法思想

(1)构建最大堆;
(2)选择顶,并与第0位置元素交换;
(3)由于步骤(2)的的交换可能破环了最大堆的性质,即第0位置的元素不再是最大元素,则需要调用maxHeap调整堆(沉降法),根据实际情况重复步骤(2)。

堆排序中最重要的算法就是maxHeap,该函数假设一个元素的两个子节点都满足最大堆的性质(即左、右子树都是最大堆),只有根元素可能违反最大堆性质,那么把该元素以及左右子节点的最大元素找出来,如果该元素已经最大,那么整棵树都是最大堆,程序退出,否则交换根元素与最大元素的位置,继续调用maxHeap构建最大元素所在的子树。

3 Java代码

 

 代码如下复制代码

publicclassHeapSort {

  publicstaticvoidmain(String[] args) {

    int[] arr = {3,2,1,0, -1, -2, -3};

    System.out.println("Before heap:");

    printArray(arr);

    heapSort(arr);

    System.out.println("After heap sort:");

    printArray(arr);

  }

 

  publicstaticvoidheapSort(int[] arr) {

    if(arr ==null|| arr.length <=1) {

      return;

    }

    buildMaxHeap(arr);//构建最大堆

    for(inti = arr.length -1; i >=1; i--) {

      exchangeElements(arr,0, i);//交换堆顶和第0位置元素

      maxHeap(arr, i,0);//因为交换元素后,有可能违反堆的性质,所以沉降元素

    }

  }

 

  privatestaticvoidbuildMaxHeap(int[] arr) {//构建最大堆

    if(arr ==null|| arr.length <=1) {

      return;

    }

    inthalf = arr.length /2;

    for(inti = half; i >=0; i--) {

      maxHeap(arr, arr.length, i);

    }

  }

 

  privatestaticvoidmaxHeap(int[] arr,intheapSize,intindex) {

    intleft = index *2+1;//左子树上的元素

    intright = index *2+2;//右子树上的元素

    intlargest = index;//初始化最大元素

    if(left < heapSize && arr[left] > arr[index]) {

      largest = left;

    }

    if(right < heapSize && arr[right] > arr[largest]) {

      largest = right;

    }

    if(index != largest) {//判断根元素是否为最大元素

      exchangeElements(arr, index, largest);

      maxHeap(arr, heapSize, largest);

    }

  }

 

  publicstaticvoidprintArray(int[] arr) {//打印数组

    System.out.print("{");

    for(inti =0; i < arr.length; i++) {

      System.out.print(arr[i]);

      if(i < arr.length -1) {

        System.out.print(", ");

      }

    }

    System.out.println("}");

  }

 

  publicstaticvoidexchangeElements(int[] arr,intindex1,intindex2) {//交换元素

    inttemp = arr[index1];

    arr[index1] = arr[index2];

    arr[index2] = temp;

  }

}

 

热门栏目