Java Program to Implement Max Heap

This Java program is to implement max heap. A Heap data structure is a Tree based data structure that satisfies the HEAP Property “If A is a parent node of B then key(A) is ordered with respect to key(B) with the same ordering applying across the heap.”
So in a Min Heap this property will be “If A is a parent node of B then key(A) is less than key(B) with the same ordering applying across the heap.” and in a max heap the key(A) will be greater than Key(B).

Here is the source code of the Java program to implement max heap. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.

```
public class MaxHeap
```
```
{
```
```
    private int[] Heap;
```
```
    private int size;
```
```
    private int maxsize;
```
```
 
```
```
    private static final int FRONT = 1;
```
```
 
```
```
    public MaxHeap(int maxsize)
```
```
    {
```
```
        this.maxsize = maxsize;
```
```
        this.size = 0;
```

        Heap = new int[this.maxsize + 1];

```
        Heap[0] = Integer.MAX_VALUE;
```
```
    }
```
```
 
```
```
    private int parent(int pos)
```
```
    {
```
```
        return pos / 2;
```
```
    }
```
```
 
```
```
    private int leftChild(int pos)
```
```
    {
```
```
        return (2 * pos);
```
```
    }
```
```
 
```
```
    private int rightChild(int pos)
```
```
    {
```
```
        return (2 * pos) + 1;
```
```
    }
```
```
 
```
```
    private boolean isLeaf(int pos)
```
```
    {
```

        if (pos >=  (size / 2)  &&  pos <= size)

```
        {
```
```
            return true;
```
```
        }
```
```
        return false;
```
```
    }
```
```
 
```

    private void swap(int fpos,int spos)

```
    {
```
```
        int tmp;
```
```
        tmp = Heap[fpos];
```
```
        Heap[fpos] = Heap[spos];
```
```
        Heap[spos] = tmp;
```
```
    }
```
```
 
```
```
    private void maxHeapify(int pos)
```
```
    {
```
```
        if (!isLeaf(pos))
```
```
        { 
```

            if ( Heap[pos] < Heap[leftChild(pos)]  || Heap[pos] < Heap[rightChild(pos)])

```
            {
```

                if (Heap[leftChild(pos)] > Heap[rightChild(pos)])

```
                {
```

                    swap(pos, leftChild(pos));

                    maxHeapify(leftChild(pos));

```
                }else
```
```
                {
```

                    swap(pos, rightChild(pos));

                    maxHeapify(rightChild(pos));

```
                }
```
```
            }
```
```
        }
```
```
    }
```
```
 
```
```
    public void insert(int element)
```
```
    {
```
```
        Heap[++size] = element;
```
```
        int current = size;
```
```
 
```

        while(Heap[current] > Heap[parent(current)])

```
        {
```

            swap(current,parent(current));

```
            current = parent(current);
```
```
        }	
```
```
    }
```
```
 
```
```
    public void print()
```
```
    {
```

        for (int i = 1; i <= size / 2; i++ )

```
        {
```

            System.out.print(" PARENT : " + Heap[i] + " LEFT CHILD : " + Heap[2*i]

                  + " RIGHT CHILD :" + Heap[2 * i  + 1]);

```
            System.out.println();
```
```
        }
```
```
    }
```
```
 
```
```
    public void maxHeap()
```
```
    {
```

        for (int pos = (size / 2); pos >= 1; pos--)

```
        {
```
```
            maxHeapify(pos);
```
```
        }
```
```
    }
```
```
 
```
```
    public int remove()
```
```
    {
```
```
        int popped = Heap[FRONT];
```
```
        Heap[FRONT] = Heap[size--]; 
```
```
        maxHeapify(FRONT);
```
```
        return popped;
```
```
    }
```
```
 
```

    public static void main(String...arg)

```
    {
```

        System.out.println("The Max Heap is ");

        MaxHeap maxHeap = new MaxHeap(15);

```
        maxHeap.insert(5);
```
```
        maxHeap.insert(3);
```
```
        maxHeap.insert(17);
```
```
        maxHeap.insert(10);
```
```
        maxHeap.insert(84);
```
```
        maxHeap.insert(19);
```
```
        maxHeap.insert(6);
```
```
        maxHeap.insert(22);
```
```
        maxHeap.insert(9);
```
```
        maxHeap.maxHeap();
```
```
 
```
```
        maxHeap.print();
```

        System.out.println("The max val is " + maxHeap.remove());

```
    }
```
```
}
```

$javac MaxHeap.java
$java MaxHeap
The Max Heap is 
 PARENT : 84 LEFT CHILD : 22 RIGHT CHILD :19
 PARENT : 22 LEFT CHILD : 17 RIGHT CHILD :10
 PARENT : 19 LEFT CHILD : 5 RIGHT CHILD :6
 PARENT : 17 LEFT CHILD : 3 RIGHT CHILD :9
The max val is 84

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

If you wish to look at all Java Programming examples, go to Java Programs.

« Prev - Java Program to Implement CountMinSketch

» Next - Java Program to Implement Min Heap

Related Posts:

Check Data Structure Books
Apply for Computer Science Internship
Practice Computer Science MCQs
Practice Programming MCQs
Practice Design & Analysis of Algorithms MCQ

Recommended Articles: