MaxHeap

• The goal of this project is to implement Max-Heap data structures idea using the Java programing language.

How to complier and run the code

• 1.Download the java source file, which named "MaxHeapTester.java", to your desktop directory.

• 2.Go to the command line. (For Windows user, please press Win+R keys and type "cmd" then press enter key. For MacOs user, please press command+space keys and type "terminal" and press enter key).

• 3.Type "cd desktop" in command line.

• 4.Type "javac MaxHeapTester.java" in command line.

• 5.Type "java MaxHeapTester" in command line.

implementation

• In order to easily implement the Max-Heap data structure idea, we can use a ArrayList to repersent the Max-Heap and we ingore the first element in the ArrayList on purpose.(Note: We can not just simply skip the first position of ArrayList and directly insert the items in sceond position of the ArrayList, but we can insert a garbage data to occupy the first position of the ArrayList. Then, we just take care of those data, which locate from the second position of the list to the end of the list.)
• As you can see the picture in the below, it show how an ArrayList can be used to repersent a Max-Heap.

Explaination to function named "remove_the_biggest"

• when we want to remove the biggest number, we just remove the element at the top of the heap and move the last element at the heap to the top of the heap. Then, we perform reheapify process to guarantee the Max-Heap in a ideal structure.

Explaination to reheapify process

-After we remove th biggest numbe from the heap and move the last element at the heap to the top of the heap, we travel the Max-Heap from the top of the Heap to the bottom of the heap so that we can repeatedly compare the value of the each root element and the value it's left and right children until a ideal heap structure has been rebuild again.In addition, since we use the an ArrayList to repersent the Max-heap and we ignore the first element in the ArrayList, the index of left child equal it's parents's index multiple by 2 and the indx of th right child is equal to it's parents's index multiple by 2 and plus 1.

Following picture show the details of remove_the_biggest function

Test cases

• Insert 15,2,18,7,4,14,20,71,6 and 3 to an empty Max Heap.

Following pictures show the detail of Max-Heap after each element were inserted manually.

Following pictures show each steps of building Max-Heap by program.

Following picture show the step of removing first,second and third biggest element from the Max-Heap and process of reheapify after each biggest element was removed.

Credit

Hing Li