Source code for algorithms.sorting.heap_sort

"""
    Heap Sort
    ---------
    Uses the max heap data structure implemented in a list.

    Time Complexity: O(n log n)

    Space Complexity: O(1) Auxiliary

    Stable: Yes

    Psuedo Code: CLRS. Introduction to Algorithms. 3rd ed.

"""


[docs]def max_heapify(seq, i, n): """ The function of max_heapify is to let the value at seq[i] "float down" in the max-heap so that the subtree rooted at index i becomes a max-heap. :param seq: A list of integers :param i: An integer that is an index in to the list that represents the root of a subtree that max heapify is called on. :param n: length of the list """ l = 2 * i + 1 r = 2 * i + 2 if l <= n and seq[l] > seq[i]: largest = l else: largest = i if r <= n and seq[r] > seq[largest]: largest = r if largest != i: seq[i], seq[largest] = seq[largest], seq[i] max_heapify(seq, largest, n)
[docs]def build_heap(seq): """ Continously calls max_heapify on the list for each subtree. :param seq: A list of integers """ n = len(seq) - 1 for i in range(n//2, -1, -1): max_heapify(seq, i, n)
[docs]def sort(seq): """ Takes a list of integers and sorts them in ascending order. This sorted list is then returned. :param seq: A list of integers :rtype: A list of sorted integers """ build_heap(seq) heap_size = len(seq) - 1 for x in range(heap_size, 0, -1): seq[0], seq[x] = seq[x], seq[0] heap_size = heap_size - 1 max_heapify(seq, 0, heap_size) return seq