I made a min-max priority queue in python. I tested it using my example and had no problems, but the coding website(a site like leetcode) said that the output was wrong(Not an error)... Is there any problems / improvements I can make?
I think there is a import that I can make to make this part easier(I think), but I'm trying to get the concept right before importing it in the future.
class MaxMinHeap:
def __init__(self, max_len):
self.heap_arr = [0 for _ in range(max_len 1)]
self.arr_len = 0
# checks if heap is empty
def empty(self):
if self.arr_len == 0:
return True
return False
# checks if the level of the tree is an odd number or an even number
def is_min_level(self):
if math.floor(math.log2(self.arr_len)) % 2 == 1:
return False
return True
# inserts a number to the heap
def insert_num(self, input_num):
self.arr_len = 1
self.heap_arr[self.arr_len] = input_num
# if the array was empty, don't do any checks
if self.arr_len == 1:
return
# else if the array is at the min level of the tree
elif self.is_min_level():
self.min_insert()
else:
self.max_insert()
# when a number is added to the heap at the max level
def max_insert(self):
# if the child is bigger than the number
if self.heap_arr[self.arr_len // 2] > self.heap_arr[self.arr_len]:
# change the values
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]
# keep updating the values up the min tree
self.minify_up(self.arr_len // 2)
else:
# keep updating the values up the max tree
self.maxity_up(self.arr_len)
# when a number is added to the heap at the min level
def min_insert(self):
# if the child is smaller than the number
if self.heap_arr[self.arr_len // 2] < self.heap_arr[self.arr_len]:
# change the values
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]
# keep updating the values up the max tree
self.maxity_up(self.arr_len // 2)
else:
# keep updating the values up the min tree
self.minify_up(self.arr_len)
# when a max number is needed
def max_output(self):
if self.empty():
return -1
# if there is only one number(the first node is in the min level) return that node
if self.arr_len == 1:
self.arr_len -= 1
return self.heap_arr[1]
# else check the second and third node to get max num
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
# change with the last element
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
# go updating down the array
self.maxify_down(temp_index)
# print the max that was changed with the last element
return self.heap_arr[self.arr_len 1]
# when a min number is needed
def min_output(self):
if self.empty():
return -1
# change with the last element(the min number is always at index 1)
self.heap_arr[self.arr_len], self.heap_arr[1] = self.heap_arr[1], self.heap_arr[self.arr_len]
self.arr_len -= 1
# go updating down the array
self.minify_down(1)
# print the min that was changed with the last element
return self.heap_arr[self.arr_len 1]
# when an output is sent from the max level
def maxify_down(self, input_index):
# while the node has a child
while input_index * 2 <= self.arr_len:
# if there are no grandchild
if input_index * 4 > self.arr_len:
# check the child
comp_index = input_index * 2
if comp_index 1 == self.arr_len and self.heap_arr[comp_index] < self.heap_arr[comp_index]:
comp_index = 1
# if any of the child are bigger change values
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]
# end update
return
# else set the comparing element to its right child
# this is because the right child might have no child. Making this node have no guarantee that it is
# smaller than the grandchild
comp_index = input_index * 2 1
# loop through the grandchild list
for temp_index in range(input_index * 4, input_index * 4 4):
if temp_index 1 == self.arr_len and self.heap_arr[comp_index] < self.heap_arr[temp_index]:
comp_index = temp_index
# swap the max number with the index
self.heap_arr[input_index], self.heap_arr[comp_index] = self.heap_arr[comp_index], self.heap_arr[input_index]
# if the swaped index was the child one end update
if comp_index == input_index * 2 1:
return
# else check the parent of the node for any errors
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]
# set the index again and loop
input_index = comp_index
# when an output is sent from the max level
def minify_down(self, input_index):
# while the node has a child
while input_index * 2 <= self.arr_len:
# if there are no grandchild
if input_index * 4 > self.arr_len:
# check the child
comp_index = input_index * 2
if comp_index 1 == self.arr_len and self.heap_arr[comp_index] > self.heap_arr[comp_index]:
comp_index = 1
# if any of the parents are bigger change values
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]
# end update
return
# else set the comparing element to its right child
# this is because the right child might have no child. Making this node have no guarantee that it is
# bigger than the grandchild
comp_index = input_index * 2 1
# loop through the grandchild list
for temp_index in range(input_index * 4, input_index * 4 4):
if temp_index 1 == self.arr_len and self.heap_arr[comp_index] > self.heap_arr[temp_index]:
comp_index = temp_index
# swap the min number with the index
self.heap_arr[input_index], self.heap_arr[comp_index] = self.heap_arr[comp_index], self.heap_arr[input_index]
# if the swaped index was the child one end update
if comp_index == input_index * 2 1:
return
# else check the parent of the node for any errors
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]
# set the index again and loop
input_index = comp_index
# when input is in max level
def maxity_up(self, input_index):
# while the input has a grandfather
while input_index // 4 > 0:
# compare grandfather with input and if input is greater swap
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]
# update index and loop
input_index = comp_index
# when input is in min level
def minify_up(self, input_index):
# while the input has a grandfather
while input_index // 4 > 0:
# compare grandfather with input and if input is smaller swap
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]
# update index and loop
input_index = comp_index
The array used to store is heap_arr and the heap starts at index 1 to make the child and parent //2 and *2 each.
I tried to look into a research paper and tried to copy its psudocode to python, but got the same results. Working for my example but not for the site.
CodePudding user response：
Your minify_down (and maxity_down) methods have bugs. In fact, you could have found this quite easily as things already went wrong with just four values.
I'll first show a few steps you could have taken to debug this yourself:
Define a method that prints the heap in a human-readable "tree-view". Nothing complicated; just a 90° (counter-clockwise) rotated view where the root appears at the left and the tree extends to the right:
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 " ")Define a method that verifies the consistency of the heap, and if it is not, print the heap and throw an error:
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)Create some random input and feed those values to the heap, and after every call of
insertalso call the aboveverifymethod.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 wellIf the above test turns out well (it does), continue with adding
min_outputcalls in the testimport 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) breakThis test failed! Reducing the size of the
origlist to even just 4 values, it went wrong with a shuffledvalueslike [3,1,0,2]. A great candidate to then drill down further into what is causing the inconsistency (see further).You can continue with
max_outputtests in the same manner.Once you find which state leads to an inconsistent heap, start debugging with a debugger stepping through the code, inspecting names, ...etc
I can only urge to not give up on an issue that quickly: designing tests like above is actually not that hard, and it helps you identify problems in a reasonable time.
Conclusions
I found these issues in minify_down:
At several places you have
if .... == self.arr_len, which excludes cases where the test index is actually less than that limit, while those indexes should be allowed to pass that test too. So change to<=.There is a
self.heap_arr[comp_index] > self.heap_arr[comp_index]test, which obviously makes no sense. Intended wasself.heap_arr[comp_index] > self.heap_arr[comp_index 1]The condition
temp_index 1 == self.arr_lenshould not only be corrected to use<=(point 1), but should betemp_index <= self.arr_len, since your intention is to accessself.heap_arr[temp_index], notself.heap_arr[temp_index 1]Further down you perform a swap without checking that this swap is needed! So change that:
self.heap_arr[input_index], self.heap_arr[comp_index] = self.heap_arr[comp_index], self.heap_arr[input_index]to:
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]
With those changes the above test code will pass. Similar problems exist in maxify_down which you can correct along the same lines.