Heap sort

HeapSort

CS 3358 Data Structures

1

Heapsort: Basic Idea

Problem: Arrange an array of items into sorted order.

1) Transform the array of items into a heap.
2) Invoke the “retrieve & delete” operation repeatedly, to
extract the largest item remaining in the heap, until the
heap is empty. Store each item retrieved from the heap
into the array from back to front.
Note: We will refer to the version of heapRebuild used by
Heapsort as rebuildHeap, to distinguish it from the version
implemented for the class PriorityQ.

2

Transform an Array Into a Heap: Example
6 3 5 7 2 4 10 9
0 1 2 3 4 5 6 7
rebuildHeap

6
• The items in the array, above,
can be considered to be
stored in the complete binary
3 5 tree shown at right.
• Note that leaves 2, 4, 9 & 10
are heaps; nodes 5 & 7 are
7 2 4 10 roots of semiheaps.
• rebuildHeap is invoked on
9 the parent of the last node in
the array (= 9).
3

6 3 5 9 2 4 10 7
0 1 2 3 4 5 6 7
rebuildHeap
• Note that nodes 2, 4, 7, 9 &
6 10 are roots of heaps; nodes
3 & 5 are roots of semiheaps.
3 5 • rebuildHeap is invoked on
the node in the array
preceding node 9.
9 2 4 10

7

10

6 3 10 9 2 4 5 7
0 1 2 3 4 5 6 7
rebuildHeap
• Note that nodes 2, 4, 5, 7, 9
6 & 10 are roots of heaps;
node 3 is the root of a
3 10 semiheap.
9 2 4 5 preceding node 10.

7

11

6 3 10 9 2 4 5 7
0 1 2 3 4 5 6 7
rebuildHeap
• Note that nodes 2, 4, 5, 7, 9
6 & 10 are roots of heaps;
3 10 semiheap.
9 2 4 5 preceding node 10.

7

12

6 9 10 3 2 4 5 7
0 1 2 3 4 5 6 7
rebuildHeap
• Note that nodes 2, 4, 5, 7 &
6 10 are roots of heaps; node 3
is the root of a semiheap.
9 10 • rebuildHeap is invoked
recursively on node 3 to
complete the transformation
3 2 4 5 of the semiheap rooted at 9
into a heap.
7

13

6 9 10 7 2 4 5 3
0 1 2 3 4 5 6 7
rebuildHeap
• Note that nodes 2, 3, 4, 5, 7,
6 9 & 10 are roots of heaps;
9 10 semiheap.
• The recursive call to
rebuildHeap returns to node
7 2 4 5 9.
3
preceding node 9.
14

10 9 6 7 2 4 5 3
0 1 2 3 4 5 6 7

10 • Note that node 10 is now the
root of a heap.
• The transformation of the
9 6
array into a heap is complete.

7 2 4 5

3

15

Transform an Array Into a Heap (Cont’d.)

• Transforming an array into a heap begins by invoking
rebuildHeap on the parent of the last node in the array.
• Recall that in an array-based representation of a complete binary
tree, the parent of any node at array position, i, is
 (i – 1) / 2 
• Since the last node in the array is at position n – 1, it follows
that transforming an array into a heap begins with the node at
position
 (n – 2) / 2  =  n / 2  – 1
and continues with each preceding node in the array.

16

Transform an Array Into a Heap: C++

// transform array a[ ], containing n items, into a heap
for( int root = n/2 – 1; root >= 0; root – – )
{
// transform a semiheap with the given root into a heap
rebuildHeap( a, root, n );
}

17

Rebuild a Heap: C++
// transform a semiheap with the given root into a heap
void rebuildHeap( ItemType a[ ], int root, int n )
{ int child = 2 * root + 1; // set child to root’s left child, if any
if( child < n ) // if root’s left child exists . . .
{ int rightChild = child + 1;
if( rightChild < n && a[ rightChild ] > a[ child ] )
child = rightChild; // child indicates the larger item
if( a[ root ] < a[ child ] )
{ swap( a[ root ], a[ child ] );
rebuildHeap( a, child, n );
}
}
}
18

Transform a Heap Into a Sorted Array

• After transforming the array of items into a heap, the next
step in Heapsort is to:
– invoke the “retrieve & delete” operation repeatedly, to
extract the largest item remaining in the heap, until the
heap is empty. Store each item retrieved from the heap
into the array from back to front.
• If we want to perform the preceding step without using
additional memory, we need to be careful about how we
delete an item from the heap and how we store it back into
the array.

19

Transform a Heap Into a Sorted Array:
Basic Idea
Problem: Transform array a[ ] from a heap of n items into a
sequence of n items in sorted order.
Let last represent the position of the last node in the heap. Initially,
the heap is in a[ 0 .. last ], where last = n – 1.
1) Move the largest item in the heap to the beginning of an (initially
empty) sorted region of a[ ] by swapping a[0] with a[ last ].
2) Decrement last. a[0] now represents the root of a semiheap in
a[ 0 .. last ], and the sorted region is in a[ last + 1 .. n – 1 ].
3) Invoke rebuildHeap on the semiheap rooted at a[0] to transform
the semiheap into a heap.
4) Repeat steps 1 - 3 until last = -1. When done, the items in array
a[ ] will be arranged in sorted order.
20

Transform a Heap Into a Sorted Array: Example
0 1 2 3 4 5 6 7
a[ ]: 10 9 6 7 2 4 5 3
Heap

10 • We start with the heap that
we formed from an unsorted
array.
9 6
• The heap is in a[0..7] and the
sorted region is empty.
7 2 4 5 • We move the largest item in
the heap to the beginning of
the sorted region by
3 swapping a[0] with a[7].
21

