Skip to content
This repository has been archived by the owner. It is now read-only.
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
69 lines (51 sloc) 1.56 KB
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.
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
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)
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)
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
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
You can’t perform that action at this time.