heapify

// package whatever; // don't place package name!
/*
subset of binary trees.
min or max heap.

        1
      /   \
      2   3
    /   \  / \
    4   5  6  7
    /
    8

    0
    /\
    1 2
    /\  /\
    3 4 5 6


  Tree implementation:
  insert: O(log n) - O(n)
  deletion: O(n)

  Array: [0,1,2,3,4,5,6]
  insert: O(1)
  deletion: O(n)
  bubbleup:
  bubble down: swap with the smaller child
  insert: O(log(n))
  deletion

  left child : p = (c - 1) / 2
  right child : p = (c - 2) / 2
  left child : c = p * 2 + 1
  right child : c = p * 2 + 2

  heapify:

  [5,3,2,8,1,4,6]

     5
    / \
    3  2
    / \ / \
    8 1 4 6


   /
   6
   / \
   x  x





  [8,5,6,4,2,1]

  8
  / \
  5  6
  / \ /
  4 2 1





*/

import java.io.*;
import java.util.*;

class MyCode {
    public static void main (String[] args) {
    int[] in = new int[]{5,3,2,8,1,4,6};
        System.out.println(Arrays.toString(Heap.heapify(in)));
    }
}
class Heap {
  public static int[] heapify(int[] in){
    for ( int i = in.length - 1; i >= 0; i--){
      in = bubbledown(in,i);
    }
    return in;
  }
  public static int[] bubbledown(int[] in,int p){
    int c = childOf(in,p);
    while (c < in.length && in[c] > in[p]){
      int temp = in[c];
      in[c] = in[p];
      in[p] = temp;
      p = c;
      c = childOf(in,p);
    }
    return in;
  }
  public static int childOf(int[] in,int p){
    int leftC = p * 2 + 1;
    if (leftC >= in.length || in[leftC] > in[leftC + 1]){
      return leftC;
    }
    return leftC + 1;
  }
}
/*
      8
    /   \
    5    6
    / \  /\
    3  1 4 2