1. Welcome to Heapsort Interactive Tutorial. Input your own values:
  2. Explore the content of the diagram: move mouse over / tap on the text.
  3. (1) Introduction.
  4. At the top of the diagram, an initial list contains random values (not sorted).
  5. At the bottom of the diagram, a sorted list is the result of the algorithm.
  6. Heapsort uses the concept of minimum heap to extract the minimum value, as described in the next steps.
  7. As a matter of fact, Heapsort could work with a maximum heap, but for didactic purposes, this text will only show a minimum heap
  8. (2) Heapsort concept.
  9. Heapsort is a sort algorithm with two parts: Fill Heap, and Extract Minimum.
  10. A Minimum Heap is a data structure with some rules to make it easy to extract the minimum value.
  11. Let's clear the heap to start a simulation.
  12. Let's clear the heap to start a simulation.
  13. 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.
  14. 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.
  15. The Fill Heap process is completed.
  16. The second part is to Extract Minimum, one at a time. After each extraction, the heap property can be restored with several promotions.
  17. The second part is to Extract Minimum, one at a time. After each extraction, the heap property can be restored with several promotions.
  18. The Extract Minimum process is completed.
  19. (2) Advanced concepts: in-place.
  20. The heap structure can be stored in a contiguous array with a simple math index transformation.
  21. Also, Heapsort is an efficient sort algorithm, and one of the few in-place algorithms (in this category).
  22. In-place means: the algorithm does not require additional storage memory (it requires only exchange of values).
  23. For didactic purpose, the extract of value in the diagram is not in-place.
  24. For each extracted value, an empty space is created at some place in the heap.
  25. Instead of this, an empty space could be created at the end of the heap.
  26. So, the sorted list could be stored just after the heap space storage, at this empty space.
  27. (3) Advanced concepts: stable / unstable sort algorithm.
  28. When a list contains two or more values that are exactly the same, how do you compare those values?
  29. In some applications, data with the same value may use additional information (what results in equal values not being the same).
  30. So, a stable / unstable sort algorithm may be relevant, for some applications.
  31. Heapsort can be implemented as a stable sort algorithm, but with some additional storage space.
  32. Originally in 1964, J. W. J. Williams described the Heapsort algorithm. Later R. W. Floyd published an in-place version of the algorithm.
  33. The end. Also, visit Quicksort Interactive Tutorial and Mergesort Interactive Tutorial.

This software is open source.