Class Heapsort

java.lang.Object
topics.sorting.heapsort.Heapsort
All Implemented Interfaces:
SortingAlgorithm
public class Heapsort extends Object implements SortingAlgorithm

Heapsort

A highly efficient comparison-based sorting algorithm that utilizes a binary heap data structure. It divides its execution into two distinct phases:

Algorithm Steps

  1. Build Heap: Rearrange the array elements into a valid Max-Heap structure in O(N) time.
  2. Extract Max: Repeatedly swap the root of the heap (the maximum value) with the last element of the unsorted segment, reduce the heap size by 1, and restore the heap property via a "down-heap" (sift-down) operation.

Complexity Analysis

  • Time Complexity: O(N log N) strictly in all cases (Best, Average, Worst).
  • Space Complexity: O(1) - The binary tree is mapped implicitly onto the array, requiring no external memory.
  • Stability: No - Operations on the heap tree structure routinely leapfrog equal elements, destroying relative order.
Author:
vicegd
See Also:
  • invalid reference 
    topics.sorting.SortingAlgorithm

  • Constructor Summary

    Constructors
    Constructor
    Description
    Heapsort()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    sort(int[] elements)
    Sorts the elements in-place silently.
    void
    sort(int[] elements, boolean trace)
    Sorts the elements in-place, optionally emitting step-by-step traces to visualize the algorithmic progression.

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • Heapsort

      public Heapsort()

  • Method Details

    • sort

      public void sort(int[] elements)
      Description copied from interface: SortingAlgorithm
      Sorts the elements in-place silently.
      Specified by:
      sort in interface SortingAlgorithm
      Parameters:
      elements - The array of integers to be sorted.

    • sort

      public void sort(int[] elements, boolean trace)
      Description copied from interface: SortingAlgorithm
      Sorts the elements in-place, optionally emitting step-by-step traces to visualize the algorithmic progression.
      Specified by:
      sort in interface SortingAlgorithm
      Parameters:
      elements - The array of integers to be sorted.
      trace - If true, logs the internal state during execution.