[Data Structure] Heaps Python Implementation

Heaps and the MaxHeap Class

Each level of a max-heap tree greows from left to right; a new level is added only after the current level fills up completely. 

Because the tree is nearly full (with at most one level not completely filled), an array implementation is efficient. The array implementation means that the root is always at index 0, and the index of any node's parent and children can be easily calculated:

• parent_index = (node_index - 1) // 2
• left_child_index = 2 * node_index + 1
• right_child_index = 2 * node_index + 2

* (// is for integer/floor division)

 

The MaxHeap class is defined with an initially-empty list as the only data member: self.heap_array = []

 

class MaxHeap:
    def __init__(self):
        self.heap_array = []

 

The list's elements are the nodes of the tree, but we don't define a Node class like other tree implementations. Even though there is no defined Node class, we still call the elements of the list nodes. 

 

---

Heap Prelocate Methods

The MaxHeap methods insert() and remove() make use of two methods, precolate_up() and precolate_down().

precolate_up() takes a string index (node_index) as an argument and compares the value at node_index (the current value) to the parent value. If the parent value is smaller than the current value, the two items swap positions in the list. The process than repeats from the current value's new position (previously parent value's position). The algorithm stops when the current value reaches the root (at index 0), or when the parent value is greater than or equal to the current value, meaning no max heap violations exist in the list. 

def precolate_up(self, node_index):
    while node_index > 0:
    	# Compute the parent node's index
        parent_index = (node_index - 1) // 2
        
        # Check for a violation of the max heap property
        if self.heap_array[node_index] <= self.heap_array[parent_index]:
            # No violation, so precolate up is done.
            return
        
        else:
            # swap heap_array[node_index] and heap_array[parent_index]
            (self.heap_array[node_index], self.heap_array[parent_index]) = (self.heap_array[parent_index], self.heap_array[node_index])
            
            # Continue the loop from the parent node
            node_index = parent_index

 

 

The precolate_down() method takes a starting index as an argument and compares the value at node_idnex (the current value) to the current value's two children's values. If either child's value is larger, the current value swaps position with the larger child. The process continues from the current value's new position. The algorithm ends when the current value is at the tree's bottom level, or when both children's values are less than or equal to the current value, meaning no max heap violation exist in the list. 

def precolate_down(self, node_index):
    child_index = 2 * node_index + 1
    value = self.heap_array[node_index]
    
    while child_index < len(self.heap_array):
        # Find the max among the node and the node's children
        max_value = value
        max_index = -1
        i = 0
        
        while i < 2 and i + child_index < len(self.heap_array):
            if self.heap_array[i + child_index] > max_value:
                max_value = self.heap_array[i + child_index]
                max_index = i + child_index
            i = i + 1
        
        # Check for a violation of the max heap property
        if max_value == value:
            return
        else:
            # Swap heap_array[node_index] and heap_array[max_index]
            (self.heap_array[node_index], self.heap_array[parent_index]) = (self.heap_array[parent_index], self.heap_array[node_index])
            
            # Continue loop from the larger child node
            node_index = max_index
            child_index = 2 * node_index + 1

 

---

insert() and remove() Methods

 

insert() and remove() methods are simple.

insert() method adds a new value to the end of the array, and use precolate_up() on the index. 

remove() method replaces the root node with the last index , and use precolate_down() on the new root index. 

def insert(self, value):
    # add the new value to the end of the array.
    self.heap_array.append(value)
    
    # percolate up from the last index to restore heap property.
    self.percolate_up(len(self.heap_array) - 1)

    
def remove(self):
    # save the max value from the root of the heap.
    max_value = self.heap_array[0]
    
    # move the last item in the array into index 0.
    replace_value = self.heap_array.pop()
    if len(self.heap_array) > 0:
        self.heap_array[0] = replace_value
        
        # percolate down to restore max heap property.
        self.percolate_down(0)
            
    # return the max value
    return max_value

 

Again, for min/max heaps, both insert() and remove() operations are O(log N) operations in the worst case.