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

An open letter to developers… 30daysofJavaScript ==> Day 24

Re-Thinking Web APIs to be Dynamic and Run-Time Adaptable

ExpressJS middleware

Open Street Map — Add Multiple Open Street Map in Primeng Carousel in Angular Project

A Brief Introduction for Web Scrapping with Puppeteer

Converting datatypes JavaScript..30daysofjavascript ==>Day10

Blog 308

Shared Preferences

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

Leetcode 520. Detect Capital

Cassandra DB — What you should know!

Sample code for IBM Event Streams Coding Challenge

Apache Kafka 101