Created
June 13, 2016 12:19
-
-
Save kuzemkon/947a53c32c05ff4b9e463ead38de714e to your computer and use it in GitHub Desktop.
Heap sorting and priority queue
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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