3

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?

Jonathan
  • 8,453
  • 9
  • 51
  • 74
  • "Position" as in what, the number of elements greater than it? Or the index in the physical list representing the heap? Or something else? Why are you trying to do this, anyway? Do you need a decrease-key operation? Or are you trying to treat a heap as if it's a fully-sorted data structure? – user2357112 Apr 02 '18 at 22:38
  • @user2357112 I want to know the number of elements that are greater than the given number. In the case of `39` there are 6, elements that are greater than `39`, so `39` would be in the 7th position or rank if you will. The reason I want to know is that it would be useful to know at what position an element is if you're using the heap in a priority queue. – Jonathan Apr 02 '18 at 22:44
  • 1
    Sedgewick books `Algorithms in ...` describe a kind of indirect heap that uses indexes of initial array (without reordering it) and allows operation 'change key' (used in Dijkstra algo) by index. For reference - `class PQi` in Java code here: http://www.cs.princeton.edu/~rs/Algs3.java1-4/code.txt – MBo Apr 03 '18 at 07:58

3 Answers3

9

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.

user2357112
  • 260,549
  • 28
  • 431
  • 505
0

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!

BPL
  • 9,632
  • 9
  • 59
  • 117
  • Yeah, that solves the problem alright, but in terms of big O complexity it's not a very good way of doing it. I'm wondering if there is a better way of solving the problem. – Jonathan Apr 02 '18 at 22:31
0

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.

Prune
  • 76,765
  • 14
  • 60
  • 81