Python program to find Largest Derangement of Sequence in Heap

In this tutorial, we are going to find the largest Derangement of Sequence using the heap data structure in Python. We will be given a sequence S of length n. The Derangement means the shuffling of items from its original position in the sequence. The largest Derangement can be obtained by shifting the maximum element of the remaining sequence to the first position and so on.

Using Heap in Python

The default heap in python “heapq” library is min-heap. The insertion and deletion take O(logn) time complexity. But it is beneficial to us as we get the maximum heap build in O(nlogn) time complexity. Rather than using the naive approach of traversing the sequence and finding the maximum in the remaining sequence which takes O(n^2) time complexity.

Here we have to use a little trick to use Min Heap as Max – Heap. We multiply each element by -1 and then insert them in heap. When popping elements multiply then with -1 and get the respective element.

nums = [4,5,3,9,1,6]
pq = []
heapify(pq)
for i in range(len(nums)):
    heappush(pq, -1* nums[i])

// pq = [-9, -6, -5, -4, -3, -1]

for i in range(len(nums)):
    print(-1 * heappop(pq), end = ' ')

// output = 9 6 5 4 3 2 1

We need to consider the possibility that derangementSequence[ n – 1 ] = sequence[ n – 1 ] in case of decresing sequence is given.

Find Largest Derangement of Sequence in Heap in Python

Let us move to code in Python.

from heapq import heappop, heappush, heapify 

n = 7
sequence = [11,80,62,88,2,70,13]
derangedSeq = []
pq = []
heapify(pq)

for i in range(n):
    heappush(pq, -1 * sequence[i])

for curr in range(n):
    x = heappop(pq) * -1
    if (curr+1 == n or x != sequence[curr]):
        derangedSeq.append(x)
    else:
        y = heappop(pq) * -1   # if the largest element to be placed is at curr position
        derangedSeq.append(y)  # we get the next largest element from heap
        heappush(pq, -1 * x)


# Swapping the last two elements if the sequence is in descending order 
if (derangedSeq[n-1] == sequence[n-1]) :
    derangedSeq[n-1] , derangedSeq[n-2] = derangedSeq[n-2], derangedSeq[n-1]

print("Largest Derangement Sequence");
for i in range(n):
    print(derangedSeq[i], end = " ")
Input :
sequence = [11,80,62,88,2,70,13]
Output :
Largest Derangement Sequence
88 70 80 62 13 11 2

In the code above, we have simply created a Priority Queue(Max Heap) in Python and pushed all elements of the given sequence to it. Then the elements in the priority_queue are sorted in decreasing order. We just pop elements one by one and check that the position of this element we popped is not the same as in the given sequence. If the position is the same, we pop the next element in PQ and put it in the derangedSeq and push the earlier popped element back because now it will not match the position in the given sequence ever and can be pushed in the next iteration.

In the end, we check if the end elements of the given sequence and derangedSeq are equal or not. If equal, then we swap the last two elements in the deranged sequence.

If any doubts comment below.

Leave a Reply