Java Reference
In-Depth Information
7
// Add elements to the heap
8
for
(
int
i =
0
; i < list.length; i++)
9 heap.add(list[i]);
10
11
// Remove elements from the heap
12
for
(
int
i = list.length -
1
; i >=
0
; i--)
13 list[i] = heap.remove();
14 }
15
16
/** A test method */
17
public static void
main(String[] args) {
18 Integer[] list = {
-44
,
-5
,
-3
,
3
,
3
,
1
,
-4
,
0
,
1
,
2
,
4
,
5
,
53
};
19 heapSort(list);
20
for
(
int
i =
0
; i < list.length; i++)
21 System.out.print(list[i] +
" "
);
22 }
23 }
add element
remove element
invoke sort method
-44 -5 -4 -3 0 1 1 2 3 3 4 5 53
23.6.6 Heap Sort Time Complexity
Let us turn our attention to analyzing the time complexity for the heap sort. Let
h
denote the
height for a heap of
n
elements. The height of a heap is the number of nodes in the longest path
from the root to a leaf node. Since a heap is a complete binary tree, the first level has 1 node,
the second level has 2 nodes, the
k
th level has 2
k
-
1
nodes, the (
h
height of a heap
1) level has 2
h
-
2
nodes,
-
and the
h
th level has at least 1 and at most 2
h
-
1
nodes. Therefore,
2
h
-
2
2
h
-
2
2
h
-
1
1
+
2
+
g
+
6
n
…
1
+
2
+
g
+
+
That is,
2
h
-
1
2
h
-
1
6
n
…
-
1
2
h
-
1
2
h
6
n
+
1
…
h
-
1
6
log(
n
+
1)
…
h
Thus,
h
6
log(
n
+
1)
+
1 and log(
n
+
1)
…
h
. Therefore, log(
n
+
1)
…
h
6
log(
n
1. Hence, the height of the heap is
O
(log
n
).
Since the
add
method traces a path from a leaf to a root, it takes at most
h
steps to add a
new element to the heap. Thus, the total time for constructing an initial heap is
O
(
n
log
n
) for
an array of
n
elements. Since the
remove
method traces a path from a root to a leaf, it takes
at most
h
steps to rebuild a heap after removing the root from the heap. Since the
remove
method is invoked
n
times, the total time for producing a sorted array from a heap is
O
(
n
log
n
).
Both merge sorts and heap sorts require
O
(
n
log
n
) time. A merge sort requires a temporary
array for merging two subarrays; a heap sort does not need additional array space. Therefore,
a heap sort is more space efficient than a merge sort.
+
1)
+
O
(
n
log
n
) worst-case time
heap sort vs. merge sort
23.13
What is a complete binary tree? What is a heap? Describe how to remove the root
from a heap and how to add a new object to a heap.
23.14
What is the return value from invoking the
remove
method if the heap is empty?
23.15
✓
✓
Check
Point
Add the elements
4
,
5
,
1
,
2
,
9
, and
3
into a heap in this order. Draw the diagrams to
show the heap after each element is added.
23.16
Show the heap after the root in the heap in Figure 23.15c is removed.
23.17
What is the time complexity of inserting a new element into a heap and what is the
time complexity of deleting an element from a heap?
Search WWH ::
Custom Search