22.11. Key Terms | Introduction to Java Programming-Comprehensive Version (6th Edition)

[Page 683 ( continued )]

20.5. Heaps

Heaps are a useful data structure for designing efficient sorting algorithms and priority queues. A heap is a binary tree with the following properties:

It is a complete binary tree.
Each node is greater than or equal to any of its children.

A binary tree is complete if every level of the tree is full, except that the last level may not be full and all the leaves on the last level are placed left-most. For example, in Figure 20.23, the binary trees in (a) and (b) are complete, but the binary trees in (c) and (d) are not complete. Further, the binary tree in (a) is a heap, but the binary tree in (b) is not a heap, because the root (39) is less than its right child (42).

Figure 20.23. A heap is a special complete binary tree.

[Page 684]

20.5.1. Representing a Heap

A heap is a binary tree, so it can be represented using a binary tree data structure. However, a more efficient representation for a heap is using an array or an array list if the heap size is known in advance. The heap in Figure 20.24(a) can be represented using an array in Figure 20.24(b). The root is at position 0, and its two children are at positions 1 and 2. For a node at position i , its left child is at position 2 i + 1, its right child is at position 2 i + 2, and its parent is ( i - 1)/2. For example, the node for element 39 is at position 4, so its left child (element 14) is at 9 (2 x 4 + 1), its right child (element 33) is at 10 (2 x 4 + 2), and its parent (element 42) is at 1 ((4 -1)/2.

Figure 20.24. A binary heap can be implemented using an array.

If the heap size is not known in advance, it is better to use an array list to store a heap.

20.5.2. Removing the Root

Often you need to remove the root from a heap. After the root is removed, the tree must be rebuilt to maintain the heap property. The algorithm for building the tree can be described as follows :

 Move the last node to replace the root; Let the root be the current node;  while  (the current node has children and the current node is smaller than one of its children) { Swap the current node with the larger of its children; Now the current node is one level down; }

Figure 20.25 shows the process of rebuilding a heap after the root 62 is removed from Figure 20.24(a). Move the last node 9 to the root, as shown in Figure 20.25(a). Swap 9 with 59 as shown in Figure 20.25(b). Swap 9 with 44 as shown in Figure 20.25(c). Swap 9 with 30 as shown in Figure 20.25(d).

Figure 20.25. Rebuild the heap after the root is removed.

(This item is displayed on page 685 in the print version)

20.5.3. Adding a New Node

To add a new node to the heap, first add it to the end of the heap and then rebuild the tree as follows:

  Let the last node be the current node;   while   (the current node is greater than its parent) { Swap the current node with its parent; Now the current node is one level up; }

Figure 20.26 shows the process of rebuilding a heap after adding a new node 88 to the heap in Figure 20.25(d). Place the new node 88 at the end of the tree, as shown in Figure 20.26(a). Swap 88 with 13, as shown in Figure 20.26(b). Swap 88 with 44, as shown in Figure 20.26(c). Swap 88 with 59, as shown in Figure 20.26(d).

[Page 685]

Figure 20.26. Rebuild the heap after adding a new node.

20.5.4. The Heap Class

Now you are ready to design and implement the Heap class. The class diagram is shown in Figure 20.27. Its implementation is given in Listing 20.10.

[Page 686]

Figure 20.27. Heap provides operations for manipulating a heap.

Listing 20.10. Heap.java

(This item is displayed on pages 686 - 687 in the print version)

 1   public class   Heap { 2    private   java.util.ArrayList list =   new   java.util.ArrayList();  3 4  /** Create a default heap */  5    public   Heap()  { 6 } 7 8  /** Create a heap from an array of objects */  9    public   Heap(Object[] objects)  { 10   for   (   int   i =     ; i < objects.length; i++) 11 add(objects[i]); 12 } 13 14  /** Add a new object into the heap */  15    public void   add(Object newObject)  { 16 list.add(newObject);  // Append to the heap  17   int   currentIndex = list.size() -   1   ;  // The index of the last node  18 19   while   (currentIndex >     ) { 20   int   parentIndex = (currentIndex -   1   ) /   2   ; 21  // Swap if the current object is greater than its parent  22   if   (((Comparable)(list.get(currentIndex))).compareTo( 23 list.get(parentIndex)) >     ) { 24 Object temp = list.get(currentIndex); 25 list.set(currentIndex, list.get(parentIndex)); 26 list.set(parentIndex, temp); 27 } 28   else   29   break   ;  // the tree is a heap now  30 31 currentIndex = parentIndex; 32 } 33 } 34 35  /** Remove the root from the heap */  36    public   Object remove()  { 37   if   (list.size() ==     )   return null   ; 38 39 Object removedObject = list.get(     ); 40 list.set(     , list.get(list.size() -   1   )); 41 list.remove(list.size() -   1   ); 42 43   int   currentIndex =     ; 44   while   (currentIndex < list.size()) {

[Page 687]

 45   int   leftChildIndex =   2   * currentIndex +   1   ; 46   int   rightChildIndex =   2   * currentIndex +   2   ; 47 48  // Find the maximum between two children  49   if   (leftChildIndex >= list.size())   break   ;  // The tree is a heap  50   int   maxIndex = leftChildIndex; 51   if   (rightChildIndex < list.size()) { 52   if   (((Comparable)(list.get(maxIndex))).compareTo( 53 list.get(rightChildIndex)) <     ) { 54 maxIndex = rightChildIndex; 55 } 56 } 57 58  // Swap if the current node is less than the maximum  59   if   (((Comparable)(list.get(currentIndex))).compareTo( 60 list.get(maxIndex)) <     ) { 61 Object temp = list.get(maxIndex); 62  list.set(maxIndex, list.get(currentIndex));  63  list.set(currentIndex, temp);  64  currentIndex = maxIndex;  65 } 66   else   67   break   ;  // The tree is a heap  68 } 69 70   return   removedObject; 71 } 72 73  /** Get the number of nodes in the tree */  74    public int   getSize()  { 75   return   list.size(); 76 } 77 }

A heap is represented using an array list internally (line 2). You may change it to other data structures, but the Heap class contract will remain unchanged. See Exercise 20.9.

The add(Object newObject) method (lines 15 “33) appends the object to the tree and then swaps it with its parent if it is greater than its parent. This process continues until the new object becomes the root or is not greater than its parent.

The remove() method (lines 36 “71) removes and returns the root. To maintain the heap property, the method moves the last object to the root position and swaps it with its larger child if it is less than the larger child. This process continues until the last object becomes a leaf or is not less than its children.

Listing 20.11 gives an example of using a heap to sort numbers . Line 3 creates a heap from an array of integers. The loop in lines 5 “7 displays all the elements in the heap in decreasing order.

Listing 20.11. TestHeap.java

 1   public class   TestHeap { 2   public static void   main(String[] args) { 3 Heap heap =   new   Heap(   new   Integer[]{   8   ,   9   ,   2   ,   3   ,   4   ,   1   ,   5   ,   6   ,   7   }); 4 5   while   (heap.getSize() >     ) 6 System.out.print(heap.remove() +   " "   ); 7 } 8 }

[Page 688]

The printout from Listing 20.11 is

 9 8 7 6 5 4 3 2 1