package leetcode832;
import java.util.Arrays;
public class leet832__1 {
/**
* 堆排序最重要的两个函数就是：上浮和下沉
* 上浮：插入元素时发生
* 下沉：删除元素（必发生在顶部）或者修改元素变小
*
* 构建堆：可以从头遍历进行上浮
* 也可以从n/2-1位置进行下沉
*
*
* 堆的一些重要特点：i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2
* @param args
*/
public static void main(String[] args) {
//测试
int [] a= {3,12,20,14,23,44,2,1};
sort(a);
for(int i=0;i<a.length;i++) {
System.out.println(a[i]);
}
}
public static void maxHeapUp(int[] a,int i) {//i就是插入的位置，或者上浮的位置
int j=(i-1)/2;//父节点
int temp=a[i];
while(j>=0&&i!=0) {
if(temp>a[j]) {
// swap(a,i,j);这里不用交换，可以直接下移，记录a[i]初始位置的值就好了,当然换的话可读性好一点,用交换的话 if里就是a[i]>a[j]
a[i]=a[j];
i=j;
j=(i-1)/2;
}else {
break;
}
}
a[i]=temp;
}
public static void maxHeapUp1(int[] a,int i) {//不用考虑i!=0这个条件了，而且代码更好读
int j=(i-1)/2;
while(a[j]<a[i]) {
swap(a,i,j);
i=j;
j=(i-1)/2;
}
}
public static void swap(int[] arr,int a,int b) {
int temp=arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
public static void maxHeapDown(int[] a,int i,int n) {//i是调整节点的坐标，n是长度
int j=2*i+1;
//int temp=a[i];,这里我改用交换的方式了
while(j<n) {
if(j+1<n&&a[j]<a[j+1]) {
j++;
}
if(a[i]>a[j]) {
break;
}
swap(a,i,j);
i=j;
j=2*i+1;
}
}
public static void sort(int[] a) {
//构建堆
for(int i=0;i<a.length;i++) {
maxHeapUp1(a,i);
}
//从最小》最大
int n=a.length-1;
while(n>0) {
swap(a,0,n);
n--;
maxHeapDown(a,0,n);
}
}
}
