CODEWITHSUNDEEP
pythonalgorithm
Jonathan
Jonathan

Reputation: 8901

Find the position of an element in a heap

Consider the following list of elements.

h = [38, 203, 1, 45, 39, 10, 34, 90, 10, 2, 100, 1]

If make this into an array based heap it will look in the following way. 

import heapq

heapq.heapify(h)
# now we have a heap that looks like this
# [1, 2, 1, 10, 39, 10, 34, 90, 45, 203, 100, 38]

What is the best way of finding out the position of 39 in this heap?

One way of finding out would be to pop items from the heap until it returns 39, that way we know its position if we keep track of the number of times we popped an item from the heap. However, that's not very efficient as we modify the heap itself.

Is there a better way to solve the problem?

Upvotes: 3

Views: 8382

Answers (3)

user2357112
user2357112

Reputation: 281949

From the clarifications in the comments, it seems you want to treat a heap as a fully-sorted data structure, and find the number of elements less than or greater than a specific element.

Heaps are not designed to support this operation. If you want to do this kind of thing, you should use a data structure that is designed for it. For example, sortedcontainers.SortedList:

import sortedcontainers

l = sortedcontainers.SortedList([38, 203, 1, 45, 39, 10, 34, 90, 10, 2, 100, 1])

index = l.index(39)

If you really want to use a heap anyway, you can run a greedy search of the heap and stop when you hit the item you're looking for. This will be very expensive for low-priority items; at worst, it will have the time complexity of a full sort, with a worse constant factor.

Upvotes: 9

Prune
Prune

Reputation: 77900

From the data you've given, I think this turns out to be simple arithmetic. You need the index of 39 counting backwards, right?

idx = len(h) - h.index(39) - 1

This results in the proper index for a 0-based count from the "right" end of the heap.

Upvotes: 0

BPL
BPL

Reputation: 9863

In case you want to keep heap, maybe something like this will do:

ordered = []
temp = heap[:]
while temp:
    ordered.append(heapq.heappop(temp))

print(ordered.index(39))

If that's not the case, maybe using sort will suit you better:

heap.sort()
print(heap.index(39))

Docs says:

These two make it possible to view the heap as a regular Python list without surprises: heap[0] is the smallest item, and heap.sort() maintains the heap invariant!

Upvotes: 0

Related Questions