Heap Sort
What is a heap?
A heap is a tree that has the "heap" property. There can be either max heaps or min heaps. A max heap has the property that for every parent node, it's key is greater than or equal to the key of its child nodes. In other words, in a max heap, the biggest number is at the top.
A min heap is similar to a max heap, except that the parent's key is less than or equal to the child's key. Therefore in a min heap, the smallest number is at the top (or root) of the tree.
What is heapsort?
Heapsort uses a heap data structure in order to perform a sort. It's an in-place comparison sort. The code implementation uses 3 functions: Heapsort, BuildHeap, and Heapify. Heapsort is the main/entry function, BuildHeap forms your initial heap, and Heapify is to make a non-heap tree into a heap. An important thing to recognize is that an array can be a representation of a tree. Imagine arr[0] as the root of the tree and arr[1] and arr[2] as the left and right nodes of the root. Then arr[3] and arr[4] would be the left and right nodes of arr[1], and so on. For example, take the max heap pictured above. In an array representation that would look like:
arr = [100, 19, 36, 17, 3, 25, 1, 2, 7]Thus, for any given index i, its children are:
left:
2*i + 1right:
2*i + 2
Pseudocode
The pseudocode for the algorithm goes like this: 1. Using the given array, build a heap using recursive insertion 2. Iterate to extract the max element in the heap and then reheapify the heap 3. Extracted elements form a sorted subsequence
Heapsort(Arr)
BuildHeap(Arr)
for i in range Arr size down to 1
swap(Arr[1], Arr[i])
NewSize = reduce size by one
Heapify(Arr, NewSize, 1)
BuildHeap(Arr)
n = Arr size
for i in floor(n/2) down to 0
Heapify(Arr, n, i AKA the RootIndex)
Heapify(Arr, i, size)
max = i
left = 2i
right = 2i+1
if (left <= size) and (Arr[left] > Arr[max])
max = left
if (right<=size) and (Arr[right] > Arr[max])
max = right
if (max != i)
swap(Arr[i], Arr[max])
Heapify(Arr, max)Code in Python
For working code in Python, visit this repl.
def heap_sort(list):
# For ease, let's make a variable for the size of the array
size = len(list)
# Build inital heap structure
build_heap(list, size)
# Loop from length down to 2 to heapify
for i in range(size - 1, 0, -1):
#swap first and "last"
list[0], list[i] = list[i], list[0]
# Call heapify on reduced list size
heapify(list, i, 0)
return list
# Convert array/list to a heap
def build_heap(list, size):
for i in range(size // 2, -1, -1):
heapify(list, size, i)
# Make our tree into a max heap
def heapify(sublist, size, root_index):
largest = root_index
left = 2*root_index + 1
right = 2*root_index + 2
if(left < size and sublist[left] > sublist[largest]):
largest = left
if(right < size and sublist[right] > sublist[largest]):
largest = right
if(root_index != largest):
sublist[largest], sublist[root_index] = sublist[root_index], sublist[largest]
heapify(sublist, size, largest)
# Test Data
print(heap_sort([8, 2, 1, 4, 6, 5, 7, 3, 22, 1, 19, 3, 33, 7, -3, 111, 21, -4, 0, 99, 89]))References
Last updated
Was this helpful?