package com.eshore.sweetop.dataframe;
import java.util.Arrays;
public class MaxHeapQeuen {
private static int parent(int i) {
return (i - 1) >> 1;
}
private static int left(int i) {
return i << 1 | 1;
}
private static int right(int i) {
return (i + 1) << 1;
}
private static void maxHeapify(int[] a, int i, int size) {
int l = left(i);
int r = right(i);
int largest = -1;
if (l < size && a[l] > a[i]) {
largest = l;
} else {
largest = i;
}
if (r < size && a[r] > a[largest]) {
largest = r;
}
if (largest != i) {
a[i] ^= a[largest];
a[largest] ^= a[i];
a[i] ^= a[largest];
maxHeapify(a, largest, size);
}
}
public static void buildMaxHeap(int[] a) {
for (int i = a.length / 2 - 1; i > -1; i--) {
maxHeapify(a, i, a.length);
}
}
private static int max(int[] a) {
return a[0];
}
private static int exmax(int[] a) {
int max = a[0];
a[0] = a[a.length - 1];
maxHeapify(a, 0, a.length - 1);
return max;
}
private static void set(int[] a, int i, int value) {
if (value < a[i]) {
throw new RuntimeException(
"new value is smaller than current value ");
}
a[i] = value;
while (i > 0 && a[parent(i)] < a[i]) {
a[i] ^= a[parent(i)];
a[parent(i)] ^= a[i];
a[i] ^= a[parent(i)];
i = parent(i);
}
}
private static int[] incream(int[] a) {
int[] b = new int[a.length + 1];
for (int i = 0; i < a.length; i++) {
b[i] = a[i];
}
return b;
}
private static void add(int[] a, int value) {
a[a.length-1] = Integer.MIN_VALUE;
set(a, a.length - 1, value);
}
public static void main(String[] args) {
int[] a = { 2, 3, 6, 11, 4, 7, 12, 9, 5, 13 };
buildMaxHeap(a);
a = incream(a);
add(a, 14);
System.out.println(max(a));
}
}