heap
This library is considered production ready.
from pykit import heap
h = heap.RefHeap([5, 1, 4, 2, 3])
while h.size > 0:
print h.pop(),
print
# 1 2 3 4 5In this module RefHeap is a binary min heap implemented with reference:
a parent has two references to two children and a child has a parent reference to
its parent.
RefHeap is not thread safe.
Why do we need it since python provides with module heapq.
-
heapqdoes not support changing heap node key, after heap created. But sometimes we need to adjust heap node key to bubble up a node or push down a node. -
heapqdoes not support locating the index by an object reference in its underlying list. Thus if a node changed, it is not possible to find it inO(1)orO(log(n))time(because the underlying list is not sorted).
RefHeap allows to have multiple same primitive type object in it but does NOT
allow to have two same non-primitive type objects in it.
Thus:
h = heap.RefHeap()
x = []
h.push(x)
h.push(x) # ValueError
h.push([]) # OKIndicates that an non-primitive object is already in a heap when push().
syntax:
Duplicate()
Indicates that a heap is empty when get().
syntax:
Empty()
Indicates that an object is not found in a heap when sift() or remove().
syntax:
NotFound()
Node is a node in heap.
It is a sub class of list and Node[0], Node[1] are left and right child in a
heap.
syntax:
Node(userdata)
arguments:
userdata: user data.
__lt__ let two Node can be compared with operator <.
It returns True or False.
A heap needs only a less than operation to work.
syntax:
Node.__lt__(b)
arguments:
b: is anotherNodeinstance.
return:
True or False
It returns the smaller child.
A None child is never a smaller one.
min_child is used when heap moves a node downwards.
syntax:
Node.min_child()
return:
a smaller left or right child, which is a Node instance, or None if both
children are None.
It is a wrapper class to convert a primitive type object to a reference object. A user does not need to use this class directly.
syntax:
Primitive(obj)
arguments:
obj: a primitive type object such asint,longorstretc.
return:
Primitive instance.
Min-heap implemented with reference instead of a list as underlying storage.
syntax:
RefHeap(iterable)
arguments:
iterable: specifies the items to push to heap after initialized.
Return the minimal object, but does not remove it.
If a heap is empty an heap.Empty error is raised.
syntax:
RefHeap.get()
return: the minimal object.
Remove and return the minimal object in the heap(the root).
If a heap is empty an heap.Empty error is raised.
syntax:
RefHeap.pop()
return: the minimal object.
Pops all item and returns them in a list.
syntax:
RefHeap.pop_all(map=lambda x:x)
arguments:
map: specifies what to do on each popped item before returning them. By default it islambda x:x, which does nothing.
return: a list of all item in heap.
Push an object into a heap.
syntax:
RefHeap.push(obj)
arguments:
obj: is any type object. A primitive type object is wrapped with Primitive() internally. But it does not affect an end user at all.
return: Nothing
Remove a reference type object from heap.
syntax:
RefHeap.remove(obj)
arguments:
obj: is a previously added object. Ifobjdoes not present in this heap,KeyErrorraises.
return: the object being removed.
Adjust position of an object in heap when the object changed.
Synopsis:
a, b = [1], [2]
h = heap.RefHeap([a, b])
h.get() # a=[1]
a[0] = 3
h.sift(a) # a becomes greater and is moved downwards
h.get() # b=[2]
b[0] = 5
h.sift(b) # b becomes greater and is moved downwards
h.get() # a=[3]syntax:
RefHeap.sift(obj)
arguments:
obj: must be an object that is already in this heap. Primitive object does not supportsift(), because it is impossible to change its state without changing itself.
return: Nothing
Zhang Yanpo (张炎泼) [email protected]
The MIT License (MIT)
Copyright (c) 2015 Zhang Yanpo (张炎泼) [email protected]