DS: Max Heap

MaxHeap.java

import java.util.Arrays;

/**
 * MAX_HEAP: the root will always be the largest value
 */
public class MaxHeap {
    private int[] data;
    private int size;

    public MaxHeap(int size) {
        this.data = new int[size];
    }

    private void swap(int i, int j) {
        int t = this.data[j];
        this.data[j] = this.data[i];
        this.data[i] = t;
    }

    // TODO: Fix implementation
    private void bubbleUp() {
        int i = this.size;
        while (i > 0) {
            int p = i / 2;
            if (this.data[i] > this.data[p]) {
                this.swap(i, p);
                i = p;
            } else {
                return;
            }
        }
    }

    // TODO: Fix implementation
    private void bubbleDown() {
        int i = 0;
        while (i < this.size) {
            int l = 2 * i;
            int r = 2 * i + 1;
            if (this.data[i] < this.data[l]) {
                this.swap(i, l);
                i = l;
            } else if (this.data[i] < this.data[r]) {
                this.swap(i, r);
                i = r;
            } else {
                return;
            }
        }
    }

    public void add(int value) {
        this.data[this.size] = value;
        this.bubbleUp();
        this.size += 1;
    }

    public int peek() {
        return this.data[0];
    }

    public int poll() {
        int max = this.data[0];
        this.size -= 1;
        this.data[0] = this.data[this.size];
        this.data[this.size] = 0;
        this.bubbleDown();
        return max;
    }

    @Override
    public String toString() {
        return Arrays.toString(this.data);
    }

    public static void main(String[] args) {
        MaxHeap heap = new MaxHeap(6);
        heap.add(4);                            // [4, 0, 0, 0, 0, 0]
        heap.add(7);                            // [7, 4, 0, 0, 0, 0]
        heap.add(10);                           // [10, 7, 4, 0, 0, 0]
        heap.add(3);                            // [10, 7, 4, 3, 0, 0]
        System.out.println(heap.poll());        // 10
        System.out.println(heap);               // [7, 4, 3, 0, 0, 0]
        heap.add(5);                            // [7, 5, 3, 4, 0, 0]
        heap.add(1);                            // [7, 5, 3, 4, 1, 0]
        System.out.println(heap.poll());        // 7
        System.out.println(heap);               // [5, 3, 1, 4, 0, 0]
    }
}