package com.lxf.sort;

public class HeapifySort {
    public static void main(String[] args) {
        int[] nums = new int[]{3,4,1,7,9,2,4};
        //堆排序算法
        sort(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]);
        }
    }
    public  static void sort(int[] a){
        for (int i=a.length-1;i>0;i--){
            //堆排序,排完序堆顶就是最大数字了
            max_heapify(a,i);

            //堆顶元素与数组a[i]交换
            int temp=a[0];
            a[0]=a[i];
            a[i]=temp;
        }
    }

    public static void max_heapify(int[] a, int n) {
        int child;
        for (int i=(n-1)/2;i>=0;i--){
            //左子节点的位置
            child=2*i+1;
            //右子节点存在且大于左子节点，child变成右子节点
            if(child!=n&&a[child]<a[child+1]){
                child++;
            }
            //如果父节点小于左右子节点的最大值则交换父节点和左右节点的最大值
            if(a[i]<a[child]){
                int temp=a[i];
                a[i]=a[child];
                a[child]=temp;
            }
        }
    }
}

2.3、排序代码（C语言版，真的大根堆）

//交换数组元素
void Swap(int* A,int i,int j){
	A[i]=A[j]^A[i];
	A[j]=A[j]^A[i];
	A[i]=A[j]^A[i];
}
//数组大根堆化
void Heapify(int* A,int n,int i){
	int c1=2*i+1;//左子结点 
	int c2=2*i+2;//右子结点
	int max=i;//根结点
	if(c1<n&&A[max]<A[c1]){
		max=c1;
	}
	if(c2<n&&A[max]<A[c2]){
		max=c2;
	}
	if(max!=i){
		Swap(A,max,i);//交换数组的两个元素 
		Heapify(A,n,max);//递归向下heapify 
	}
} 
//建堆
void BuildMaxHeap(int* A,int n){
	for(int i=(n-1)/2;i>=0;i--){
		Heapify(A,n,i);
	}
}
//堆排序
void HeapSort(int* A,int n){
	BuildMaxHeap(A,n);//建堆
	for(int i=n-1;i>0;i--){
		Swap(A,0,i);
		Heapify(A,i,0);
	} 
}