Package commons :: Module structs :: Class Heap

[frames] | no frames]

Class Heap

object --+    
         |    
 ListMixin --+
             |
            Heap

A list that maintains the heap invariant. http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/440673

TODO using things like pop() is unsafe! they rely on the unimplemented _get_element()

TODO things like popmin() produce poor error msgs (when empty)

Instance Methods

__init__(self, iterable=(), key=None)
x.__init__(...) initializes x; see x.__class__.__doc__ for signature source code

peek(self)

source code

push(self, item)
Push the item onto the heap.

source code

popmin(self)
Pop the smallest item off the heap

source code

replace(self, item)
Equivalent to "x = heap.popmin(); heap.push(); return x" but more efficient.

source code

pushpop(self, item)
Equivalent to "heap.push(); return heap.popmin()" but more efficient.

source code

iterpop(self)
Return a destructive iterator over the heap's elements.

source code

constructor(self, iterable)

source code

__len__(self)

source code

get_element(self, pos)

source code

__setitem__(self, pos, item)

source code

__delitem__(self, pos)

source code

source code

__nonzero__(self)

source code

__cmp__(self, other)

source code

__eq__(self, other)

source code

__ne__(self, other)

source code

count(self, item)

source code

append(self, item)
Push the item onto the heap.

source code

insert(self, pos, item)

source code

extend(self, other)

source code

sort(self)

source code

source code

_wrap(self, item)

source code

_unwrap(self, item)

source code

Inherited from ListMixin: __add__, __copy__, __deepcopy__, __getitem__, __hash__, __iadd__, __imul__, __mul__, __radd__, __repr__, __rmul__, __str__, index, pop, remove

Inherited from ListMixin (private): _fix_index, _tuple_from_slice

Inherited from object: __delattr__, __format__, __getattribute__, __new__, __reduce__, __reduce_ex__, __setattr__, __sizeof__, __subclasshook__

Properties

Inherited from object: __class__

Method Details

init(self, iterable=`()`, key=None)
(Constructor)

x.__init__(...) initializes x; see x.__class__.__doc__ for signature

Parameters:

iterable - An iterable over items to be added to the heap.
key - Specifies a function of one argument that is used to extract a comparison key from each heap element.

Overrides: object.__init__

iterpop(self)

Return a destructive iterator over the heap's elements.

Each time next is invoked, it pops the smallest item from the heap.

setitem(self, pos, item)
(Index assignment operator)

Overrides: ListMixin.__setitem__

delitem(self, pos)
(Index deletion operator)

Overrides: ListMixin.__delitem__

iter(self)

Overrides: ListMixin.__iter__

cmp(self, other)
(Comparison operator)

Overrides: ListMixin.__cmp__

count(self, item)

Overrides: ListMixin.count

append(self, item)

Push the item onto the heap.

Overrides: ListMixin.append

insert(self, pos, item)

Overrides: ListMixin.insert

extend(self, other)

Overrides: ListMixin.extend

sort(self)

Overrides: ListMixin.sort

reverse(self)

Overrides: ListMixin.reverse