BinaryHeap.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
import java.util.stream.IntStream; import java.util.stream.Collectors; public class BinaryHeap { int[] heap; int size = 0; int maxSize = 10; public BinaryHeap(){ heap = new int[maxSize]; } public int parentIdx(int idx){ return (idx-1)/2; } public int leftChildIdx(int idx){ return (2 * idx) + 1; } public int rightChildIdx(int idx){ return (2 * idx) + 2; } public void insert(int k){ if (size == maxSize) return; //We'd ideally want to implement resizing... heap[size++] = k; for (int i = size - 1; heap[parentIdx(i)] > heap[i]; i = parentIdx(i)) swap(i, parentIdx(i)); } public int removeRoot(){ if (size == 0) return Integer.MAX_VALUE; if (size == 1){ size--; return heap[0]; } int rootVal = heap[0]; heap[0] = heap[size-1]; size--; heapify(0); return rootVal; } public void heapify(int idx){ int leftIdx = leftChildIdx(idx); int rightIdx = rightChildIdx(idx); int minIdx = idx; if (leftIdx < size && heap[leftIdx] < heap[minIdx]) minIdx = leftIdx; if (rightIdx < size && heap[rightIdx] < heap[minIdx]) minIdx = rightIdx; if (minIdx != idx){ swap(idx, minIdx); heapify(minIdx); } } public void printArr(int[] arr){ System.out.println(IntStream.of(arr) .boxed() .map(Object::toString) .limit(size) .collect(Collectors.joining(", "))); } private void swap(int idx1, int idx2){ int i1 = heap[idx1]; heap[idx1] = heap[idx2]; heap[idx2] = i1; } public static void main(String[] args){ BinaryHeap h = new BinaryHeap(); h.insert(9); h.insert(3); h.printArr(h.heap); h.insert(6); h.insert(5); h.insert(8); h.insert(1); h.printArr(h.heap); System.out.println("Min Val: " + h.removeRoot()); h.printArr(h.heap); } } |