The max value in the max heap isn't the correct value

Question

The program takes as input:

(string)’yyyy-mm-dd’, (int)sensor id, (int)covid level.

The expected output is: yyyy-mm-dd,covid level.

Input: 2022−09−08, 23, 371; 2022−09−08, 2, 3171; 2022−09−08, 12, 43; 2021−03−21, 4, 129

Output: 2022 −09 −08, 3171

I have provided my code below. My output doesn't work correctly when the input is large. I think the heapify got screwed up somewhere. Here is my code:

import sys

class MaxHeap:

def __init__(self, maxsize):
    self.maxsize = maxsize
    self.size = 0
    self.Heap = [0] * (self.maxsize + 1)
    self.Heap[0] = ('1.1.1977', sys.maxsize)              
    self.FRONT = 1

# Function to return the position of parent for the node currently at pos
def parent(self, pos):
     
    return pos // 2

# Function to return the position of the left child for the node currently at pos
def leftChild(self, pos):
     
    return 2 * pos

# Function to return the position of the right child for the node currently at pos
def rightChild(self, pos):
     
    return (2 * pos) + 1

# Function that returns true if the passed node is a leaf node
def isLeaf(self, pos):
     
    if pos >= (self.size//2) and pos <= self.size:
        return True
    return False

# Function to swap two nodes of the heap
def swap(self, fpos, spos):
     
    self.Heap[fpos], self.Heap[spos] = (self.Heap[spos], self.Heap[fpos])

# Function to heapify the node at pos
def maxHeapify(self, pos):
    
    # If the node is a non-leaf node and smaller
    # than any of its child
    if not self.isLeaf(pos):
        if (self.Heap[pos] < self.Heap[self.leftChild(pos)] or self.Heap[pos] < self.Heap[self.rightChild(pos)]):

            # Swap with the left child and heapify
            # the left child
            if (self.Heap[self.leftChild(pos)] > self.Heap[self.rightChild(pos)]):
                self.swap(pos, self.leftChild(pos))
                self.maxHeapify(self.leftChild(pos))

            # Swap with the right child and heapify
            # the right child
            else:
                self.swap(pos, self.rightChild(pos))
                self.maxHeapify(self.rightChild(pos))

# Function to insert a node into the heap
def insert(self, element):
     
    if self.size >= self.maxsize:
        return
    self.size += 1
    self.Heap[self.size] = element

    current = self.size

    while (str(self.Heap[current]) >
           str(self.Heap[self.parent(current)])):
        self.swap(current, self.parent(current))
        current = self.parent(current)

# Function to print the contents of the heap
def Print(self):
     
    for i in range(1, (self.size // 2) + 1):
        print("PARENT : " + str(self.Heap[i]) +
              "LEFT CHILD : " + str(self.Heap[2 * i]) +
              "RIGHT CHILD : " + str(self.Heap[(2 * i) + 1]))

# Function to remove and return the maximum
# element from the heap
def extractMax(self):

    ext = self.Heap[self.FRONT]
    self.Heap[self.FRONT] = self.Heap[self.size]
    self.size -= 1
    self.maxHeapify(self.FRONT)
     
    return ext


# Driver Code
if __name__ == "__main__":
   input = input()
   input = input.split(";")
dates = []
values = []
for d in input:
    date = d.split(',', 2)
    dates.append(date[0])
    values.append(date[2])

values = [int(x) for x in values]
tuples = list(zip(dates, values))
heap = MaxHeap(len(tuples) + 1)
for t in tuples:
    heap.insert(t)

max_heap = heap.extractMax()                                

My output for this input:

2023-04-19,9132,438804;2022-04-04,4535,316300;2021-05-24,3079,101563;2021-04-29,7378,18098;2023-04-13,7790,15956;2023-08-16,4086,190312;2022-05-07,6779,749569;2021-07-06,9852,574634;2022-09-23,934,112247;2022-01-31,8810,405090;2020-12-22,7342,381167;2021-07-17,711,993694;2022-10-10,409,522123;2021-03-31,3392,797680;2021-04-19,5982,842608;2023-05-01,2400,487512;2021-09-20,945,842398;2020-01-18,9269,104747;2020-07-26,6781,596629;2021-08-02,8162,360261;2019-09-30,1919,637237;2022-12-06,1914,81688;2022-07-13,603,676273;2022-05-27,950,185217;2022-04-25,3386,595046;2020-04-24,4442,779015;2020-11-10,2985,366614;2021-09-08,9104,797580;2021-07-09,4635,890720;2023-01-12,7299,514824;2023-08-26,5111,261446;2022-11-30,9761,664774;2023-02-27,5702,101817;2022-10-30,7463,552832;2020-05-26,8611,635344;2020-01-10,1154,912487;2021-08-03,1751,481369;2020-09-23,5469,696646;2021-11-07,6329,836149;2022-05-18,8444,621113;2021-09-15,5352,128613;2023-07-01,6008,393441;2022-10-11,2598,346254;2019-12-18,1956,666816;2020-10-01,5303,705215;2022-12-06,3580,86464;2021-08-19,655,503907;2020-07-27,9448,414938;2021-05-29,1887,10723;2023-05-30,3787,753166;2021-04-25,615,155563;2022-07-06,5024,504939;2020-07-10,9029,980440;2020-08-21,6138,862944;2020-07-14,2660,648708;2023-05-13,5482,313792;2020-01-21,3730,401475;2022-01-23,1701,569155;2021-05-10,6324,361397;2020-07-09,7832,553689;2020-01-08,7655,261610;2022-06-23,6407,300140;2020-02-28,4394,120407;2022-01-15,8922,372324;2020-06-01,2544,903305;2021-07-18,4792,571747;2020-08-29,8251,72353;2019-09-09,4894,886404;2021-06-27,473,446021;2021-03-12,7044,711193;2020-01-11,9889,188949;2021-07-11,8809,667911;2021-04-16,7349,103581;2021-08-03,966,328995;2023-07-08,4301,48755;2022-03-20,7034,228660;2020-09-08,4874,860249;2022-03-18,3717,107146;2023-05-01,3596,582978;2022-08-02,2420,2761;2022-09-10,3728,672878;2019-12-15,2545,251375;2022-10-26,1526,376646;2021-08-29,6201,158015;2022-04-02,972,843280;2020-12-01,1891,424955;2022-10-24,7948,563497;2021-07-16,7922,901972;2023-02-01,464,870315;2020-03-29,3974,512011;2023-02-04,915,131894;2023-06-02,1889,971126;2022-01-19,7300,245778;2020-01-18,5677,154759;2023-01-20,1373,152443;2022-09-29,2471,417724;2022-09-09,2260,504994;2023-08-30,9896,425287;2021-07-16,3388,607646;2021-03-13,4559,207877;2022-09-08,42,114573

is: 2023-08-30,425287

It's supposed to be: 2021-07-17,993694

Could someone please help me? I've fixated on this question for way too long now.

Answer 1

The problem is your sorting. You are sorting based on date. If you change your loop inside insert to this, you'll sort by the numeric value and things work fine:

        while self.Heap[current][1] > self.Heap[self.parent(current)][1]: