skip to main | skip to sidebar

Java Programs and Examples with Output

Pages

  • Home
 
  • RSS
  • Twitter
Wednesday, August 13, 2014

Java program to create a Binary Heap and Perform various operation

Posted by Happy Coder at 3:27 PM – 0 comments
 
A binary heap (min-heap) is a complete binary tree with elements from a partially ordered set, such that the element at every node is less than (or equal to) the the element at it's left and right child.

This Binary Heap is a min-heap implemented with one-based array (root is element 1; children of element n are elements 2n and 2n+1) for simplicity.

Complexity: Space O(n), findMin O(1), insert O(logn), deleteMin O(logn), buildHeap O(n);

class BinaryHeap {

 private int nodes[];
 private int size;
 private int capacity;
 

 public BinaryHeap(int capacity) {
  this.size = 0;
  this.capacity = capacity;
  this.nodes = new int[capacity + 1];
 }

 public int size() {
  return size;
 }

 public int findMin() {
  if (size <= 0) {
   throw new RuntimeException("Empty Heap is empty.");
  }
  return nodes[1];
 }

 public void insert(int e) {
  if (size >= capacity) {
   throw new RuntimeException("Heap overflow.");
  }

  size++;
  nodes[size] = e;
  percolateUp();
 }

 public int deleteMin() {
  if (size <= 0) {
   throw new RuntimeException("Empty Heap is empty.");
  }
  int min = findMin();
  nodes[1] = nodes[size];
  size--;
  percolateDown();
  return min;
 }

 private void percolateDown() {
  int index = 1;
  while (true) {
   int child = index * 2;
   if (child > size)
    break;
   if (child + 1 <= size) {
    // if there are two children -> take the smallest or
    // if they are equal take the left one
    child = findMin(child, child + 1);
   }
   if (nodes[index] <= nodes[child])
    break;
   swap(index, child);
   index = child;
  }
 }

 private void percolateUp() {
  int index = size();
  while (index > 1) {
   int parent = index / 2;
   if (nodes[index] >= nodes[parent])
    break;
   swap(index, parent);
   index = parent;
  }
 }

 private void swap(int i, int j) {
  int temp = nodes[i];
  nodes[i] = nodes[j];
  nodes[j] = temp;
 }

 private int findMin(int leftChild, int rightChild) {
  if (nodes[leftChild] <= nodes[rightChild]) {
   return leftChild;
  } else {
   return rightChild;
  }
 }
 
 public static void main(String[] args) {
  BinaryHeap bh = new BinaryHeap(10);
  bh.insert(7);
  bh.insert(5);
  bh.insert(9);
  bh.insert(6);
  bh.insert(4);
  bh.insert(8);
  bh.insert(10);
  bh.insert(1);
  bh.insert(3);
  bh.insert(2);
  
  System.out.println("Size of Binary Heap is : " + bh.size());

  System.out.println("Delete min from Binary Heap : " + bh.deleteMin());
  System.out.println("Size of Binary Heap is : " + bh.size());

  System.out.println("Delete min from Binary Heap : " + bh.deleteMin());
  System.out.println("Size of Binary Heap is : " + bh.size());
 }
 
}

Output of this Program
Size of Binary Heap is : 10
Delete min from Binary Heap : 1
Size of Binary Heap is : 9
Delete min from Binary Heap : 2
Size of Binary Heap is : 8

Try this by Yourself : http://ideone.com/FnSiPv
Labels: Searching Example Email This BlogThis! Share to X Share to Facebook

Leave a Reply

Older Post
Subscribe to: Post Comments ( Atom )

List of Java Programs

  • Java Program to check Greater between the Two Number
  • Java Program to find that given number is Palindrome or not
  • Java Program to Demonstrate the Use of Pre and Post Operator
  • Java Program to Reverse the Given Number
  • Java Program to Print Number in the Given Data Type
  • Program to Demonstrate Skipping using Continue
  • Program to find whether entered character is a vowel or Consonant
  • Java Program to Calculate the Sum of Digits of Given Number
  • How to swap two numbers using only two variables
  • Checking the Given Number is Armstrong or Not
  • Average an Array of Values
  • Display ASCII Code Instead of Character
  • Comparison of Two Variable using If
  • Printing Table In java using While Loop
  • Generate Random Number Using Math.Random Function
  • To Find roots of Quadratic Equation
  • Performing Arithmetic Opration on Two Variable
  • Concatenation of Two String in Java
  • Command Line Argument in JAVA
  • Java Hello World Program
  • Calculate Circle Perimeter | Java Program
  • Calculate the Area of Circle | Java Program
  • To Find Whether Given Year is a Leap Year or not
  • Popular
  • Recent
  • Archives

Total Pageviews

Sparkline

Followers

