'Heaps methods in JAVA
I have to implement two methods, downHeap and upHeap methods. But unfortunately I don't know how I can do that..
I tried to implement the upHeap but I don't know if it's okay. Unfortunately, the others method I don't know how to do it.
import java.util.*;
class Heap {
private static final int d = 2;
private int[] heap;
private int heapSize;
public Heap(int capacity) {
heapSize = 0;
heap = new int[capacity + 1];
Arrays.fill(heap, -1);
}
public boolean isEmpty() {
return heapSize == 0;
}
public boolean isFull() {
return heapSize == heap.length;
}
private int parent(int i) {
return (i - 1) / d;
}
private int kthChild(int i, int k) {
return d * i + k;
}
public void insert(int x) {
if (isFull())
throw new UnsupportedOperationException("Heap is full");
heap[heapSize++] = x;
upHeap(heapSize - 1);
}
public int delete(int x) {
if (isEmpty())
throw new NoSuchElementException("Heap is empty");
int key = heap[x];
heap[x] = heap[heapSize - 1];
heapSize--;
downHeap(x);
return key;
}
// maintain heap property during insertion
private void upHeap(int i) {
int aux;
if (heap[i]<heap[parent(i)]){
aux=heap[i];
heap[i]=heap[parent(i)];
heap[parent(i)]=aux;
}
}
// maintain heap property during deletion
private void downHeap(int i) {
int maxi=maxChild(i);
}
private int maxChild(int i) {
/**
* This method returns -1 in case the node has no children
*/
int leftChild = kthChild(i, 1);
int rightChild = kthChild(i, 2);
if (leftChild < heap.length && rightChild < heap.length) {
return heap[leftChild] > heap[rightChild] ? leftChild : rightChild;
} else if (rightChild < heap.length) {
return heap[rightChild];
} else if (leftChild < heap.length) {
return heap[leftChild];
}
return -1;
}
public void printHeap() {
for (int i = 0; i < heapSize; i++)
System.out.print(heap[i] + " ");
System.out.println();
}
// return max from the heap
public int findMax() {
if (isEmpty())
throw new NoSuchElementException("Heap is empty.");
return heap[0];
}
public int[] getHeap() {
// This method is used for autotesting
return heap;
}
}
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
