.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)

Related Courses

Course

Learn Data Structures and Algorithms with Python

Intermediate

37 Lessons
Path

Computer Science

Beginner friendly

83 Lessons