Min Heap | Min Heap In Java
In a Min Heap, the data of the root node must be less than or equal to its
children nodes data and this property holds for all the nodes of the min
binary heap.
children nodes data and this property holds for all the nodes of the min
binary heap.
In the case of Min Heap, the root node will have the smallest
smallest compared to all other nodes.
Min Heap implementation
Given a complete binary tree convert the complete binary tree into a
min-heap.
min-heap.
For a given node, heapify the left subtree, similarly, heapify the right subtree and after that if necessary bubble down
the current node such that the tree rooted with the current node satisfies
min heap property.
min heap property.
Implementation of Min Heap using a complete binary tree:
First, traverse through each node of a complete binary tree in pre-order
fashion and while traversing compare the data in the left child of the node
with data of the node and if data in the left child is less than the data in the
parent node then swap the data and again call the recursive function with
left subtree, if the data in right child is less than data in the parent node
swap the data and again call the recursive function with the right subtree.
fashion and while traversing compare the data in the left child of the node
with data of the node and if data in the left child is less than the data in the
parent node then swap the data and again call the recursive function with
left subtree, if the data in right child is less than data in the parent node
swap the data and again call the recursive function with the right subtree.
Min Heap Implementation
package minmax;
import java.util.*;
public class MinHeap {
static int [] MINHEAP;
static int last = 1;
static Vector<Integer> sortedList = new Vector<>();
static int getParent(int index)
{
return (index/2);
}
static int getLeftChild(int index)
{
return (index*2);
}
static int getRightChild(int index)
{
return (index*2+1);
}
static void heapify()
{
for(int i=last-1;i>0;i--)
{
if(MINHEAP[i] < MINHEAP[getParent(i)])
{
int t = MINHEAP[i];
MINHEAP[i] = MINHEAP[getParent(i)];
MINHEAP[getParent(i)] = t;
}
}
}
static void heapifyDel()
{
int currentIndex = 1;
int left = MINHEAP[getLeftChild(1)];
int right = MINHEAP[getRightChild(1)];
while((MINHEAP[currentIndex]>left ||
MINHEAP[currentIndex]>right && getRightChild(currentIndex) != last)
MINHEAP[currentIndex]>right && getRightChild(currentIndex) != last)
&& getLeftChild(currentIndex)<last)
{
if(left<right || right == 0)
{
int l = getLeftChild(currentIndex);
int t = MINHEAP[currentIndex];
MINHEAP[currentIndex] = MINHEAP[l];
MINHEAP[l] = t;
currentIndex = l;
left = MINHEAP[getLeftChild(l)];
right = MINHEAP[getRightChild(l)];
}
else
{
int r = getRightChild(currentIndex);
int t = MINHEAP[currentIndex];
MINHEAP[currentIndex] = MINHEAP[r];
MINHEAP[r] = t;
currentIndex = r;
left = MINHEAP[getLeftChild(r)];
right = MINHEAP[getRightChild(r)];
}
}
}
static void insert(int element)
{
MINHEAP[last] = element;
last++;
heapify();
}
static void display()
{
int n = (int) Math.floor(Math.log(last-1)/Math.log(2)) + 1 ;
for(int i=1;i<=n;i++)
{
for(int j=n-i;j>0;j--)
{
System.out.print(" ");
}
for(int j=(int)Math.pow(2,i-1);j<Math.pow(2,i) && j<last;j++)
{
System.out.print(MINHEAP[j] + " ");
}
System.out.println();
}
}
static void delete()
{
if(last == 1)
{
MINHEAP[last] = 0;
}
else
{
sortedList.add(MINHEAP[1]);
MINHEAP[1] = MINHEAP[last-1];
MINHEAP[last-1] = 0;
last--;
}
heapifyDel();
}
public static void main(String[] args) {
MINHEAP = new int[50];
Scanner sc = new Scanner(System.in);
int c;
do
{
System.out.println("1:Insert\n2:Delete\n3:Exit");
c = sc.nextInt();
switch(c)
{
case 1:
System.out.print("Enter the element : ");
int elem = sc.nextInt();
insert(elem);
display(); break;
case 2:
System.out.println("Sorting Elements");
int n = last;
for(int i=1;i<n;i++)
delete();
for(Integer a : sortedList)
System.out.print(a + " ");
System.out.println();
break;
}
}while(c!=3);
}
}
OUTPUT
OUTPUT
1:Insert
2:Delete
3:Exit
1
Enter the element: 42
42
1:Insert
2:Delete
3:Exit
1
Enter the element: 30
30
42
1:Insert
2:Delete
3:Exit
1
Enter the element: 50
30
42 50
1:Insert
2:Delete
3:Exit
1
Enter the element: 60
30
42 50
60
1:Insert
2:Delete
3:Exit
1
Enter the element: 6
6
30 50
60 42
1:Insert
2:Delete
3:Exit
1
Enter the element : 38
6
30 38
60 42 50
1:Insert
2:Delete
3:Exit
1
Enter the element : 12
6
30 12
60 42 50 38
1:Insert
2:Delete
3:Exit
2
Sorting Elements
6 12 30 38 42 50 60
1:Insert
2:Delete
3:Exit
3
tags: min heap, min heap implementation, data structures,
min-max heap, min-heap max-heap.
You must be also searching for these programming languages :
min-max heap, min-heap max-heap.
ReplyDeleteAccounts receivable financing gets your outstanding invoices paid - fast! The term financing receivables is used to describe an arrangement whereby a business uses its receivables to gain immediate access to cash.