[数据结构与算法]堆排序学习心得，一层套一层

堆排序学习心得，一层套一层

堆的结构：可以分为****大根堆*和*小根堆*，是一个完全二叉树*，而堆排序是根据堆的这种数据结构设计的一种排序，下面先来看看什么是大根堆和小根堆

性质：每个结点的值都大于其左孩子和右孩子结点的值，称之为大根堆；每个结点的值都小于其左孩子和右孩子结点的值，称之为小根堆

。

想看完整代码，直接划到最后。

总体步骤分为：构建二叉树、子树按堆排序 || heapify（），进行递归，建好完整堆，最后进行堆排序

首先随便构建二叉树

    public static void main(String[] args) {
        int[] tree = {2,5,3,1,10,4};  //相当于建立树
        int n=6;
         heap_sort(tree,n);
         for (int i=0;i<n;i++){
            System.out.print(tree[i]+" ");
        }
    }

二叉树的

父节点下标=（子节点下标-1）/2

左子节点下标=（父节点下标*2）+1

右子节点下标=（父节点下标*2）+2

    public static  void heapify(int []tree,int n,int i){    //参数分析：树、n为个数，i为根节点下标
        if (i>=n){
            return;
        }
        int c1=2*i+1;
        int c2=2*i+2;
        int max=i;
        if (c1<n&&tree[c1]>tree[max]){
               max=c1;
        }
        if (c2<n&&tree[c2]>tree[max]){
             max=c2;
        }
        if (max!=i){
            swap(tree,i,max);
           heapify(tree,n,max);    
        }

    }

上面执行完，因为是递归一边，也只能完成一边堆。

所以完成整个堆

规律：最后一个节点下标求出父节点，然后递减，去heapify。

    //建好堆
    public static void  build_heap(int []tree,int n){
        //从o开始，所以最后一个节点是n-1；
        int last_node=n-1;
        int last_parent=(last_node-1)/2;
        for (int i=last_node;i>=0;i--){
            //从下面往上递归
            heapify(tree,n,i);
        }
    }

最后进行堆排序。

根节点砍断，然后 heapify。变成少一个数新的堆，不断的砍，知道为0；

看出来的数字，就是从小到大。因为交换的时候 swap(tree,i,0); i是逐渐减少的，意味数组下标逐渐减少，存的数字也是减少的。

    //堆排序
    public static void  heap_sort(int []tree,int n){
        build_heap(tree,n);
        for (int i=n-1;i>=0;i--){
            swap(tree,i,0);
            heapify(tree,i,0);
        }
    }

完整代码

package com.wu.排序;

public class 堆排序 {


    public static void main(String[] args) {
        int[] tree = {2,5,3,1,10,4};
        int n=6;
         heap_sort(tree,n);
        for (int i=0;i<n;i++){
            System.out.print(tree[i]+" ");
        }
    }
   
    //堆排序
    public static void  heap_sort(int []tree,int n){
        build_heap(tree,n);
        for (int i=n-1;i>=0;i--){
            swap(tree,i,0);
            heapify(tree,i,0);
        }
    }

    //建好堆
    public static void  build_heap(int []tree,int n){
        //从o开始，所以最后一个节点是n-1；
        int last_node=n-1;
        int last_parent=(last_node-1)/2;
        for (int i=last_node;i>=0;i--){
            //从下面往上递归
            heapify(tree,n,i);
        }
    }



    public static  void heapify(int []tree,int n,int i){
        if (i>=n){
            return;
        }
        int c1=2*i+1;
        int c2=2*i+2;
        int max=i;
        if (c1<n&&tree[c1]>tree[max]){
               max=c1;
        }
        if (c2<n&&tree[c2]>tree[max]){
             max=c2;
        }
        if (max!=i){
            swap(tree,i,max);
            //即使从下面往上递归，但是上面的父节点和子节点更换时候，
            // 有可能导致子节点（子树的父节点）与下面的子子节点，不满足堆的定义，所以继续递归
           heapify(tree,n,max);
        }

    }
   //交换方法
    private static void swap(int[] tree, int i, int max) {
              int temp=0;
              temp=tree[i];
              tree[i]=tree[max];
              tree[max]=temp;
    }


}