SORTING - Introduction to Java Programming: Comprehensive Version - page 878

Heap<E extends Comparable<E>>

-list: java.util.ArrayList<E>

+Heap()
+Heap(objects: E[])

Creates a default empty heap.
Creates a heap with the specified objects.

+add(newObject: E): void Adds a new object to the heap.

+remove(): E

Removes the root from the heap and returns it.

+getSize(): int

Returns the size of the heap.

F IGURE 23.16

The Heap class provides operations for manipulating a heap.

L ISTING 23.9

Heap.java
1 public class Heap<E extends Comparable<E>> {
2 private java.util.ArrayList<E> list = new java.util.ArrayList<>(); internal heap representation

3
4 /** Create a default heap */
5 public Heap() {
6 }
7
8 /** Create a heap from an array of objects */
9 public Heap(E[] objects) {
10 for ( int i = 0 ; i < objects.length; i++)
11 add(objects[i]);
12 }
13
14 /** Add a new object into the heap */
15 public void add(E newObject) {
16 list.add(newObject); // Append to the heap
17

no-arg constructor

constructor

add a new object
append the object

int currentIndex = list.size() - 1 ; // The index of the last node

18
19 while (currentIndex > 0 ) {
20 int parentIndex = (currentIndex - 1 ) / 2 ;
21 // Swap if the current object is greater than its parent
22 if (list.get(currentIndex).compareTo(
23 list.get(parentIndex)) > 0 ) {
24 E temp = list.get(currentIndex);
25 list.set(currentIndex, list.get(parentIndex));
26 list.set(parentIndex, temp);
27 }
28

swap with parent

else

29 break ; // The tree is a heap now heap now

30
31 currentIndex = parentIndex;
32 }
33 }
34
35 /** Remove the root from the heap */

36 public E remove() {

remove the root
empty heap 37 if (list.size() == 0 ) return null ;

38
39 E removedObject = list.get( 0 );
40 list.set( 0 , list.get(list.size() - 1 ));
41 list.remove(list.size() - 1 );
42
43

root
new root
remove the last

int currentIndex = 0 ;

44 while (currentIndex < list.size()) { adjust the tree