How to implement a binary heap in java ?

Binary heap in java

A binary heap is a complete binary tree which satisfies the heap ordering property.

There are two types of heap :

• Max heap : Every parent is greater than or equal to its children
• Min heap: every parent is less than or equal to its children

A binary heap must be a complete tree,children are added at each level from left to right,and usually implemented as arrays.The maximum or minimum value will always be at the root of the tree, this is the advantage of using a heap.

For Heapify,the process of converting a binary tree into a heap,is often has to be done after an insertion or deletion.

To implement the heaps as arrays:

• We put the root at array[0]
• Then we traverse each level from left to right,and so the left child of the root would go into array[1],its right child would be into array[2],etc.

For the node at array[i], we can get left child using this formula (2i + 1), for the right child we can use this one (2i + 2),and for parent item floor((i — 1) / 2).This works just with complete binary trees.

To insert into heap :

• Always add new items to the end of the array
• Then we have to fix the heap(heapify process)
• We compare the new item against its parent
• If the item is greater than its parent, we swap it with its parent
• We then rinse and repeat

Example of implementation in java :

public class Heap {

    private int[] heap;
    private int size;

    public Heap(int capacity) {
        heap = new int[capacity];
    }

    public void insert(int value) {
        if (isFull()) throw new IndexOutOfBoundsException("Heap is full");

        heap[size] = value;

        fixHeapAbove(size);
        size++;
    }

    private void fixHeapAbove(int index) {
        int newValue = heap[index];

        while (index > 0 && newValue > heap[getParent(index)]) {
            heap[index] = heap[getParent(index)];
            index = getParent(index);
        }

        heap[index] = newValue;
    }

    public boolean isFull() {
        return heap.length == size;
    }

    public int getParent(int index) {
        return (index - 1) / 2;
    }
}

As a conclusion,in java JDK we have PriorityQueue, an unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a comparator provided at queue construction time, depending on which constructor is used.

As a bonus from this article, I want to share with you some books,that changed my life in the domain of software engineering:

1- Clean Code: A Handbook of Agile Software Craftsmanship

2- Clean Architecture: A Craftsman’s Guide to Software Structure and Design (Robert C. Martin Series)

3-The Pragmatic Programmer: your journey to mastery, 20th Anniversary Edition

Thanks for Reading !

If you like my work and like to support me …

• Follow me on twitter here
• Follow me on facebook here
• Subscribe on my Youtube channel,I share lots of amazing content like this but in video
• Check out my blog website selcote.com