Welcome to Heapsort Interactive Tutorial. Input your
own values:
Explore the content of the diagram: move mouse over /
tap on the text.
(1) Introduction.
At the top of the diagram, an initial list contains random
values (not sorted).
At the bottom of the diagram, a sorted list is the result of the
algorithm.
Heapsort uses the concept of minimum heap to extract the minimum value, as described in the next steps.
As a matter of fact, Heapsort could work with a maximum heap, but for didactic purposes, this text
will only show a minimum heap
(2) Heapsort concept.
Heapsort is a sort algorithm with two parts: Fill Heap, and Extract
Minimum.
A Minimum Heap is a data structure with some rules to make it easy to extract
the minimum value.
Let's clear the heap to start a simulation.
Let's clear the heap to start a simulation.
First Part (Fill Heap): The input values are stored at the end of the heap,
one at a time. Some values may violate the heap property, what can be restored with swaps.
First Part (Fill Heap): The input values are stored at the end of the heap,
one at a time. Some values may violate the heap property, what can be restored with swaps.
The Fill Heap process is completed.
The second part is to Extract Minimum, one at a
time. After each extraction, the heap property can be restored with several promotions.
The second part is to Extract Minimum, one at
a
time. After each extraction, the heap property can be restored with several promotions.
The Extract Minimum process is completed.
(2) Advanced concepts: in-place.
The heap structure can be stored in a contiguous array with a simple math index transformation.
Also, Heapsort is an efficient sort algorithm, and one of the few in-place algorithms (in this
category).
In-place means: the algorithm does not require
additional storage memory (it requires only exchange of values).
For didactic purpose, the extract of value in the
diagram is not in-place.
For each extracted value, an empty space is created at
some place in the heap.
Instead of this, an empty space could be created at
the end of the heap.
So, the sorted list could be stored just after the
heap space storage, at this empty space.