Untitled

mail@pastecode.io avatar
unknown
java
a year ago
1.9 kB
3
Indexable
Never
public class MinHeap {

	private int[] heap;
	private int size;

	public MinHeap(int capacity) {
		heap = new int[capacity];
		size = 0;
	}

	public MinHeap(int[] arr) {
		heap = new int[arr.length]
		System.arraycopy(arr, 0, heap, 0, arr.length);
		size = arr.length;
		buildMinHeap();
	}

	public void offer(int data) {
		if (isFull()) {
			int[] newHeap = new int[heap.length * 2];
			System.arraycopy(heap, 0, newHeap, 0, size);
			heap = newHeap;
		}
		heap[size] = data;
		heapifyUp(size);
		size++;
	}

	public void heapifyUp(int i) {
		int parent = (i - 1) / 2;
		if (i > 0 && heap[i] < heap[parent]) {
			swap(i, parent);
			heapifyUp(parent);
		}
	}

	public int poll() {
		if (isEmpty()) {
			throw new IllegalStateException("The heap is empty.");
		}
		int data = heap[0];
		heap[0] = heap[--size];
		heapifyDown(0);
		return data;
	}

	public void heapifyDown(int i) {
		int smallest = i;
		int left = 2 * i + 1;
		int right = 2 * i + 2;

		if (left < size && heap[left] < heap[smallest]) {
			smallest = left;
		}
		if (right < size && heap[right] < heap[smallest]) {
			smallest = right;
		}
		if (smallest != i) {
			swap(i, smallest);
			heapifyDown(smallest);
		}
	}

	public int peek() {
		if (isEmpty()) {
			throw new IllegalStateException("The heap is empty.");
		}
		return heap[0];
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public boolean isFull() {
		return size == heap.length;
	}

	public void swap(int i, int j) {
		int temp = heap[i];
		heap[i] = heap[j];
		heap[j] = temp;
	}

	public boolean isMinHeap() {
		for (int i = 0; i <= (size - 2) / 2; i++) {
			int left = 2 * i + 1;
			int right = 2 * i + 2;
			if (left < size && heap[left] < heap[i] || right < size && heap[right] < heap[i]) {
				return false;
			}
		}
		return true;
	}

	public void buildMinHeap() {
		for (int i = (size / 2) - 1; i >= 0; i--) {
			heapifyDown(i);
		}
	}

}