Min-Max heap

A min-max heap takes input at time O(logn) and output of max num and min num of O(1).

Basic Min-Max Heap

This is a min-max heap with a min root. At the right side we can see the level of the heap. In the max level all the child nodes are smaller than the current one and in the min level all the child nodes are larger than the current one.

Inserting a Node in a Max-Min Heap

To insert a value to the heap we add the number to the end of the heap array. Then depending on the level it is in we compare the number to the parent. If the node is at a max level like the top image then we check if the node is bigger than the parent. If the parent is bigger we know that all the nodes at max level in the path to the node are greater than the parent. So we just need to check the min level path for updates. If the parent is smaller then we know that the node is greater than all the nodes at min level in the path to the node. So we just need to check the max level path for updates. For min level insertion it works the same but with the opposite logic.

Taking the Max or Min from Min-Max Heap

If we need the min node then we swap the root node and the last node, update the heap and then pop the last node in the heap array. if we need the max node then we check the node at address 2 and 3 to find the larger number. We then swap the nodes and then update the heap from that node down. Lastly we pop the last node in the heap array.

Here is where we get a lot of variance to the remaining heap. Here are some of the examples.

Situations When Updating Heap

If the current node has a grindchild when we just have to find the smallest number, but that is not true because if we see the second example we will get 3 instead of the real min number 1. So when the node has grandchildren we just have to check all the grandchildren and the right child. The left child doesn't need to be checked, because if there are grandchildren then the left child will have its child and this child will be smaller than the parent. Lastly if we follow this logic in the first example we will get the 27 node at 1's place. Then we have to check the parent node to see if it is bigger. If the parent is smaller than the swaped node then we have to switch it making the 9 node go to 1's place instead and 27 node going to the 9's place. When we have no grandchildren like in the third example we just have to compare with the children and swap if its smaller than the current node.

This is the code I made for the max-min heap.

import sys, math, random


