Algorithm: Implement my own Heap

Heap

A heap is a specialized tree-based data structure that satisfies the heap property:

in a max heap, for any given node C, if P is a parent node of C, then the value of P is equal or greater than the key of C

in a min heap, the key of P is equal or less than the key of C

PriorityQueue in Java is an instance of Heap.

Heap Implementaion

Heap should at least implement one method, which is peak & pop the max/min value inside it.

// we are going to implement a Max Heap, which means
// root node is the biggest node
public class MyHeap {
    int size;
    int[] arr;
    
    public MyHeap(int size) {
        this.size = 0;
        arr = new int[size];
    }
    
    public int pop() {
        int max = arr[0];
        arr[0] = arr[--size];
        heapify(0);
        return max;
    }
    
    public int peek() {
        return arr[0];
    }
    
    public void insert(int i) {
        if (size == arr.length) {
            return;
        }
        arr[size] = i;
        heapInsert(size++);
    }
    
    private void heapInsert(int index) {
        int parentIndex = (index - 1) / 2;
        while(arr[parentIndex] < arr[index]) {
            swap(parentIndex, index);
            index = parentIndex;
            parentIndex = (index - 1) / 2;
        }
    }
    
    private void heapify(int index) {
        int leftChildIndex = index * 2 + 1;
        int maxChildIndex = leftChildIndex;
        while (leftChildIndex < size) {
            if (leftChildIndex + 1 < size) {
                maxChildIndex = arr[leftChildIndex] > arr[leftChildIndex + 1] ? leftChildIndex : leftChildIndex + 1;
            } else {
                maxChildIndex = leftChildIndex;
            }
            if (arr[index] < arr[maxChildIndex]) {
                swap(index, maxChildIndex);
                index = maxChildIndex;
                leftChildIndex = index * 2 + 1;
            } else {
                break;
            }
        }
    }
    
    private void swap(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}