What data structure to use for heap in python

Question

I was writing a custom heap implementation for Udacity course and needed a heap that would return a metric value for an element through both heap index and key of an element.

I have ended up with a list for a heap that contains tuples (Metric, Key).

But to get the right element via key I had to create a separate map and maintain it's validity for each change in the heap.

So in the end instead of having functions with two parameters like heapup(heap, i), I had to pass map to all the functions - heapup(heap, i, map).

I am wondering if there is a simpler way to do this through procedures, lists and dictionaries. Or Heap object will be required to hide the Map inside?

 def heapup(L, i, map):

    if i == 0: return i # we reached the top!
    if i >= len(L): return i
    if L[parent(i)] > L[i]:
       # print "going up"
        (L[i], L[parent(i)]) = (L[parent(i)], L[i])
        map[L[i][1]] = i
        map[L[parent(i)][1]] = parent(i)
        return up_heapify(L, parent(i), map)
    else:
     #   print "going down"
        if leaf(L,i): return i
        if one_child(L,i): return i # we could only come this way
        if L[i] > L[left(i)]: # compare with left child
            (L[i], L[left(i)]) = (L[left(i)], L[i])
            map[L[i][1]] = i
            map[L[left(i)][1]] = left(i)
            return left(i)
        if L[i] > L[right(i)]: # compare with right child
            (L[i], L[right(i)]) = (L[right(i)], L[i])
            map[L[i][1]] = i
            map[L[right(i)][1]] = right(i)
            return right(i)

I would like to get rid of map in that function but still be able to get items values from heap by their key which I now can do like this:

item = heap[map[key]]

For example:

if

L = [(3,'A'), (5, 'D'), (4, 'G') ...]

then

map = {'A':0, 'D':1, 'G': 2, ...}

so I can get a value of an element like this:

L[map['G']]

which will give me 4

I'm afraid I really don't understand what you're doing. What is map exactly? What does "Metric" mean in this context? Can you show the code you've created so far? — Blckknght
– Blckknght, Commented Jan 16, 2013 at 11:52
basically L consists of tuples (x,y) where x - is a metric, and y is a key of the element. As you can see I have to update map every time I change position of elements in the heap. that will allow me to get element from the heap by Key like this: heap[map[key]] — Bulat
– Bulat, Commented Jan 16, 2013 at 12:13
@Blckknght metric is some numeric value that is used to sort elements in the heap — Bulat
– Bulat, Commented Jan 16, 2013 at 12:14

wwwayne · Accepted Answer · 2013-05-06 17:56:43Z

3

Use heapq http://docs.python.org/2/library/heapq.html with description:

"This module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm."

answered May 6, 2013 at 17:56

wwwayne

1231 silver badge7 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

What data structure to use for heap in python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related