class MaxMinHeap:
    def __init__(self, max_len):
        # Has the actual heap
        self.heap_arr = [0 for _ in range(max_len + 1)]
        # The array length
        self.arr_len = 0

    # checks if the array is empty
    def empty(self):
        if self.arr_len == 0:
            return True
        return False

    # checks if the level of the input is min
    def is_min_level(self):
        if math.floor(math.log2(self.arr_len)) % 2 == 1:
            return False
        return True

    # inputs a number to the min-max heap
    def insert_num(self, input_num):
        # add 1 to the length of the heap
        self.arr_len += 1
        # set the number to the last index of the array
        self.heap_arr[self.arr_len] = input_num
        # if the input is at the root
        if self.arr_len == 1:
            return
        # if the input is at the min level
        elif self.is_min_level():
            self.min_insert()
        # if the input is at the max level
        else:
            self.max_insert()

    def max_insert(self):
        # if the number is inserted at the max level check if the parent is bigger
        if self.heap_arr[self.arr_len // 2] > self.heap_arr[self.arr_len]:
            # switch the numbers parent and child
            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]
            # update the min level from the parent position
            self.minify_up(self.arr_len // 2)
        # if the parent is smaller
        else:
            # update the max level from the current position
            self.maxity_up(self.arr_len)

    def min_insert(self):
        # if the number is inserted at the max level check if the parent is bigger
        if self.heap_arr[self.arr_len // 2] < self.heap_arr[self.arr_len]:
            # switch the numbers parent and child
            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]
            # update the min level from the parent position
            self.maxity_up(self.arr_len // 2)
        # if the parent is smaller
        else:
            # update the max level from the current position
            self.minify_up(self.arr_len)

    def max_output(self):
        # if the array is empty return 'None'
        if self.empty():
            return None
        # if the array has only 1 value remove root and return the value
        if self.arr_len == 1:
            self.arr_len -= 1
            return self.heap_arr[1]
        # set the output as the left child of root
        temp_index = 2
        # if the right child does exist and the right child is bigger than the left child
        if temp_index + 1 <= self.arr_len and self.heap_arr[temp_index] < self.heap_arr[temp_index + 1]:
            # change the output as the right child of the root
            temp_index += 1
        # swap the max num with the last index value
        self.heap_arr[self.arr_len], self.heap_arr[temp_index] = self.heap_arr[temp_index], self.heap_arr[self.arr_len]
        # remove the last node from the heap
        self.arr_len -= 1
        # update down the tree from the max node
        self.maxify_down(temp_index)
        # return the deleted node from the heap
        return self.heap_arr[self.arr_len + 1]

    def min_output(self):
        # if the array is empty return 'None'
        if self.empty():
            return None
        # swap the root(min num) to the last index value
        self.heap_arr[self.arr_len], self.heap_arr[1] = self.heap_arr[1], self.heap_arr[self.arr_len]
        # remove the last node from the heap
        self.arr_len -= 1
        # update down the tree from the root
        self.minify_down(1)
        # return the deleted node from the heap
        return self.heap_arr[self.arr_len + 1]

    # update down the heap
    def maxify_down(self, input_index):
        # while the node is not the leaf
        while input_index * 2 <= self.arr_len:
            # if the node has no grandchildren
            if input_index * 4 > self.arr_len:
                # set the compare node to the left child
                comp_index = input_index * 2
                # if there is no right child or the right child is bigger than the left one
                if comp_index + 1 <= self.arr_len and self.heap_arr[comp_index] < self.heap_arr[comp_index + 1]:
                    # change the compare node to the right child
                    comp_index += 1
                # if the compare node has a higher value than the current node
                if self.heap_arr[input_index] < self.heap_arr[comp_index]:
                    # swap the compare node and current node
                    self.heap_arr[input_index], self.heap_arr[comp_index] = self.heap_arr[comp_index], self.heap_arr[input_index]
                # end search because there are no more children for the compare node(from first if statement)
                return
            # else if there are any grandchildren
            # set compare node to the right child(this is set because we know that the left child will be smaller than
            # the grandchildren at the left, but the right node might not have any children)
            comp_index = input_index * 2 + 1
            # loop through the grandchildren
            for temp_index in range(input_index * 4, input_index * 4 + 4):
                # if there is the grandchild and the value is bigger than the value of the compare node
                if temp_index <= self.arr_len and self.heap_arr[comp_index] < self.heap_arr[temp_index]:
                    # change the compare node to the grandchild
                    comp_index = temp_index
            # if the compare node value is bigger than the current node value
            if self.heap_arr[input_index] < self.heap_arr[comp_index]:
                # swap the values
                self.heap_arr[input_index], self.heap_arr[comp_index] = self.heap_arr[comp_index], self.heap_arr[input_index]
            # if the swapped node is the child node
            if comp_index == input_index * 2 + 1:
                # end the value
                return
            # check if the parent node is smaller than the changed node
            if self.heap_arr[comp_index] < self.heap_arr[comp_index // 2]:
                # swap the nodes
                self.heap_arr[comp_index // 2], self.heap_arr[comp_index] = self.heap_arr[comp_index], self.heap_arr[comp_index // 2]
            # change the compare node to the current node
            input_index = comp_index

    # update down the heap
    def minify_down(self, input_index):
        # while the node is not the leaf
        while input_index * 2 <= self.arr_len:
            # if the node has no grandchildren
            if input_index * 4 > self.arr_len:
                # set the compare node to the left child
                comp_index = input_index * 2
                # if there is no right child or the right child is smaller than the left one
                if comp_index + 1 <= self.arr_len and self.heap_arr[comp_index] > self.heap_arr[comp_index + 1]:
                    # change the compare node to the right child
                    comp_index += 1
                # if the compare node has a smaller value than the current node
                if self.heap_arr[input_index] > self.heap_arr[comp_index]:
                    # swap the compare node and current node
                    self.heap_arr[input_index], self.heap_arr[comp_index] = self.heap_arr[comp_index], self.heap_arr[input_index]
                # end search because there are no more children for the compare node(from first if statement)
                return
            # else if there are any grandchildren
            # set compare node to the right child(this is set because we know that the left child will be bigger than
            # the grandchildren at the left, but the right node might not have any children)
            comp_index = input_index * 2 + 1
            # loop through the grandchildren
            for temp_index in range(input_index * 4, input_index * 4 + 4):
                # if there is the grandchild and the value is bigger than the value of the compare node
                if temp_index <= self.arr_len and self.heap_arr[comp_index] > self.heap_arr[temp_index]:
                    # change the compare node to the grandchild
                    comp_index = temp_index
            # if the compare node value is bigger than the current node value
            if self.heap_arr[input_index] > self.heap_arr[comp_index]:
                # swap the values
                self.heap_arr[input_index], self.heap_arr[comp_index] = self.heap_arr[comp_index], self.heap_arr[input_index]
            # check if the parent node is smaller than the changed node
            if comp_index == input_index * 2 + 1:
                # end the value
                return
            # check if the parent node is smaller than the changed node
            if self.heap_arr[comp_index] > self.heap_arr[comp_index // 2]:
                # swap the nodes
                self.heap_arr[comp_index // 2], self.heap_arr[comp_index] = self.heap_arr[comp_index], self.heap_arr[comp_index // 2]
            # change the compare node to the current node
            input_index = comp_index

    # update up the heap
    def maxity_up(self, input_index):
        # while the node has a grandfather
        while input_index // 4 > 0:
            # set the grandfather as the compare index
            comp_index = input_index // 4
            # if the grandfather is bigger than the current node
            if self.heap_arr[comp_index] >= self.heap_arr[input_index]:
                # end update
                break
            # if the current node is bigger swap the values
            self.heap_arr[comp_index], self.heap_arr[input_index] = self.heap_arr[input_index], self.heap_arr[comp_index]
            # update from the grandfather
            input_index = comp_index

    # update up the heap
    def minify_up(self, input_index):
        # set the grandfather as the compare index
        while input_index // 4 > 0:
            # set the grandfather as the compare index
            comp_index = input_index // 4
            # if the grandfather is smaller than the current node
            if self.heap_arr[comp_index] <= self.heap_arr[input_index]:
                # end update
                break
            # if the current node is smaller swap the values
            self.heap_arr[comp_index], self.heap_arr[input_index] = self.heap_arr[input_index], self.heap_arr[comp_index]
            # update from the grandfather
            input_index = comp_index

    # prints the array as output using recursion
    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 + "    ")

    # verifies if the heap is correct
    def verify(self, i=1, ismin=True, low=-100000, high=100000):
        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 ismin:
            low = val
        else:
            high = val
        self.verify(i * 2, not ismin, low, high)
        self.verify(i * 2 + 1, not ismin, low, high)

The print function and the verify functions are used for debugging and I think I will try to add this to all my code that has more than 2 functions to get a easier view of the error made.