About testing and printing

I learned the importance of testing and printing from the previous 2 days.

class MaxMinHeap:
    def __init__(self, max_len):
        self.heap_arr = [0 for _ in range(max_len + 1)]
        self.arr_len = 0

    def empty(self):
        if self.arr_len == 0:
            return True
        return False

    def is_min_level(self):
        if math.floor(math.log2(self.arr_len)) % 2 == 1:
            return False
        return True

    def insert_num(self, input_num):
        self.arr_len += 1
        self.heap_arr[self.arr_len] = input_num
        if self.arr_len == 1:
            return
        elif self.is_min_level():
            self.min_insert()
        else:
            self.max_insert()

    def max_insert(self):
        if self.heap_arr[self.arr_len // 2] > self.heap_arr[self.arr_len]:
            self.heap_arr[self.arr_len], self.heap_arr[self.arr_len // 2] = self.heap_arr[self.arr_len // 2], self.heap_arr[self.arr_len]
            self.minify_up(self.arr_len // 2)
        else:
            self.maxity_up(self.arr_len)

    def min_insert(self):
        if self.heap_arr[self.arr_len // 2] < self.heap_arr[self.arr_len]:
            self.heap_arr[self.arr_len], self.heap_arr[self.arr_len // 2] = self.heap_arr[self.arr_len // 2], self.heap_arr[self.arr_len]
            self.maxity_up(self.arr_len // 2)
        else:
            self.minify_up(self.arr_len)

    def max_output(self):
        if self.empty():
            return None
        if self.arr_len == 1:
            self.arr_len -= 1
            return self.heap_arr[1]
        temp_index = 2
        if temp_index + 1 <= self.arr_len and self.heap_arr[temp_index] < self.heap_arr[temp_index + 1]:
            temp_index += 1
        self.heap_arr[self.arr_len], self.heap_arr[temp_index] = self.heap_arr[temp_index], self.heap_arr[self.arr_len]
        self.arr_len -= 1
        self.maxify_down(temp_index)
        return self.heap_arr[self.arr_len + 1]

    def min_output(self):
        if self.empty():
            return None
        self.heap_arr[self.arr_len], self.heap_arr[1] = self.heap_arr[1], self.heap_arr[self.arr_len]
        self.arr_len -= 1
        self.minify_down(1)
        return self.heap_arr[self.arr_len + 1]

    def maxify_down(self, input_index):
        while input_index * 2 <= self.arr_len:
            if input_index * 4 > self.arr_len:
                comp_index = input_index * 2
                if comp_index + 1 <= self.arr_len and self.heap_arr[comp_index] < self.heap_arr[comp_index + 1]:
                    comp_index += 1
                if self.heap_arr[input_index] < self.heap_arr[comp_index]:
                    self.heap_arr[input_index], self.heap_arr[comp_index] = self.heap_arr[comp_index], self.heap_arr[input_index]
                return
            comp_index = input_index * 2 + 1
            for temp_index in range(input_index * 4, input_index * 4 + 4):
                if temp_index <= self.arr_len and self.heap_arr[comp_index] < self.heap_arr[temp_index]:
                    comp_index = temp_index
            if self.heap_arr[input_index] < self.heap_arr[comp_index]:
                self.heap_arr[input_index], self.heap_arr[comp_index] = self.heap_arr[comp_index], self.heap_arr[input_index]
            if comp_index == input_index * 2 + 1:
                return
            if self.heap_arr[comp_index] < self.heap_arr[comp_index // 2]:
                self.heap_arr[comp_index // 2], self.heap_arr[comp_index] = self.heap_arr[comp_index], self.heap_arr[comp_index // 2]
            input_index = comp_index

    def minify_down(self, input_index):
        while input_index * 2 <= self.arr_len:
            if input_index * 4 > self.arr_len:
                comp_index = input_index * 2
                if comp_index + 1 <= self.arr_len and self.heap_arr[comp_index] > self.heap_arr[comp_index + 1]:
                    comp_index += 1
                if self.heap_arr[input_index] > self.heap_arr[comp_index]:
                    self.heap_arr[input_index], self.heap_arr[comp_index] = self.heap_arr[comp_index], self.heap_arr[input_index]
                return
            comp_index = input_index * 2 + 1
            for temp_index in range(input_index * 4, input_index * 4 + 4):
                if temp_index <= self.arr_len and self.heap_arr[comp_index] > self.heap_arr[temp_index]:
                    comp_index = temp_index
            if self.heap_arr[input_index] > self.heap_arr[comp_index]:
                self.heap_arr[input_index], self.heap_arr[comp_index] = self.heap_arr[comp_index], self.heap_arr[input_index]
            if comp_index == input_index * 2 + 1:
                return
            if self.heap_arr[comp_index] > self.heap_arr[comp_index // 2]:
                self.heap_arr[comp_index // 2], self.heap_arr[comp_index] = self.heap_arr[comp_index], self.heap_arr[comp_index // 2]
            input_index = comp_index

    def maxity_up(self, input_index):
        while input_index // 4 > 0:
            comp_index = input_index // 4
            if self.heap_arr[comp_index] >= self.heap_arr[input_index]:
                break
            self.heap_arr[comp_index], self.heap_arr[input_index] = self.heap_arr[input_index], self.heap_arr[comp_index]
            input_index = comp_index

    def minify_up(self, input_index):
        while input_index // 4 > 0:
            comp_index = input_index // 4
            if self.heap_arr[comp_index] <= self.heap_arr[input_index]:
                break
            self.heap_arr[comp_index], self.heap_arr[input_index] = self.heap_arr[input_index], self.heap_arr[comp_index]
            input_index = comp_index

I made the following code and got lots of errors(It is fixed now).

This made the debugging process so hard to follow.

So I uploaded the problem to stackoverflow: https://stackoverflow.com/questions/74849006/having-problems-making-a-max-min-priority-queuepython/74852593#74852593

Having problems making a max-min priority queue(python)

 

The answer I got helped alot, and if you never tested your code I recommend reading the response(Thank you so much!).

From this I learned the importance of testing. All the code below are from the response.

 

First is to print the class to get the output we want.

def print(self, i=1, tab=""):
    if i > self.arr_len:
        return
    self.print(i * 2 + 1, tab + "     ")
    print(tab, self.heap_arr[i])
    self.print(i * 2, tab + "     ")

Adding this single simple function to the class made all the debugging processes easier to view.

 

Next is a verify function to check if the heap is correct.

def verify(self, i=1, is_min=True, low=-math.inf, high=math.inf):
    if i > self.arr_len:
        return
    val = self.heap_arr[i]
    if not (low <= val <= high):
        self.print()
        raise ValueError(f"inconsistent heap at {val}")
    if is_min:
        low = val
    else:
        high = val
    self.verify(i*2, not is_min, low, high)
    self.verify(i*2+1, not is_min, low, high)

This will print an error if the input is wrong with the exact point it cases an error.

 

Lastly 'random' import is used to input a random input and get the corresponding output.

import random

orig = list(range(20))
for i in range(100):  # repeat a few times with different shuffles of input
    values = orig[:]
    random.shuffle(values)
    heap  = MaxMinHeap(len(values)+3)  # Allocate enough space for the heap
    for value in values:  # Insert the values in their shuffled order
        heap.insert_num(value)
        heap.verify()  # ... and each time verify all is well

    res = []  # output of values as they are removed from the heap
    while not heap.empty():
        res.append(heap.min_output())
        heap.verify()

    if res != orig:
        print(values)
        print("Removal was not in order", res)
        break

This will check if the heap is correct for every random input and output.

 

These steps will be used by me for future code where the code is too long to debug.