SlideFinderPowerPoint search engine with thumbnail results
Newest Viewed Downloaded

Comparison of sorting methods

Initializing A Max Heap input array = [-, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

8 4 7 6 7 8 9 3 7 10 1 11 5 2

Initializing A Max Heap Start at rightmost array position that has a child.

8 4 7 6 7 8 9 3 7 10 1 11 5 2 Index is n/2.

Initializing A Max Heap Move to next lower array position.

8 4 7 6 7 8 9 3 7 10 1 5 11 2

Initializing A Max Heap

8 4 7 6 7 8 9 3 7 10 1 5 11 2

Initializing A Max Heap

8 9 7 6 7 8 4 3 7 10 1 5 11 2

Initializing A Max Heap

8 9 7 6 7 8 4 3 7 10 1 5 11 2

Initializing A Max Heap

8 9 7 6 3 8 4 7 7 10 1 5 11 2

Initializing A Max Heap

8 9 7 6 3 8 4 7 7 10 1 5 11 2

Initializing A Max Heap

8 9 7 6 3 8 4 7 7 10 1 5 11 Find a home for 2.

Initializing A Max Heap

8 9 7 6 3 8 4 7 7 5 1 11 Find a home for 2. 10

Initializing A Max Heap

8 9 7 6 3 8 4 7 7 2 1 11 Done, move to next lower array position. 10 5

Initializing A Max Heap

8 9 7 6 3 8 4 7 7 2 1 11 10 5 Find home for 1.

Initializing A Max Heap

11 8 9 7 6 3 8 4 7 7 2 10 5 Find home for 1.

Initializing A Max Heap

8 9 7 6 3 8 4 7 7 2 11 10 5 Find home for 1.

Initializing A Max Heap

8 9 7 6 3 8 4 7 7 2 11 10 5 Find home for 1.

Initializing A Max Heap

8 9 7 6 3 8 4 7 7 2 11 10 5 Done. 1

Time Complexity

8 7 6 3 4 7 7 10 11 5 2 9 8 1 Height of heap = h. Number of subtrees with root at level j is <= 2 j-1. Time for each subtree is O(h-j+1).

Complexity

Time for level j subtrees is <= 2j-1(h-j+1) = t(j). Total time is t(1) + t(2) + … + t(h-1) =

Heap Sort

Heap Sort (program 9.12) create a max heap keep extracting the root element from the max heap, and put the element into the result array accordingly time complexity = initialization time + n × deleting element time = O(n)+O(n × log n) = O(n log n)

Heap Sort --example

Showing 1 - 20 of 61 items Details

Name: 
mlec9-2
Author: 
Preferred Customer
Company: 
N/A
Description: 
Comparison of sorting methods
Tags: 
the | tree | leftist | min | heap | and | meld | root
Created: 
6/17/1995 11:31:02 PM
Slides: 
61
Views: 
0
Downloads: 
0
Rating: 
0


> Comment



Share this presentation
|
1234 Next >>

Comments

Share this presentation:

|
Sitemap