Codecademy Logo

Heaps and Heapsort

.add() Method

The .add() method is used in the MaxHeap class to add new values to a max-heap while maintaining the max-heap property that a parent must have a larger value than its children.

def add(self, element):
self.count += 1
print("Adding: {0} to {1}".format(element, self.heap_list))
self.heap_list.append(element)
self.heapify_up()

.heapify_up() Method

The .heapify_up() method is used in the MaxHeap class to rebalance the heap data structure after an element is added to it.

Starting at the end of the heap where the new element is placed, the new element is compared to its parent value. If the parent has a smaller value than the child, the values swap places. This process repeats itself until an element has no parent value.

def heapify_up(self):
print("Heapifying up")
idx = self.count
while self.parent_idx(idx) > 0:
child = self.heap_list[idx]
parent = self.heap_list[self.parent_idx(idx)]
if parent < child:
print("swapping {0} with {1}".format(parent, child))
self.heap_list[idx] = parent
self.heap_list[self.parent_idx(idx)] = child
idx = self.parent_idx(idx)
print("Heap Restored {0}".format(self.heap_list))

Heapsort

Heapsort is a sorting algorithm that utilizes the heap data structure to sort an unordered list of data.

To implement a heapsort algorithm, take the following steps:

  • Add items of an unsorted list into a max-heap.
  • While there is at least one element in the heap, remove the root of the heap and place it at the beginning of a list that will hold the sorted values. Whenever the root is extracted, the heap must be rebalanced.
  • Once the heap is empty, return the sorted list.
def heapsort(lst):
sort = []
max_heap = MaxHeap()
# Add items of an unsorted list into a max-heap.
for idx in lst:
max_heap.add(idx)
# While there is at least one element in the heap, remove the root of the heap and place it at the beginning of a list that will hold the sorted values. Whenever the root is extracted, the heap must be rebalanced.
while max_heap.count > 0:
max_value = max_heap.retrieve_max()
sort.insert(0, max_value)
# Return the sorted list
return sort
my_list = [99, 22, 61, 10, 21, 13, 23]
sorted_list = heapsort(my_list)
print(sorted_list) # Prints: [10, 13, 21, 22, 23, 61, 99]

.retrieve_max() Method

The .retrieve_max() method is used in the heapsort algorithm to return the largest value in a heap.

In this method, the root of the heap is extracted and replaced by the last element in the heap. Then, the method rebalances the heap data structure using .heapify_down(). Finally, the method returns the largest value.

def retrieve_max(self):
if self.count == 0:
print("No items in heap")
return None
# Store the largest value in a variable
max_value = self.heap_list[1]
print("Removing: {0} from {1}".format(max_value, self.heap_list))
# Replace the root of the heap with the last element in the list
self.heap_list[1] = self.heap_list[self.count]
# Decrease the count
self.count -= 1
# Remove the last element in the list
self.heap_list.pop()
print("Last element moved to first: {0}".format(self.heap_list))
# Rebalance the heap
self.heapify_down()
# Return the largest value
return max_value

.heapify_down() Method

The .heapify_down() method is used in the heapsort algorithm to rebalance the heap data structure after the root is removed and replaced with the last element in the heap.

While an element contains a child value, the parent value is compared with the value of its largest child. The larger child is determined using the .get_larger_child_idx() method. If the parent has a smaller value than the child, the two elements are swapped. Once an element has no children, the heap is restored.

def heapify_down(self):
idx = 1
# This while loop will execute as long as a child element is present
while self.child_present(idx):
print("Heapifying down!")
# Get the index of the child element with the larger value
larger_child_idx = self.get_larger_child_idx(idx)
child = self.heap_list[larger_child_idx]
parent = self.heap_list[idx]
# If the parent value is less than the child value, swap the values
if parent < child:
self.heap_list[idx] = child
self.heap_list[larger_child_idx] = parent
idx = larger_child_idx
print("HEAP RESTORED! {0}".format(self.heap_list))

.get_larger_child_idx() Method

The .get_larger_child_idx() method, which is used in the heapsort algorithm, compares the values of an element’s children and returns the index of the child with the larger value.

def get_larger_child_idx(self, idx):
# Check if a right child exists
if self.right_child_idx(idx) > self.count:
print("There is only a left child")
return self.left_child_idx(idx)
else:
left_child = self.heap_list[self.left_child_idx(idx)]
right_child = self.heap_list[self.right_child_idx(idx)]
# Compare the left and right child values and return the index of the larger child
if left_child > right_child:
print("Left child "+ str(left_child) + " is larger than right child " + str(right_child))
return self.left_child_idx(idx)
else:
print("Right child " + str(right_child) + " is larger than left child " + str(left_child))
return self.right_child_idx(idx)

Learn more on Codecademy