数据结构之堆

package com.hfm.util;

import java.util.Arrays;

public class Heap {
    int arr[];

    public Heap(int[] arr) {
        this.arr = arr;
        print(arr);
        build(arr,arr.length-1,arr.length-1);
        System.out.println();
        print(arr);
    }

    private int getHeight(int arr[]){
        return (int)Math.ceil(Math.log(1+arr.length)/Math.log(2));
    }

    private static void print(int arr[]){
        int height = 0,count = 0;
        while(count<arr.length){
            int num = ((int) Math.pow(2, height));
            for(int i=0;i<num&&(count<arr.length);i++){
                System.out.print(arr[count]+"\t");
                count ++;
            }
            height++;
            System.out.println();
        }
    }

    private void swap(int arr[],int x,int y){
        arr[x] += arr[y];
        arr[y] = arr[x] - arr[y];
        arr[x] = arr[x] - arr[y];
    }

    private void build(int arr[],int curNotLeaf,int visited){ // 大根堆的构建
        if(visited==0)
            return;
        int parent = ((int) Math.ceil(curNotLeaf / 2.0))-1>-1? ((int) Math.ceil(curNotLeaf / 2.0))-1:0,last = 0;
        while (parent>-1){
            if(arr[curNotLeaf]>arr[parent]){
                swap(arr,curNotLeaf,parent);
                last = parent;
                curNotLeaf = parent;
                parent = ((int) Math.ceil(parent / 2.0))-1>-1? ((int) Math.ceil(parent / 2.0))-1:0;
                continue;
            }
            break;
        }
        //交换叶子节点最大值和当前值
        int res[] = null;
        while((res = maxLeaf(arr,last))[0]!=-Integer.MAX_VALUE){
            if(res[0] != -Integer.MAX_VALUE){
                if(arr[last]<arr[res[1]]){
                    swap(arr,res[1],last);
                }
                last = res[1];
            }
        }
        build(arr,--visited, visited);
    }

    private int[] maxLeaf(int arr[],int index){
        if(index*2+1>arr.length-1)
            return new int[]{-Integer.MAX_VALUE,-Integer.MAX_VALUE};
        if(index*2+2>arr.length-1)
            return new int[]{arr[index*2+1],index*2+1};
        else
            return arr[index*2+1]>=arr[index*2+2]?new int[]{arr[index*2+1],index*2+1}:new int[]{arr[index*2+2],index*2+2};
    }
    public static void main(String[] args) {
        Heap heap = new Heap(new int[]{5,8,13,2,7,12,15,2});
    }
}