MaxHeap

package homework;

import java.util.Arrays;

public class MaxHeap {
    private int size; // # of nodes
    private int capacity; // array capacity
    private int[] array; // array of nodes

    // constructor for empty heap
    public MaxHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.array = new int[capacity];

    }

    // constructor for array->heap
    public MaxHeap(int[] array) {
        this.capacity = array.length;
        this.size = array.length;
        this.array = array;
        buildHeap();
    }

    private int left(int i) {
        return 2*i + 1;
    }

    private int right(int i) {
        return 2*i + 2;

    }

    private boolean hasLeft(int i) {
        return left(i) < size;
    }

    private boolean hasRight(int i) {
        return right(i) < size;
    }

    private int parent(int i) {
        return (i - 1) / 2;
    }

    private boolean isLeaf(int i) {
        return !hasLeft(i) && !hasLeft(i);
    }

    private void swap(int i, int j) {
        // swap 2 places (nodes) in array (heap)
        int tmp = this.array[i];
        this.array[i] = this.array[j];
        this.array[j] = tmp;
    }

    private void heapifyDown(int i) {
        if (i < this.size && !isLeaf(i)) {
            int index = i;
            if (hasLeft(i) && this.array[left(i)] > this.array[i]) { // left child is larger
                index = left(i);
            }
            if (hasRight(i) && this.array[right(i)] > this.array[index]) { // right child is maximal
                index = right(i);
            }
            if (index != i) {
            swap(i, index); // swap places between i and largest child if exists
            heapifyDown(index);
            }
            else {
                return ;
            }
        }
        else {
            return;
        }

    }

    private void heapifyUp(int i) {
        if (i >= 1 && this.array[i] > this.array[parent(i)]) {
            swap(i, parent(i));
            heapifyUp(parent(i));
        }
        else {
            return;
        }
    }

    // build heap from array
    private void buildHeap() {
        int n = this.size;
        for (int i = n - 1; i >= 0; i--) {
            heapifyDown(i);
        }
    }

    public void insert(int key) {
        if (this.size < this.capacity) {
            this.array[this.size++] = key;
            heapifyUp(this.size - 1);
        }
        else { // array is full
            return;
        }
    }

    public void increaseKey(int i, int inc) {
        if (i > this.size) { // not in heap
            return;
        }
        else {
            this.array[i] += inc;
            heapifyUp(i);
        }
    }

    public void delete (int i) {
        if (i < this.size) {
            this.array[i] = this.array[this.size-1];
            this.size -= 1;
            heapifyDown(i);
            heapifyUp(i);
        }

    }

    public int max() {
        return this.array[0];
    }

    @Override
    public String toString() {
        int[] arr = new int[this.size];
        for (int i = 0; i < this.size; i++) {
            arr[i] = this.array[i];
        }
        return Arrays.toString(arr);
    }


}