package Heap; import java.util.StringJoiner; public class Heap { private int size; private int[] data; private boolean mode_max; // true = max heap, false = min heap Heap() { size = 0; data = new int[1000]; // Initializing with some large size for simplicity mode_max = true; } Heap(boolean mode) { this(); // Call the default constructor mode_max = mode; } void setModeMax(boolean mode) { mode_max = mode; } private int parent(int i) { return (i - 1) / 2; } private int left(int i) { return 2 * i + 1; } private int right(int i) { return 2 * i + 2; } void heaptify(int i) { int largestOrSmallest = i; int l = left(i); int r = right(i); if (mode_max) { if (l < size && data[l] > data[largestOrSmallest]) largestOrSmallest = l; if (r < size && data[r] > data[largestOrSmallest]) largestOrSmallest = r; } else { if (l < size && data[l] < data[largestOrSmallest]) largestOrSmallest = l; if (r < size && data[r] < data[largestOrSmallest]) largestOrSmallest = r; } if (largestOrSmallest != i) { // Swap int temp = data[i]; data[i] = data[largestOrSmallest]; data[largestOrSmallest] = temp; heaptify(largestOrSmallest); } } void insert(int value) { if (size == data.length) return; // Heap overflow size++; int i = size - 1; data[i] = value; // Fix the heap property while (i != 0 && (mode_max ? data[parent(i)] < data[i] : data[parent(i)] > data[i])) { int temp = data[i]; data[i] = data[parent(i)]; data[parent(i)] = temp; i = parent(i); } } void delete(int value) { // Find the index of the value to be deleted int index = -1; for (int i = 0; i < size; i++) { if (data[i] == value) { index = i; break; } } // If value is not found, return if (index == -1) return; // Replace the value with the last element in the heap data[index] = data[size - 1]; size--; // Restore heap property heaptify(index); } void show_array() { StringJoiner stringJoiner = new StringJoiner(" ", "[", "]"); for (int i = 0; i < size; i++) { stringJoiner.add(String.valueOf(data[i])); } System.out.println(stringJoiner); } private int calculateHeapHeight(int n) { return (int) Math.floor(Math.log(n + 1) / Math.log(2)); } void show_tree() { int i = 0; int h = calculateHeapHeight(size); for (int l = 0; l <= h; l++) { for (int j = 0; j < Math.pow(2, l) && i < size; j++) { System.out.print(data[i++] + " "); } System.out.println(); } } }

heap in java

Related code examples

Code examples by languages