Animation: Heapsort

Animation Systems Collection--Animations Collection

Description

The sorting algorithm Heapsort is based on the data structure where the greatest element is the root of the binary tree.

The sorting is divided into three steps:

1. Insert all Elements to be sorted into a nearly complete binary tree.
2. Conversion into a heap by starting with the last inner node and making sure that the current node is greater or equal to its children. If this is not the case the place of the node and its greatest child are swapped. The swapping process ("downheap") may have to be repeated recursively.
3. Remove the root of the heap – the greatest element of the partial tree – and swap it with the last leave (e.g. the element with the greatest index) Following that the binary tree has to be converted to a heap again as the new root probably is not greater than its children and so does not conform to the heap specification. When the heap is restored continue with step 2 until all elements have been removed.

Through the saving of the root of step i at the position n-i the (n-i)th-greatest element is then at its correct place.In the end all elements are sorted.

Heapsort guarantees a complexity of O(n * log n) and does not have a worst case unlike Quicksort which usually has the same complexity but can go up to a quadratic complexity in a worst case scenario.

Screen Shot(s):

Generating a heap from an unsorted binary tree

State after removing the root node twice (marked)

Reestablishing the heap condition along the blue path

After reestablishing the heap condition

Classification

• Algorithms
• Sorting Algorithms
• Data Structures
• Tree Structures

Animation Rating

You can provide a rating for this animation. The rating is performed on a scale of 1 to 10, where 10 is the highest possible grade.

1(very bad) 2 3 4 5 6 7 8 9 10(very good)

File information

Title	Heapsort
Animation URL	http://www.animal.ahrgr.de/Anims/en/heapsort.aml
Animation Applet	Animal Applet
Animation System	Animal
Animation Type	dynamic full VCR
Supported OS(s)	Linux,MacOS,Windows 95,Windows 98,Windows ME,Windows NT,Windows 2000,Unix
Author(s)	Marc-Daniel Haunschild
Date	1999-05-11
File Size size	5874 Byte
Number of Accesses:	15661
Added to DB by	Guido Rößling
Average Rating	5.4894(47 submitted ratings)
Language:	en
Number of Accesses:	15661

BibTeX bibliographic entry for citations:

@Misc{Haunschild:1999,
   author = {Marc-Daniel Haunschild},
   title = {Heapsort},
   howpublished = {WWW: \url{http://www.animal.ahrgr.de/Anims/en/heapsort.aml}},
 }