Java Heap Tutorial
Welcome to my Java Heap Tutorial. In previous tutorials, I covered how to print out trees in Java. You may want to look at that before continuing here, but it isn’t required.
A Heap is kind of like a tree, but it is normally implemented as an array. There are 2 main rules for using a heap. 1. Every row is complete except for last row. 2. Parent keys are bigger then children. I will cover how to insert and remove items. I’ll show how an array is heaped. I’ll also cover how the Heap Sort works. Everything is covered in the video and code below.
If you like videos like this, it helps to tell Google+ with a click here [googleplusone]
Code From the Video
Java Heap Tutorial : Heap2.java
import java.util.Arrays;
public class Heap2 {
private Data3[] theHeap;
private int itemsInArray = 0;
private int maxSize;
public Heap2(int maxSize) {
this.maxSize = maxSize;
theHeap = new Data3[maxSize];
}
public void insert(int index, Data3 newData) {
theHeap[index] = newData;
}
public void incrementTheArray() {
itemsInArray++;
}
public Data3 pop() {
// if (itemsInArray != 0) {
int tempItemsInArray = itemsInArray - 1;
// Used to show how data is moved during sorting
System.out.println("Store " + theHeap[0] + " in root. Store "
+ theHeap[tempItemsInArray] + " in index 0");
System.out.println(Arrays.toString(theHeap) + "\n");
Data3 root = theHeap[0];
theHeap[0] = theHeap[--itemsInArray];
// Send to the array heap method starting with index 0
heapTheArray(0);
return root;
// }
// return null;
}
public void printTree2(int rows) {
// Number of spaces between items in tree
int spaces = 0;
int iteration = 1;
// Generate all of the indents that are
// needed depending on the number of rows
// to print
int[] indent = getIndentArray(rows);
while (iteration <= rows) {
// Find first Index : .5 * (-2 + 2^n)
int indexToPrint = (int) (.5 * (-2 + (Math.pow(2, iteration))));
// Number of Items per Row : 2^(n - 1)
int itemsPerRow = (int) (Math.pow(2, iteration - 1));
int maxIndexToPrint = indexToPrint + itemsPerRow;
// Print the indents needed
for (int j = 0; j < indent[iteration - 1]; j++)
System.out.print(" ");
// Print all of the index values for each row
// indexToPrint represents the first index in the
// row, while maxIndexToPrint equals the last
for (int l = indexToPrint; l < maxIndexToPrint; l++) {
// If the array isn't full don't try to print
// indexes that don't exist
if (l < itemsInArray) {
System.out.print(String.format("%02d", theHeap[l].key));
for (int k = 0; k < spaces; k++)
System.out.print(" ");
}
}
// In a tree the spaces get bigger in the
// same way that indents get smaller
spaces = indent[iteration - 1];
iteration++;
System.out.println();
}
}
// Calculate each indent per row for the tree
// then reverse their order to go from biggest
// to smallest
public int[] getIndentArray(int rows) {
int[] indentArray = new int[rows];
for (int i = 0; i < rows; i++) {
indentArray[i] = (int) Math.abs((-2 + (Math.pow(2, i + 1))));
}
Arrays.sort(indentArray);
indentArray = reverseArray(indentArray);
return indentArray;
}
// Reverse the indent values in the array
// so that they go from biggest to smallest
public int[] reverseArray(int[] theArray) {
// Index of the first element
int leftIndex = 0;
// Index of last element
int rightIndex = theArray.length - 1;
while (leftIndex < rightIndex) {
// Exchange the left and right elements
int temp = theArray[leftIndex];
theArray[leftIndex] = theArray[rightIndex];
theArray[rightIndex] = temp;
// Move the indexes to check towards the middle
leftIndex++;
rightIndex--;
}
return theArray;
}
// Fill the heap with random numbers based on
// the number that is passed in
public void generateFilledArray(int randNum) {
Data3 randomData1;
for (int i = 0; i < this.maxSize; i++) {
randomData1 = new Data3((int) (Math.random() * randNum) + 1);
this.insert(i, randomData1);
// Need to do this in a separate function because
// later when I sort the array I need to use insert
// without incrementing the array
incrementTheArray();
}
}
public void heapTheArray(int index) {
int largestChild;
Data3 root = theHeap[index];
while (index < itemsInArray / 2) {
// Get the index for the leftChild
int leftChild = 2 * index + 1;
// Get the index for the rightChild
int rightChild = leftChild + 1;
// If leftChild is less then rightChild
// save rightChild in largestChild
if (rightChild < itemsInArray
&& theHeap[leftChild].key < theHeap[rightChild].key) {
System.out.println("Put Value " + theHeap[rightChild]
+ " in largestChild");
largestChild = rightChild;
} else {
System.out.println("Put Value " + theHeap[leftChild]
+ " in largestChild");
// Otherwise save leftChild in largestChild
largestChild = leftChild;
}
// If root is greater then the largestChild
// jump out of while
if (root.key >= theHeap[largestChild].key)
break;
System.out.println("Put Index Value " + theHeap[largestChild]
+ " in Index " + index);
// Save the value in largest child into the top
// index
theHeap[index] = theHeap[largestChild];
index = largestChild;
System.out.println();
printTree2(4);
System.out.println();
}
theHeap[index] = root;
}
// Cycle through the array and pop off each so
// the array goes from smallest to largest
public void heapSort() {
for (int k = maxSize - 1; k >= 0; k--) {
Data3 largestNode = pop();
insert(k, largestNode);
System.out.println(Arrays.toString(theHeap));
}
}
public static void main(String args[]) {
Heap2 newHeap = new Heap2(7);
newHeap.generateFilledArray(90);
// Print out the array before it is sorted
System.out.println("Original Array");
System.out.println(Arrays.toString(newHeap.theHeap));
System.out.println();
newHeap.printTree2(4);
System.out.println();
for (int j = newHeap.maxSize / 2 - 1; j >= 0; j--) {
newHeap.heapTheArray(j);
}
System.out.println("Heaped Array");
System.out.println(Arrays.toString(newHeap.theHeap) + "\n");
newHeap.printTree2(4);
System.out.println("HEAPED SORTED");
newHeap.heapSort();
// Print the sorted array
System.out.println("\nSorted Array");
System.out.println(Arrays.toString(newHeap.theHeap));
}
}
class Data3 {
public int key;
public Data3(int key) {
this.key = key;
}
public String toString() {
return Integer.toString(key);
}
}
Hello, There is any implementation of the heap or tree, or hash?
best,
x
Hello, I have all of my algorithm tutorials here Java Algorithms Tutorial. I plan on coming back and covering advanced algorithms soon.
hey derek,
when are you gonna start with the advanced tutorials?
I’m not certain. I’m being asked for a bunch of different tutorials. normally when that happens I hold a vote.
Hello Derek,
I have a question that when Heap Sort should be applied on or Where we should use it?
Hello Abhishek, Many things can effect the speed of sorting : whether data tends to be partially sorted, the amount of data, whether data tends to be reverse sorted, etc. It is always best to pick your sorting algorithm based on the data. You may also find that it would help to test data dynamically and switch to different sorting algorithms.
Thanks! Any particular reason why heaps are implemented using arrays?
Mainly because this is a pretty well structured heap. Pointers would allow you to grow the structure dynamically and flexibly however which would be a plus for many reasons