Obtaining process count through MaxHeap gives incorrect output

Question

I'm working on a feature that requires a queue for its implementation. The queue contains the priorities of some processes. An element from the queue can be deleted only if it is the maximum element of the queue. If it's not, the queue needs to be rotated until we get the maximum element at the front end. If there are more than one elements having the maximum priority, the one nearest to the front end of the queue will be deleted first. For determining the maximum element, I'm using a MaxHeap as a helper data structure as it will help mw to do so at minimum cost.

A particular element needs to be deleted from the queue, and I need to count the number of elements that needed to be deleted (including that element). This represents the number of processes that were executed before that specific process is initiated.

Let me illustrate this with the help of some examples:

Example 1 Consider the queue [2, 2, 2, 2, 4]. The element at index 3 needs to be deleted. The successive steps are shown below:

[2, 2, 2, '2', 4]
[2, 2, '2', 4, 2]
[2, '2', 4, 2, 2]
['2', 4, 2, 2, 2]
[4, 2, 2, 2, '2']    # 4 is the maximum element, and therefore it can be deleted
[2, 2, 2, '2']       # 2 is the maximum element, and therefore it can be deleted
[2, 2, '2']
[2, '2']
['2']
[]

In total, 5 elements needed to be removed (this includes the desired element).

Example 2 Consider the queue [2, 3, 2, 2, 4]. The element at index 3 needs to be deleted. The successive steps are shown below:

[2, 3, 2, '2', 4]
[3, 2, '2', 4, 2]
[2, '2', 4, 2, 3]
['2', 4, 2, 3, 2]
[4, 2, 3, 2, '2']    # 4 is the maximum element, and therefore it can be deleted
[2, 3, 2, '2']       
[3, 2, '2', 2]       # 3 is the maximum element, and therefore it can be deleted
[2, '2', 2]          # 2 is the maximum element, and therefore it can be deleted
['2', 2]
[2]

In total, 4 elements needed to be removed (this includes the desired element).

I have implemented this as follows:

from collections import deque
import heapq

# n = length of array; k = index of the element that needs to be deleted
def processCount(arr: list, n: int, k: int) -> int:
    count = 0
    myPriority = arr[k]
    
    # Push the priorities into a queue
    q = deque()
    
    for i in arr:
        q.append(i)
    
    # Heapify the array      
    heapq._heapify_max(arr)
    
    # If the first element in the queue has the greatest priority, remove it from the queue and increment 'count'.
    # Otherwise, move it to the end of the queue.

    while True:
        if (priority := q[0]) == arr[0]:
            q.popleft()
            heapq._heappop_max(arr)
            count += 1
            
            if priority is myPriority:
                break
            
        else:
            q.append(q.popleft())

    return count

But this is producing incorrect output. For the above examples, it returns '2' and '3' respectively which is unexpected. I think that I am not able to determine the correct element using the line if priority is myPriority:. Where am I going wrong?

score 0 · Accepted Answer · answered Jul 23 '23 at 20:38

The problem is with this statement:

if priority is myPriority:

This will identify the value, but not which occurrence of that value. Your first example has several occurrences of 2 in the input, and the first time a two is encountered when all greater values have already been removed, your code "guesses" that this 2 is the one that was at index k, but there is no reason why this would be the case.

The solution is to also store the original indexes in the deque. That way you can verify that the extracted value really is the one that originally occurred at index k.

Here is the modified code:

def processCount(arr: list, n: int, k: int) -> int:
    count = 0    
    # Fill the queue with tuples (value, index)
    q = deque((value, i) for i, value in enumerate(arr))
    
    heapq._heapify_max(arr)
    
    while True:
        priority, idx = q.popleft()
        if priority == arr[0]:
            heapq._heappop_max(arr)
            count += 1
            if idx == k:  # compare by index
                break
        else:
            q.append((priority, idx))
    return count

Using 'is' operator, I wanted to check whether it was referring to the same object. But unfortunately, that didn't work. — RedHat, Jul 24 '23 at 02:24
Correct, that doesn't reliably work, as Python will in some cases use the same object for the same integers. [See here](https://stackoverflow.com/questions/306313/is-operator-behaves-unexpectedly-with-integers). — trincot, Jul 24 '23 at 04:59

Obtaining process count through MaxHeap gives incorrect output

1 Answers1