Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import material.u03.IMaxHeap;
- import java.lang.reflect.Array;
- public class MaxHeap<T extends Comparable<T>> implements IMaxHeap<T> {
- private boolean init=true;
- private T[] array;
- private int capacity;
- public MaxHeap(int capacity){
- this.capacity=capacity+1;
- }
- @Override
- public int capacity() {
- if(init){
- return 0;
- }else
- return array.length-1;
- }
- @Override
- public T extractMax() {
- int n = size();
- if(size()<=(capacity()/4) && n>0){
- this.capacity=((capacity+1)/2);
- int elements = size();
- T[] smallarray = (T[]) Array.newInstance(array[1].getClass(), this.capacity);
- System.arraycopy(array, 1, smallarray, 1, elements);
- array = (T[]) Array.newInstance(smallarray[1].getClass(), this.capacity);
- System.arraycopy(smallarray, 1, array, 1, elements);
- }
- if(n>0){
- T a = array[1];
- array[1]=array[n];
- array[n]=null;
- n--;
- int i=1;
- T b = array[i];
- int j =2*i;
- while(j<=n){
- if((j<n)&&(array[j+1].compareTo(array[j])>0)){
- j++;
- }
- if(b.compareTo(array[j])<0){
- array[i]=array[j];
- i=j;
- j=2*i;
- }else{
- j=n+1;
- }
- }
- array[i]=b;
- return a;
- }else{
- System.out.println("Heap ist leer");
- return null;
- }
- }
- @Override
- public T insert(T t) {
- if(init){
- array = (T[]) Array.newInstance(t.getClass(), this.capacity);
- init=false;
- }
- int i = size()+1;
- if(i>capacity()){ //Array vergrößern falls voll
- this.capacity=(capacity*2)-1;
- int elements = size();
- T[] bigarray = (T[]) Array.newInstance(t.getClass(), this.capacity);
- System.arraycopy(array, 1, bigarray, 1, elements);
- array = (T[]) Array.newInstance(t.getClass(), this.capacity);
- System.arraycopy(bigarray, 1, array, 1, elements);
- }
- while(i>1 && (array[(int) Math.floor(i/2)].compareTo(t)<0)){
- array[i]=array[(int) Math.floor(i/2)];
- i=(int) Math.floor(i/2);
- }
- array[i]=t;
- return array[i];
- }
- @Override
- public boolean isEmpty() {
- if(init){
- return true;
- }else
- for(int i=1;i<array.length;i++){
- if(array[i]!=null){
- return false;
- }
- }
- return true;
- }
- @Override
- public T max() {
- if(init){
- return null;
- }else
- return array[1];
- }
- @Override
- public int size() {
- if(init){
- return 0;
- }else
- for(int i=1;i<array.length;i++){
- if(array[i]==null){
- return i-1;
- }
- }
- return array.length-1;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement