I have to construct a program that find the k-th smallest integer in a given set S of numbers; read from the standard input a first line containing positive integers N, k, and d separated by spaces. Each of the following N lines contains a positive integer of the set S. I have to implement a generic d-ary heap class that implements all methods of the priority queue interface.
i have the following code...but the inserting bubbling doesnt seem to wokr right...
any help would be great:
import java.util.*;
public class Heap {
static Element[] heap;
int N;
static int k;
int d;
static int size = 0;
Compare comp;
public Heap(int nodes, int max, Compare c)
{
N = max;
d = nodes;
heap = new Element[N];
comp = c;
}
public static void main(String args[])
{
Scanner _scan = new Scanner(System.in);
// String Nkd = _scan.nextLine();
// Scanner _scanNkd = new Scanner(Nkd);
int _N = 0;
int _d = 0;
Compare _c = new Compare();
_N = _scan.nextInt();
k = _scan.nextInt();
_d = _scan.nextInt();
Heap _heap = new Heap(_d,_N,_c);
int i=0;
int num=0;
while(_scan.hasNextLine()&&num<_N)
{
System.out.println("test" + _scan.nextInt());
_heap.insert(i, _scan.nextInt());
i++;
size++;
num++;
}
for(int z=0;z<_N;z++)
{
// System.out.println(heap[z].getKey());
}
/*
Element kth = null;
for(int j = 1; j <=k; j++)
{
kth = _heap.removeMin();
}
System.out.print(kth.getKey());
System.out.print('\n');
*/
/*System.out.print(k);
System.out.print('\n');
System.out.print(_heap.size());
System.out.print('\n');
System.out.print('\n');
System.out.print(heap[0].getKey());
System.out.print('\n');
System.out.print(heap[1].getKey());
System.out.print('\n');
System.out.print(heap[2].getKey());
System.out.print('\n');
System.out.print(heap[3].getKey());
System.out.print('\n');
System.out.print(heap[4].getKey());
System.out.print('\n');
System.out.print(heap[5].getKey());*/
}
public void insert(int i, int e)
{
heap[i] = new Element(e,i);
this.bubbleUp(heap);
}
public int size() {return size;}
public boolean isEmpty() {return(size == 0);}
public int min(){return heap[0].getKey();}
public Element remove()
{
int i = size-1;
size--;
return heap[i];
}
public Element removeMin()
{
Element min = this.root();
if(size == 1)
this.remove();
else
{
this.replace(this.root(), this.remove());
this.bubbleDown(this.root());
}
return min;
}
public Element replace(Element a, Element b)
{
a.setIndex(b.getIndex());
a.setKey(b.getKey());
return a;
}
public void bubbleUp(Element e)
{
Element f;
while(!e.isRoot(e.getIndex()))
{
f = this.getParent(e.getIndex());
if(comp.compare(f,e) <= 0)
break;
else
{
int temp = f.getIndex();
f.setIndex(e.getIndex());
e.setIndex(temp);
swap(f,e);
System.out.println("bubbling");
e=f;
}
}
}
public void bubbleDown(Element e)
{
int i = e.getIndex();
while(e.isInternal(i, size))
{
Element s;
if(!e.hasRight(i, size))
s = this.getLeft(i);
else if(comp.compare(this.getLeft(i), this.getRight(i)) <= 0)
s = this.getLeft(i);
else
s = this.getRight(i);
if(comp.compare(s,e) < 0)
{
swap(e,s);
e = s;
}
else
break;
}
}
public void swap(Element x, Element y)
{
int temp = x.getIndex();
x.setIndex(y.getIndex());
y.setIndex(temp);
}
public Element root() {return heap[0];}
public Element getLeft(int i) {return heap[i*2];}
public Element getRight(int i) {return heap[i*2+1];}
public Element getParent(int i) {return heap[i/2];}
}
class Element
{
private int key;
private int index;
public Element(int k, int i)
{
key = k;
index = i;
}
public int getKey() {return key;}
public void setKey(int k) {key = k;}
public int getIndex() {return index;}
public void setIndex(int i) {index = i;}
public boolean isRoot(int i) {
if (i == 0)
return true;
else
return false;
//return i == 1;
}
public boolean hasLeft(int i, int size) {return 2*i <= size;}
public boolean hasRight(int i, int size) {return 2*i+1 <= size;}
public boolean isInternal(int i, int size) {return hasLeft(i, size);}
public boolean isExternal(int i, int size) {return !isInternal(i, size);}
}
class Compare implements Comparator<Element>
{
public Compare(){}
public int compare(Element a, Element b)
{
int x=0;
if(a.getKey() < b.getKey())
x = -1;
else if(a.getKey() == b.getKey())
x = 0;
else if(a.getKey() > b.getKey())
x = 1;
return x;
}
}