Heap.java

import java.util.Arrays;
import java.lang.Math;

class Heap {
    public int[] data;
    public int lastIndex;

    Heap(int size) {
        this.data = new int[size];
        this.lastIndex = -1;
    }

    Heap(int[] data) {
        this.data = data;
        this.lastIndex = data.length - 1;
    }

    public static int parentIndex(int i) {
        return (int) Math.floor((i - 1) / 2);
    }

    public static int leftIndex(int i) {
        return i * 2 + 1;
    }

    public static int rightIndex(int i) {
        return i * 2 + 2;
    }

    public static Heap buildMaxHeap(int[] inputArr) {
        int heapSize = inputArr.length;

        for (int i = Heap.parentIndex(heapSize); i >= 0; i--) {
            Heap.siftDown(inputArr, i);
        }

        return new Heap(inputArr);
    }

    public void insert(int value) {
        this.lastIndex++;
        this.data[this.lastIndex] = value;
        Heap.siftUp(this.data, this.lastIndex, this.lastIndex + 1);
    }

    public void delete(int index) {
        this.data[index] = this.data[this.lastIndex];
        this.lastIndex--;
        Heap.siftDown(this.data, index, this.lastIndex + 1);
    }

    public int extractMax() {
        int rootValue = this.data[0];

        Heap.swap(this.data, 0, lastIndex);
        Heap.siftDown(this.data, 0, lastIndex);
        this.lastIndex--;
        return rootValue;
    }

    public static void siftUp(int[] inputArr, int i) {
        Heap.siftUp(inputArr, i, inputArr.length);
    }

    public static void siftUp(int[] inputArr, int i, int heapSize) {
        if (i == 0) {
            return;
        }

        int parentIndex = Heap.parentIndex(i);
        if (i < inputArr.length && inputArr[i] > inputArr[parentIndex]) {
            Heap.swap(inputArr, i, parentIndex);
            Heap.siftUp(inputArr, parentIndex);
        }
    }

    public static void siftDown(int[] inputArr, int i) {
        Heap.siftDown(inputArr, i, inputArr.length);
    }

    public static void siftDown(int[] inputArr, int i, int heapSize) {
        int biggest = i;
        int leftIndex = Heap.leftIndex(i);
        int rightIndex = Heap.rightIndex(i);

        if (leftIndex < heapSize && inputArr[biggest] < inputArr[leftIndex]) {
            biggest = leftIndex;
        }

        if (rightIndex < heapSize && inputArr[biggest] < inputArr[rightIndex]) {
            biggest = rightIndex;
        }

        if (biggest != i) {
            Heap.swap(inputArr, i, biggest);
            siftDown(inputArr, biggest, heapSize);
        }
    }

    public static int[] swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;

        return arr;
    }

    public String toString() {
        return Arrays.toString(Arrays.copyOfRange(this.data, 0, this.lastIndex + 1));
    }
}

class Main {
    public static void main(String[] args) {
        int[] test = new int[]{1, 2, 3, 4, 5, 6, 7};
        Heap maxHeap = Heap.buildMaxHeap(test);

        // Do your things here
    }
}