import java.util.Arrays;
import javax.management.RuntimeErrorException;
public class MyHeap {
public static void main(String args) {
MyHeap minHeap = new MyHeap(10, true);
minHeap.insert(70);
minHeap.insert(20);
minHeap.insert(90);
minHeap.insert(60);
minHeap.insert(40);
minHeap.insert(10);
minHeap.insert(50);
minHeap.insert(30);
minHeap.insert(80);
minHeap.insert(100);
System.out.println("Min Heap: " + Arrays.toString(minHeap.heap));
MyHeap maxHeap = new MyHeap(10, false);
maxHeap.insert(70);
maxHeap.insert(20);
maxHeap.insert(90);
maxHeap.insert(60);
maxHeap.insert(40);
maxHeap.insert(10);
maxHeap.insert(50);
maxHeap.insert(30);
maxHeap.insert(80);
maxHeap.insert(100);
System.out.println("Max Heap: " + Arrays.toString(maxHeap.heap));
}
private int[] heap;
private int size = 0;
private int capacity;
private boolean reverse;// true if min heap
public MyHeap(int capacity) {
this.capacity = capacity;
heap = new int[capacity];
// max heap by default
this.reverse = false;
}
public MyHeap(int capacity, boolean reverse) {
this.capacity = capacity;
heap = new int[capacity];
this.reverse = reverse;
}
private int compare(int a, int b) {
if (reverse)
return b - a;
return a - b;
}
public void insert(int key) {
if (isFull()) {
throw new IndexOutOfBoundsException("Out of given capacity");
}
heap[size] = key;
swim(size++);
}
// private void rightshift(int parent, int position) {
// for (int i = position; i > parent; i--) {
// if (compare(heap[i], heap[i - 1]) > 0)
// swap(i, i - 1);
// }
// }
private void swim(int position) {
int parent = (position) / 2;
if (position > 0 && compare(heap[parent], heap[position]) < 0) {
swap(parent, position);
// rightshift(parent, position);
swim(parent);
}
}
private void sink(int position) {
int left = position * 2 + 1;
int right = position * 2 + 2;
int largest = position;
if (left < size && compare(heap[position], heap[left]) < 0) {
largest = left;
}
if (right < size && compare(heap[position], heap[right]) < 0) {
largest = right;
}
if (largest != position) {
swap(largest, position);
sink(largest);
}
}
public int getMin() {
if (isEmpty()) {
throw new IllegalStateException("No Data available");
}
if (reverse) {
return heap[size - 1];
}
return heap[0];
}
public int getMax() {
if (isEmpty()) {
throw new IllegalStateException("No Data available");
}
if (reverse) {
return heap[0];
}
return heap[size - 1];
}
public void delTop() {
if (isEmpty()) {
throw new IllegalStateException("No Data Available to delete");
}
swap(0, size - 1);
size--;
sink(0);
}
public void delMin() {
if (isEmpty()) {
throw new IllegalStateException("No Data Available to delete");
}
if (reverse) {
throw new RuntimeErrorException(null, "You Initialized a Min heap");
}
swap(getMin(), 0);
size--;
sink(0);
}
public void delMax() {
if (isEmpty()) {
throw new IllegalStateException("No Data Available to delete");
}
if (!reverse) {
throw new RuntimeErrorException(null, "You Initialized a Max heap");
}
swap(getMax(), 0);
size--;
sink(0);
}
public int size() {
return size - 1;
}
public boolean isFull() {
return size - 1 == capacity;
}
public boolean isEmpty() {
return size == 0;
}
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
@Override
public String toString() {
int[] items = Arrays.copyOf(heap, size);
return Arrays.toString(items);
}
}
Output:
Min Heap: 10, 20, 40, 30, 80, 60, 70, 50, 90, 100
Max Heap: 100, 90, 80, 60, 70, 10, 50, 30, 20, 40
Problem Description:
I'm working on implementing a min-heap and max-heap in Java, but I'm encountering issues with sorting the array correctly. Let me explain the problem through an example:
Let's say we have an array arr initialized as follows: {0, 0, 0} (max heap).
We insert 70, and arr becomes {70, 0, 0}. No further changes will be done. We insert 50, and arr becomes {70, 50, 0}. No further changes will be done. We insert 80, and arr becomes {70, 50, 80}. Here, 80 is greater than its parent (70), so we swap them. After this swap, arr becomes {80, 50, 70}. Now, the array is still not sorted correctly. I attempted to solve this issue by introducing a rightshift function, but it didn't work as expected.
What I've Tried:
I have already implemented the basic structure of the min-heap and max-heap, but I believe the issues are primarily related to the swim, sink, and rightshift functions.
I have made changes to the code, including adjusting the compare function and modifying the swim and sink functions. However, the array is still not sorted as expected.
Question:
I need help fixing the sink, swim, and rightshift functions or any other necessary changes to ensure that the array is correctly sorted for both min-heap and max-heap implementations. Can you please review my code and provide guidance on what needs to be changed to achieve this?
Now, the array is still not sorted correctly.
A heap is not a sorted array, nor is heapsort a matter of just building a heap.
This also means you cannot have both getMin and getMax functions. You can only get the "top" of the heap as a reliable value. The last value in the array is not guaranteed to be the other extreme. For the same reason you cannot have both delMin and delMax functions, only a delTop function, like this:
public void delTop() {
if (isEmpty()) {
throw new IllegalStateException("No Data Available to delete");
}
swap(0, --size);
sink(0);
}
Heapsort consists of building a heap, and then repeatedly deleting the top from a heap that reduces in size and putting the extracted values in a sorted partition (at the end).
Aside from the above remarks, there is one mistake in this part of the sink function:
if (left < size && compare(heap[position], heap[left]) < 0) {
largest = left;
}
if (right < size && compare(heap[position], heap[right]) < 0) {
largest = right;
}
The second if condition compares the entry at position with the one at right, but it should compare the entry at largest. So correct to:
if (left < size && compare(heap[position], heap[left]) < 0) {
largest = left;
}
if (right < size && compare(heap[largest], heap[right]) < 0) {
largest = right;
}
There is also an issue in the functions size() and isFull() as they work with size - 1, while they should use size instead. Here is the correction to both functions:
public int size() {
return size;
}
public boolean isFull() {
return size == capacity;
}
To implement heapsort, you could add this method:
public void sort() {
// HeapSort algorithm:
int origSize = size;
while (size > 1) {
delTop();
}
size = origSize;
// Reverse, so it also is in line with heap property
for (int i = 0, j = size - 1; i < j; i++, j--) {
swap(i, j);
}
}
Call this sort method in your main function:
public static void main(String[] args) {
MyHeap minHeap = new MyHeap(10, true);
minHeap.insert(70);
minHeap.insert(20);
minHeap.insert(90);
minHeap.insert(60);
minHeap.insert(40);
minHeap.insert(10);
minHeap.insert(50);
minHeap.insert(30);
minHeap.insert(80);
minHeap.insert(100);
minHeap.sort();
System.out.println("Min Heap: " + minHeap);
MyHeap maxHeap = new MyHeap(10, false);
maxHeap.insert(70);
maxHeap.insert(20);
maxHeap.insert(90);
maxHeap.insert(60);
maxHeap.insert(40);
maxHeap.insert(10);
maxHeap.insert(50);
maxHeap.insert(30);
maxHeap.insert(80);
maxHeap.insert(100);
minHeap.sort();
System.out.println("Max Heap: " + maxHeap);
}
Now it will print out the values in their sorted order.