0 1 2 3 4 5 6 7
a[ ]: 3 9 6 7 2 4 5 10
Semiheap Sorted
rebuildHeap
• a[0..6] now represents a
3 semiheap.
• a[7] is the sorted region.
9 6
• Invoke rebuildHeap on the
semiheap rooted at a[0].

7 2 4 5

22

0 1 2 3 4 5 6 7
a[ ]: 9 3 6 7 2 4 5 10
Becoming a Heap Sorted
rebuildHeap
• rebuildHeap is invoked
9 recursively on a[1] to
of the semiheap rooted at a[0]
3 6 into a heap.

7 2 4 5

23

0 1 2 3 4 5 6 7
a[ ]: 9 7 6 3 2 4 5 10
Heap Sorted

• a[0] is now the root of a heap
9 in a[0..6].
• We move the largest item in
7 6 the sorted region by
swapping a[0] with a[6].
3 2 4 5

24

0 1 2 3 4 5 6 7
a[ ]: 5 7 6 3 2 4 9 10
Semiheap Sorted
rebuildHeap
5 semiheap.
• a[6..7] is the sorted region.
7 6

3 2 4

25

0 1 2 3 4 5 6 7
a[ ]: 7 5 6 3 2 4 9 10
Heap Sorted
rebuildHeap
• Since a[1] is the root of a
7 heap, a recursive call to
rebuildHeap does nothing.
5 6 in a[0..5].
3 2 4 the heap to the beginning of
the sorted region by
26

0 1 2 3 4 5 6 7
a[ ]: 4 5 6 3 2 7 9 10
Semiheap Sorted
rebuildHeap
4 semiheap.
5 6

3 2

27

0 1 2 3 4 5 6 7
a[ ]: 6 5 4 3 2 7 9 10
Heap Sorted

6 in a[0..4].
3 2

28

0 1 2 3 4 5 6 7
a[ ]: 2 5 4 3 6 7 9 10
Semiheap Sorted
rebuildHeap
2 semiheap.
5 4

3

29

0 1 2 3 4 5 6 7
a[ ]: 5 2 4 3 6 7 9 10
Becoming a Heap Sorted
rebuildHeap
• rebuildHeap is invoked
5 recursively on a[1] to
of the semiheap rooted at a[0]
2 4 into a heap.

3

30

0 1 2 3 4 5 6 7
a[ ]: 5 3 4 2 6 7 9 10
Heap Sorted

5 in a[0..3].
2

31

0 1 2 3 4 5 6 7
a[ ]: 2 3 4 5 6 7 9 10
Semiheap Sorted
rebuildHeap
2 semiheap.
3 4

32

0 1 2 3 4 5 6 7
a[ ]: 4 3 2 5 6 7 9 10
Heap Sorted

4 in a[0..2].

33

0 1 2 3 4 5 6 7
a[ ]: 2 3 4 5 6 7 9 10
Semiheap Sorted
rebuildHeap
2 semiheap.
3

34

0 1 2 3 4 5 6 7
a[ ]: 3 2 4 5 6 7 9 10
Heap Sorted

3 in a[0..1].
2 the sorted region by

35

0 1 2 3 4 5 6 7
a[ ]: 2 3 4 5 6 7 9 10
Heap Sorted

2 • Since a[0] is a heap, a
recursive call to rebuildHeap
does nothing.
• We move the only item in the
heap to the beginning of the
sorted region.

36

0 1 2 3 4 5 6 7
a[ ]: 2 3 4 5 6 7 9 10
Sorted

• Since the sorted region
contains all the items in the
array, we are done.

37

Heapsort: C++
void heapsort( ItemType a[ ], int n )
{ // transform array a[ ] into a heap
for( int root = n/2 – 1; root >= 0; root – – )
rebuildHeap( a, root, n );
for( int last = n – 1; last > 0; )
{ // move the largest item in the heap, a[ 0 .. last ], to the
// beginning of the sorted region, a[ last+1 .. n–1 ], and
// increase the sorted region
swap( a[0], a[ last ] ); last – – ;
// transform the semiheap in a[ 0 .. last ] into a heap
rebuildHeap( a, 0, last );
}
}
38

Heapsort: Efficiency
• rebuildHeap( ) is invoked  n / 2  times to transform an array of
n items into a heap. rebuildHeap( ) is then called n – 1 more
times to transform the heap into a sorted array.
• From our analysis of the heap-based, Priority Queue, we saw
that rebuilding a heap takes O( log n ) time in the best, average,
and worst cases.
• Therefore, Heapsort requires
O( [  n / 2  + (n – 1) ] * log n ) = O( n log n )
time in the best, average and worst cases.
• This is the same growth rate, in all cases, as Mergesort, and the
same best and average cases as Quicksort.
• Knuth’s analysis shows that, in the average case, Heapsort
requires about twice as much time as Quicksort, and 1.5 times as
much time as Mergesort (without requiring additional storage).
39

Growth Rates for Selected Sorting Algorithms
Best case Average case (†) Worst case
Selection sort n2 n2 n2
Bubble sort n n2 n2
Insertion sort n n2 n2
Mergesort n * log2 n n * log2 n n * log2 n
Heapsort n * log2 n n * log2 n n * log2 n
Treesort n * log2 n n * log2 n n2
Quicksort n * log2 n n * log2 n n2
Radix sort n n n
†
According to Knuth, the average growth rate of Insertion sort is about
0.9 times that of Selection sort and about 0.4 times that of Bubble Sort.
Also, the average growth rate of Quicksort is about 0.74 times that of
Mergesort and about 0.5 times that of Heapsort.
40

Heap sort

Recommended

Recommended

More Related Content

What's hot

What's hot (20)

Viewers also liked

Viewers also liked (17)

Recently uploaded

Recently uploaded (20)

Heap sort