十大排序之堆排序

十大排序之堆排序（HeapSort）

十大排序之快速排序

十大排序之归并排序

十大排序插入排序

十大排序之 堆排序

十大排序之冒泡排序

扫码关注公众号，更多资料尽在掌握。

1.简介
堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。
堆排序的时间复杂度是：O(nlogn) 空间复杂度：O(1).
说到堆排序就不得不提到完全二叉树了。什么是完全二叉树呢？

完全二叉树定义：
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
一颗普通的完全二叉树：
在这里插入图片描述

我们把堆又分为大根堆和小根堆，

大根堆：根结点的键值是所有堆结点键值中最大者，在堆排序算法中用于升序排列。
在这里插入图片描述

小根堆：根结点的键值是所有堆结点键值中最小者，在堆排序算法中用于降序排列；
在这里插入图片描述

2.图解步骤

利用堆排序的实现排序的思路也很简单：

第一步、将待排序数组构建成一个堆（大根堆或者小根堆，一般用大根堆来升序排序）；
第二步、把堆首（最大值）和堆尾互换；取出最大的元素（此时堆个数减一）；
第三步、重新构建大根堆；
第四步、重复第二步，第三步，知道堆的大小为1，完成排序。

图解：
假设待排序数组：1，5，2，12，10，9

假设我们使用大根堆来排序：
在这里插入图片描述

将堆首元素和堆尾元素交换：
在这里插入图片描述

剔除最后一个元素，然后将剩下的元素，重新构建成一个堆。
在这里插入图片描述

继续交换堆首元素和堆尾元素
在这里插入图片描述

剔除最后一个元素，然后将剩下的元素，重新构建成一个堆。
在这里插入图片描述
交换：

剔除，构建堆。

在这里插入图片描述

交换，剔除。
在这里插入图片描述

最终完成排序：

1 2 5 9 10 12

3.代码实现

用大根堆实现排序：

package com.znzz.heapSort;


import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {2,4,1,8,20,3,6};
       new HeapSort().heap_sort(arr, arr.length);
        System.out.println(Arrays.toString(arr));
    }

    /**
     *
     * @param arr  待排数组
     * @param n    数组元素
     * @param i    对哪个节点做heapify
     */
    void heapify(int arr[], int n, int i){

        if(i >= n){
            return;
        }
           int c1 = 2 * i + 1;
           int c2 = 2 * i + 2;

           int max = i;
           if(c1 < n && arr[c1] > arr[max]){
               max = c1;
           }
           if(c2 < n && arr[c2] > arr[max]){
             max = c2;
           }
           if(max != i){
               swap(arr,max ,i);
               heapify(arr,n,max);
           }


}

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;

    }


    void build_heap(int arr[], int n){
        int last_node = n -1;
        int parent = (last_node -1) /2;
        int i;
        for (i = parent; i >= 0; i--) {
            heapify(arr,n,i);
        }

    }


  void  heap_sort(int arr[], int n){
        build_heap(arr,n);
      for (int i = n -1; i >= 0 ; i--) {
            swap(arr,i,0);
            heapify(arr,i ,0);
      }
    }

}