Skip to content

Instantly share code, notes, and snippets.

@rishi93
Created December 15, 2017 15:34
Show Gist options
  • Select an option

  • Save rishi93/89ab444d99c302ad42ed9004710dacc8 to your computer and use it in GitHub Desktop.

Select an option

Save rishi93/89ab444d99c302ad42ed9004710dacc8 to your computer and use it in GitHub Desktop.
Heap sort (Implementation in Java)
class MinHeap{
int[] heap_array;
int heap_size;
int capacity = 100;
MinHeap(){
heap_array = new int[capacity];
heap_size = 0;
}
int parent(int i){
return (i-1)/2;
}
int left(int i){
return (2*i + 1);
}
int right(int i){
return (2*i + 2);
}
public void insertKey(int k){
if(heap_size == capacity){
System.out.println("Overflow");
return;
}
heap_size += 1;
int i = heap_size - 1;
heap_array[i] = k;
while(i > 0 && heap_array[parent(i)] > heap_array[i]){
int temp = heap_array[parent(i)];
heap_array[parent(i)] = heap_array[i];
heap_array[i] = temp;
i = parent(i);
}
}
public void minHeapify(int i){
int smallest = i;
int l = left(i);
int r = right(i);
if(l < heap_size && heap_array[l] < heap_array[smallest]){
smallest = l;
}
if(r < heap_size && heap_array[r] < heap_array[smallest]){
smallest = r;
}
if(smallest != i){
int temp = heap_array[i];
heap_array[i] = heap_array[smallest];
heap_array[smallest] = temp;
minHeapify(smallest);
}
}
public int extractMin(){
if(heap_size == 0){
System.out.println("No elements");
return -1;
}
if(heap_size == 1){
heap_size -= 1;
return heap_array[0];
}
int root = heap_array[0];
heap_array[0] = heap_array[heap_size - 1];
heap_size -= 1;
minHeapify(0);
return root;
}
public void printTree(){
for(int i = 0; i < heap_size; i++){
System.out.print(heap_array[i] + " ");
}
System.out.println();
}
public boolean isEmpty(){
if(heap_size == 0){
return true;
}
else{
return false;
}
}
}
public class Test{
public static void main(String[] args){
MinHeap ob = new MinHeap();
ob.insertKey(5);
ob.insertKey(2);
ob.insertKey(3);
ob.insertKey(4);
ob.insertKey(1);
while(!ob.isEmpty()){
System.out.print(ob.extractMin() + " ");
}
System.out.println();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment