How to implement a binary heap in java ?

Binary heap in java
  • Max heap : Every parent is greater than or equal to its children
  • Min heap: every parent is less than or equal to its children
  • 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.
  • 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
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;
}
}

Thanks for Reading !

--

--

--

I am a software engineer and entrepreneur. My focus is on Developing technical skills,Learning marketing,and taking care of the health.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

What Are Time Series Databases?

Firebase Cloud Messaging — PHP integration, push notifications

My experiences at Grace Hopper Conference, 2018

How much does it cost to build an app

Using Sidecar Mode for Kubernetes Log Collection

Introducing Code-Replay, and how we built it

MongooseIM 3.3.0: Supporting happy relations

What can we do with salesforce asynchronous apex?

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
El Akioui Zouhaire

El Akioui Zouhaire

I am a software engineer and entrepreneur. My focus is on Developing technical skills,Learning marketing,and taking care of the health.

More from Medium

Common Interview Question Part 1

Design a Parking Lot System

What Is JWM — java virtual machine.

SQL(RDBMS) vs No SQL(non RDBMS): How do I decide