Heap
Insert in Heap, Delete in Heap, Heapify and HeapSort using max_heap (code in JAVA)
import java.util.ArrayList;
import java.util.Scanner;
public class _heap {
private static int heapSize;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of elements: ");
int n = scanner.nextInt();
ArrayList<Integer> arr = new ArrayList<>();
System.out.println("Enter the elements:");
for (int i = 0; i < n; i++) {
arr.add(scanner.nextInt());
}
buildMaxHeap(arr);
System.out.println("Max Heap after heapify: " + arr);
while (true) {
System.out.println("\nChoose operation:");
System.out.println("1. Insert a node");
System.out.println("2. Delete maximum element");
System.out.println("3. HeapSort and Exit");
int choice = scanner.nextInt();
if (choice == 1) {
System.out.print("Enter the element to insert: ");
int element = scanner.nextInt();
insert(arr, element);
System.out.println("Node inserted in heap: " + arr);
} else if (choice == 2) {
int max = extractMax(arr);
System.out.println("Maximum element removed from heap: " + max);
System.out.println("Heap after deletion: " + arr);
} else if (choice == 3) {
heapSort(arr);
System.out.println("Sorted array: " + arr);
break;
} else {
System.out.println("Invalid choice. Please try again.");
}
}
scanner.close();
}
private static void buildMaxHeap(ArrayList<Integer> arr) {
heapSize = arr.size();
for (int i = (heapSize / 2) - 1; i >= 0; i--) {
heapify(arr, i);
}
}
private static void heapify(ArrayList<Integer> arr, int i) {
heapify(arr, i, heapSize);
}
private static void heapify(ArrayList<Integer> arr, int i, int n) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr.get(left) > arr.get(largest)) {
largest = left;
}
if (right < n && arr.get(right) > arr.get(largest)) {
largest = right;
}
if (largest != i) {
int temp = arr.get(i);
arr.set(i, arr.get(largest));
arr.set(largest, temp);
heapify(arr, largest, n);
}
}
private static void insert(ArrayList<Integer> arr, int element) {
heapSize++;
int i = heapSize - 1;
arr.add(i, element);
while (i > 0 && arr.get((i - 1) / 2) < arr.get(i)) {
int parentIndex = (i - 1) / 2;
int temp = arr.get(i);
arr.set(i, arr.get(parentIndex));
arr.set(parentIndex, temp);
i = parentIndex;
}
}
private static int extractMax(ArrayList<Integer> arr) {
if (heapSize <= 0) {
System.out.println("Heap is empty, cannot delete.");
return -1;
}
int root = arr.get(0);
arr.set(0, arr.remove(heapSize - 1));
heapSize--;
heapify(arr, 0);
return root;
}
private static void heapSort(ArrayList<Integer> arr) {
int n = arr.size();
// Build a max heap
buildMaxHeap(arr);
// Extract elements one by one
for (int i = n - 1; i >= 0; i--) {
int temp = arr.get(0);
arr.set(0, arr.get(i));
arr.set(i, temp);
heapify(arr, 0, i);
}
}
}
No comments:
Post a Comment