Popular Posts of This Week

  • Java program to create a Binary Heap and Perform various operation
    A binary heap (min-heap) is a complete binary tree with elements from a partially ordered set, such that the element at every node is less ...
  • Sort an Integer array with Bucket Sort
    Here is a java program to Sort an Integer array with Bucket Sort class BucketSort { public int[] bucketSort(int[] array) { /...
  • Stack implemented as array - Data Structure
    // Stack implemented as array public class ArrayStack<T> { private T[] stack; private int numElements = 0; // points to s...
  • Merge-Sort Algorithm implementation in JAVA
    Merge-Sort Function void MergeSort(int low, int high) // a[low : high] is a global array to be sorted. // Small(P) is true if there...
  • Password Encryption Decryption using PBE With MD5 And DES algorithm in java
    In Some applications, at User registration time, we need to Encrypt the password field and then store into the database. After that ...
  • Java Class to Calculate the Volume of Box
    Here is a Java Class to Calculate the Volume of Box. class Box { double width; double height; double depth; // This is the con...
  • Implementation of a basic generic tree, with labels of type T - Data Structure
    // This implements a basic generic tree, with labels of type T, // pointer to the parent node, and a singly linked list of children nodes...
  • Compute distance light travels using long variables
    Here is a Java Program to Compute distance light travels using long variables class Light { public static void main(String args[]) { ...
  • To Sort an Interger Array using Shell Sort
    To Sort an Interger Array using Shell Sort class ShellSort { public static int[] shellSort(int[] array) { int N = array.length; ...
  • Word Wrap
    Word Wrap has been implemented in Java. The program can be used to wrap text into lines of N characters each and take care of word wrap whi...
Powered by Blogger.

Archives

  • ▼  2014 ( 4 )
    • ▼  August ( 4 )
      • Java program to create a Binary Heap and Perform v...
      • Create an Adjacency matrix Graph and perform Add a...
      • To Sort an Interger Array using Shell Sort
      • Sort an Integer array with Bucket Sort
  • ►  2013 ( 6 )
    • ►  August ( 1 )
    • ►  April ( 5 )
  • ►  2012 ( 673 )
    • ►  November ( 9 )
    • ►  October ( 223 )
    • ►  September ( 272 )
    • ►  August ( 2 )
    • ►  June ( 1 )
    • ►  February ( 67 )
    • ►  January ( 99 )
 

Our Blogs

  • Linux Tutorial
  • C Programming Tutorial

Labels

  • Agile Methodology ( 1 )
  • Algorithm ( 3 )
  • AntiSamy ( 1 )
  • Arithmetic Operation ( 1 )
  • Array Example ( 9 )
  • ArrayList Examples ( 11 )
  • Average an Array of Values ( 1 )
  • Barcode Example ( 1 )
  • Basic Java Programs ( 34 )
  • Bing API Example ( 2 )
  • BitSet Example ( 1 )
  • Boolean Example ( 1 )
  • Bouncy Castle API ( 1 )
  • Break Statement ( 2 )
  • BufferedReader Example ( 2 )
  • Calendar Example ( 1 )
  • Chart Generation Example ( 1 )
  • Command Line Argument ( 1 )
  • Comparator Example ( 1 )
  • Concatenation of String ( 1 )
  • Continue Statement ( 1 )
  • Control Structure ( 1 )
  • Copy File Example ( 1 )
  • CRC Example ( 1 )
  • CSV Example ( 6 )
  • Data Structure ( 5 )
  • Date Example ( 2 )
  • Directory Example ( 1 )
  • Do - While Loop Example ( 1 )
  • Domino Database ( 1 )
  • Email Example ( 8 )
  • Encryption Example ( 3 )
  • Excel Example ( 15 )
  • Factorial Example ( 1 )
  • File Upload Example ( 1 )
  • Find Roots of Quadratic Equation ( 1 )
  • FTP Example ( 2 )
  • Graph Examples ( 1 )
  • Greater between Two Numbers ( 1 )
  • GSON Library ( 1 )
  • HashMap Example ( 1 )
  • HashSet Example ( 1 )
  • Hello World Program ( 1 )
  • If Condition ( 2 )
  • Inner Class Example ( 1 )
  • iText Example ( 3 )
  • JAR File ( 1 )
  • JAVA Applet ( 1 )
  • Java Applications ( 1 )
  • Java AWT Example ( 9 )
  • Java Certification ( 1 )
  • Java Class Examples ( 15 )
  • Java Collection Example ( 1 )
  • Java Command Example ( 4 )
  • Java Constructor Examples ( 1 )
  • Java Currency Example ( 1 )
  • Java Database Example ( 3 )
  • Java Date and Time Example ( 3 )
  • Java DateFormat Example ( 3 )
  • Java Examples ( 2 )
  • Java Exception Example ( 5 )
  • Java File Example ( 22 )
  • Java GUI Example ( 1 )
  • Java Image Examle ( 3 )
  • Java Inheritance Example ( 3 )
  • Java Input Output Example ( 1 )
  • Java IO Example ( 3 )
  • Java Jar Example ( 1 )
  • Java JSON Example ( 3 )
  • Java Mail Examples ( 4 )
  • Java Map Example ( 5 )
  • Java MapReduce Example ( 2 )
  • Java MultiThreading Example ( 7 )
  • Java Network Example ( 9 )
  • Java Package ( 1 )
  • Java Programs ( 1 )
  • Java RMI ( 1 )
  • Java Robot Class Examples ( 2 )
  • Java Runtime Example ( 1 )
  • Java Swing Example ( 9 )
  • Java Util Example ( 1 )
  • Java Vector Example ( 4 )
  • Java Voice Example ( 1 )
  • Java Webservice Example ( 1 )
  • Java XML Example ( 3 )
  • Java Zip Class Examples ( 2 )
  • JDBC ( 9 )
  • JDK Version Comparison ( 1 )
  • JFrame Example ( 3 )
  • JOptionPane Dialog Example ( 1 )
  • JPanel Example ( 1 )
  • JSP Example ( 2 )
  • JSTL Example ( 1 )
  • jUnit Example ( 2 )
  • LinkedList Example ( 2 )
  • List Example ( 1 )
  • Long Variable ( 1 )
  • Lottery Nubmer ( 1 )
  • MD5 Hashing Example ( 3 )
  • Memory Management Example ( 1 )
  • Method Override ( 1 )
  • MIDI Sound ( 8 )
  • Module Operator Example ( 2 )
  • Multiplication Table ( 1 )
  • Observer Interface Example ( 1 )
  • Operator Example ( 5 )
  • Pagination ( 1 )
  • Palindrome Number ( 1 )
  • Pass By Reference Example ( 1 )
  • Pass By Value Example ( 1 )
  • PDF File Example ( 3 )
  • PDF Generation Example ( 4 )
  • Pre and Post Operator ( 2 )
  • Prime Number ( 3 )
  • Progress Bar Example ( 1 )
  • Property List Example ( 2 )
  • Random Function ( 7 )
  • Recursion Example ( 2 )
  • Regex Example ( 2 )
  • Remote Host Example ( 2 )
  • Robot Class ( 4 )
  • Searching Example ( 3 )
  • Slideshow ( 1 )
  • Sorting Example ( 7 )
  • SpringLayout Example ( 1 )
  • Stack Example ( 4 )
  • Static Variable ( 1 )
  • StreamTokenizer Example ( 2 )
  • String Example ( 19 )
  • Struts2 Example ( 1 )
  • Sum of Digits ( 1 )
  • Swap Two Numbers ( 1 )
  • Switch Case ( 3 )
  • Tapestry Components ( 1 )
  • Thumbnail Example ( 2 )
  • TimerTask Example ( 2 )
  • To Calculate Volume ( 1 )
  • To Check Armstrong Number ( 1 )
  • Tree Example ( 1 )
  • TreeMap Example ( 1 )
  • TreeSet Example ( 1 )
  • Two Dimensional Array Example ( 1 )
  • UUID ( 1 )
  • Validation Example ( 2 )
  • Variable Casting ( 1 )
  • While Loop ( 1 )
  • XML Parsing ( 7 )
  • XSS Attacks ( 1 )
  • Zip File ( 15 )

Popular Posts

  • Java Class to Calculate the Volume of Box
    Here is a Java Class to Calculate the Volume of Box. class Box { double width; double height; double depth; // This is the con...
  • Java class that defines an integer stack that can hold 10 values
    Here is a Java class that defines an integer stack that can hold 10 values. class Stack { int stck[] = new int[10]; int tos; // ...
  • Validating Password and Confirm Password in JSF
    <html xmlns:f="http://java.sun.com/jsf/core" xmlns:h="http://java.sun.com/jsf/html" xmlns="http://www.w3.org...
  • Java program to create a Binary Heap and Perform various operation
    A binary heap (min-heap) is a complete binary tree with elements from a partially ordered set, such that the element at every node is less ...
  • Compute distance light travels using long variables
    Here is a Java Program to Compute distance light travels using long variables class Light { public static void main(String args[]) { ...
  • Stack implemented as array - Data Structure
    // Stack implemented as array public class ArrayStack<T> { private T[] stack; private int numElements = 0; // points to s...
  • To Sort an Interger Array using Shell Sort
    To Sort an Interger Array using Shell Sort class ShellSort { public static int[] shellSort(int[] array) { int N = array.length; ...
  • Create an Adjacency matrix Graph and perform Add and Remove operation
    import java.util.ArrayList; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; import...
  • Java Program to Generate the Lottery Number between 1 to 49
     A lottery requires that you select six different numbers from the integers 1 to 49. Write a program to do this for you and generate five s...
  • Merge-Sort Algorithm implementation in JAVA
    Merge-Sort Function void MergeSort(int low, int high) // a[low : high] is a global array to be sorted. // Small(P) is true if there...
 
 
© 2011 Java Programs and Examples with Output | Designs by Web2feel & Fab Themes

Bloggerized by DheTemplate.com - Main Blogger