CODEWITHSUNDEEP
pythondata-structuresheap
Bulat
Bulat

Reputation: 6969

What data structure to use for heap in python

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

Upvotes: 1

Views: 2447

Answers (1)

wwwayne
wwwayne

Reputation: 123

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."

Upvotes: 3

Related Questions