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

23.18

Show the steps of creating a heap using {45, 11, 50, 59, 60, 2, 4, 7, 10}.

23.19

Given the following heap, show the steps of removing all nodes from the heap.

62

42 59

32 39 44 13

22 29 14 33 17 30 9

23.20

Which of the following statements are wrong?

1 Heap<Object> heap1 = new Heap<>();
2 Heap<Number> heap2 = new Heap<>();
3 Heap<BigInteger> heap3 = new Heap<>();
4 Heap<Calendar> heap4 = new Heap<>();
5 Heap<String> heap5 = new Heap<>();

23.7 Bucket Sort and Radix Sort
Bucket sorts and radix sorts are efficient for sorting integers.

Key
Point

All sort algorithms discussed so far are general sorting algorithms that work for any types of
keys (e.g., integers, strings, and any comparable objects). These algorithms sort the elements
by comparing their keys. It has been proven that no sorting algorithms based on comparisons
can perform better than O ( n log n ). However, if the keys are integers, you can use a bucket sort
without having to compare the keys.
The bucket sort algorithm works as follows. Assume the keys are in the range from 0 to t .
We need t + 1 buckets labeled 0 , 1 , . . . , and t . If an element's key is i , the element is put
into the bucket i . Each bucket holds the elements with the same key value.

bucket sort

Elements
with key 0

Elements
with key 1

Elements
with key 2

Elements
with key t

. . .

bucket[0] bucket[1] bucket[2] bucket[t]

You can use an ArrayList to implement a bucket. The bucket sort algorithm for sorting a list
of elements can be described as follows:

void bucketSort(E[] list) {
E[] bucket = (E[]) new java.util.ArrayList[t+ 1 ];

// Distribute the elements from list to buckets
for ( int i = 0 ; i < list.length; i++) {
int key = list[i].getKey(); // Assume element has the getKey() method

if (bucket[key] == null )
bucket[key] = new java.util.ArrayList<>();

bucket[key].add(list[i]);
}