Last active
November 24, 2017 18:33
-
-
Save anil477/853664ca69b89068e3a3394be3feab84 to your computer and use it in GitHub Desktop.
Min Heap - Insert and Extract All Min Element
This file contains 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
// http://algorithms.tutorialhorizon.com/binary-min-max-heap/ | |
// the implementation uses 1 as the root and not 0. So the left, right and root will be - 2i, 2i+1, i/2 respectively. | |
class MinHeap { | |
public int size; | |
public int[] mH; | |
public int position; | |
public MinHeap(int size) | |
{ | |
this.size = size; | |
mH = new int[size + 1]; | |
position = 0; | |
} | |
public void createHeap(int[] arrA) { | |
if (arrA.length > 0) { | |
for (int i = 0; i < arrA.length; i++) { | |
insert(arrA[i]); | |
} | |
} | |
} | |
public void display() { | |
for (int i = 1; i < mH.length; i++) { | |
System.out.print(" " + mH[i]); | |
} | |
System.out.println(""); | |
} | |
public void insert(int x) { | |
// this root element is set as 1 and not 0. | |
// https://stackoverflow.com/questions/22900388/why-in-a-heap-implemented-by-array-the-index-0-is-left-unused/35460725#35460725 | |
if (position == 0) { | |
mH[position + 1] = x; | |
position = 2; | |
} else { | |
mH[position++] = x; | |
bubbleUp(); | |
} | |
} | |
public void bubbleUp() | |
{ | |
int pos = position - 1; | |
// We get the index of the last element. Then compare it with it's parent which is index/2 | |
// pos > 0 to check that position is still valid | |
// if the parent is larger than swap it | |
// next we set the pointer to the parent | |
// we keep bubbling up until the particular element is at correct position | |
while (pos > 0 && pos/2 > 0 && mH[pos / 2] > mH[pos]) { | |
int y = mH[pos]; | |
mH[pos] = mH[pos / 2]; | |
mH[pos / 2] = y; | |
pos = pos / 2; // set the new pointer to point to the parent | |
} | |
} | |
// minimum element is the first element. we will return that. | |
// next we place the last element to that first position and then start the bubbling down | |
public int extractMin() { | |
int min = mH[1]; | |
mH[1] = mH[position - 1]; | |
mH[position - 1] = 0; | |
position--; | |
sinkDown(1); | |
return min; | |
} | |
public void sinkDown(int k) { | |
int smallest = k; | |
// check if the index passed is greater than the left child. If yes we need to swap it with it | |
if (2 * k < position && mH[smallest] > mH[2 * k]) { | |
smallest = 2 * k; | |
} | |
// check if the index passed is greater than the right child. If yes we need to swap it with it | |
if (2 * k + 1 < position && mH[smallest] > mH[2 * k + 1]) { | |
smallest = 2 * k + 1; | |
} | |
// if the current node satisfies the heap property then no need to change anything. | |
// else swap and call bubble down with the new swapped node | |
if (smallest != k) { | |
swap(k, smallest); | |
sinkDown(smallest); | |
} | |
} | |
public void swap(int a, int b) { | |
int temp = mH[a]; | |
mH[a] = mH[b]; | |
mH[b] = temp; | |
} | |
public static void main(String args[]) { | |
int arrA[] = { 3, 2, 1, 7, 8, 4, 10, 16, 0 }; | |
System.out.println("Original Array : "); | |
for (int i = 0; i < arrA.length; i++) { | |
System.out.print(" " + arrA[i]); | |
} | |
MinHeap m = new MinHeap(arrA.length); | |
System.out.println("\nMin-Heap : "); | |
m.createHeap(arrA); | |
m.display(); | |
System.out.print("Extract Min :"); | |
for (int i = 0; i < arrA.length; i++) { | |
System.out.print(" " + m.extractMin()); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment