Skip to content

Instantly share code, notes, and snippets.

@kuzemkon
Created June 13, 2016 12:19
Show Gist options
  • Save kuzemkon/947a53c32c05ff4b9e463ead38de714e to your computer and use it in GitHub Desktop.
Save kuzemkon/947a53c32c05ff4b9e463ead38de714e to your computer and use it in GitHub Desktop.
Heap sorting and priority queue
public class Sort {
private int[] a;
private int n;
private int left;
private int right;
private int largest;
Sort(int[] array){
sort(array);
}
Sort(int[] array, boolean queue){
if(queue){
this.a = array;
buildheap(this.a);
} else {
sort(array);
}
}
private void buildheap(int []a){
n=a.length-1;
for(int i=n/2;i>=0;i--){
maxheap(a,i);
}
}
private void maxheap(int[] a, int i){
left=2*i+1;
right=2*i+2;
if(left <= n && a[left] > a[i]){
largest=left;
}
else{
largest=i;
}
if(right <= n && a[right] > a[largest]){
largest=right;
}
if(largest!=i){
swap(i,largest);
maxheap(a, largest);
}
}
private void sort(int []a0){
a=a0;
buildheap(a);
for(int i=n;i>0;i--){
swap(0, i);
n=n-1;
maxheap(a, 0);
}
}
public int[] getResult(){
return this.a;
}
public int heapMaximum(){
return this.a[0];
}
public void maxHeapInsert(int key){
increaseArray(1);
this.a[this.a.length-1]=-999;
heapIncraseKey(this.a.length-1,key);
}
private void increaseArray(int number){
int[] newArray = new int[this.a.length+number];
for (int i=0; i<this.a.length; i++){
newArray[i] = this.a[i];
}
this.a = newArray;
}
public void heapIncraseKey(int i,int key){
if(key<this.a[i]){
System.out.println("Error");
return;
}
this.a[i] = key;
buildheap(a);
}
private void swap(int first, int second){
int temp = this.a[first];
this.a[first] = this.a[second];
this.a[second] = temp;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment