Class HeapSort

An IInputMutatingSort implementation based on heapsort.

Inheritance
System.Object
HeapSort
Implements
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.Lists.Sorting
Assembly: MoreStructures.dll
Syntax
public class HeapSort : IInputMutatingSort
Remarks

ALGORITHM
- This sorting algorithm relies entirely on the max binary heap data structure.
- Given the list L to sort, it builds an heap H out of the entire list, passing L as backing structure for H.
- H is defined at the end of L and with an inverted order, so that it always pops the current minimum from the root located at very end of the list, and leaves holes at the beginning of the list.
- Then, it pops items from H, one by one, appending at the front of L, where the pop has left a hole.
- For example if L is 10 items long, the first pop will leave the item at index 0 unoccupied, the second pop will leave the item at index 1 unoccupied (the item at index 0 already is out of the picture), etc.
- Once the last item of H is popped, the heap is empty and L is sorted in ascending order.

COMPLEXITY
- Building a heap in batch from a list of n items takes a linear amount of time.
- Each pop takes a logarithmic amount of time, due to the sift down required to restore the heap property.
- Storing the popped item at the back of the list is a constant time operation.
- Because the heap is built in place on the provided list, the list is never replicated in memroy and only a constant amount of additional space is required, for heap re-adjustment operations.
- Therefore, Time Complexity is O(n * log(n)) and Space Complexity is O(1), where n is the number of items being sorted (which can be lower than the size of the provided list).

Methods

| Improve this Doc View Source

Sort<T>(IList<T>)


Uses the heapsort algorithm with the default comparer for T, given by .

Declaration
public void Sort<T>(IList<T> list)
    where T : IComparable<T>
Parameters
Type Name Description
IList<T> list
Type Parameters
Name Description
T
Remarks

| Improve this Doc View Source

Sort<T>(IList<T>, IComparer<T>)


Uses the heapsort algorithm with the specified comparer.

Declaration
public void Sort<T>(IList<T> list, IComparer<T> comparer)
Parameters
Type Name Description
IList<T> list
IComparer<T> comparer
Type Parameters
Name Description
T
Remarks

Implements

Extension Methods