Heaps

class pydatastructs.BinaryHeap(elements=None, heap_property='min')

Represents Binary Heap.

Parameters

  • elements (list, tuple) – Optional, by default ‘None’. List/tuple of initial elements in Heap.

  • heap_property (str) – If the key stored in each node is either greater than or equal to the keys in the node’s children then pass ‘max’. If the key stored in each node is either less than or equal to the keys in the node’s children then pass ‘min’. By default, the heap property is set to ‘min’.

Examples

>>> from pydatastructs.trees.heaps import BinaryHeap
>>> min_heap = BinaryHeap(heap_property="min")
>>> min_heap.insert(1, 1)
>>> min_heap.insert(5, 5)
>>> min_heap.insert(7, 7)
>>> min_heap.extract().key
1
>>> min_heap.insert(4, 4)
>>> min_heap.extract().key
4

>>> max_heap = BinaryHeap(heap_property='max')
>>> max_heap.insert(1, 1)
>>> max_heap.insert(5, 5)
>>> max_heap.insert(7, 7)
>>> max_heap.extract().key
7
>>> max_heap.insert(6, 6)
>>> max_heap.extract().key
6

References

1

https://en.m.wikipedia.org/wiki/Binary_heap

heap
d
heap_property
__module__ = 'pydatastructs.trees.heaps'
class pydatastructs.TernaryHeap(elements=None, heap_property='min')

Represents Ternary Heap.

Parameters

  • elements (list, tuple) – Optional, by default ‘None’. List/tuple of initial elements in Heap.

  • heap_property (str) – If the key stored in each node is either greater than or equal to the keys in the node’s children then pass ‘max’. If the key stored in each node is either less than or equal to the keys in the node’s children then pass ‘min’. By default, the heap property is set to ‘min’.

Examples

>>> from pydatastructs.trees.heaps import TernaryHeap
>>> min_heap = TernaryHeap(heap_property="min")
>>> min_heap.insert(1, 1)
>>> min_heap.insert(5, 5)
>>> min_heap.insert(7, 7)
>>> min_heap.insert(3, 3)
>>> min_heap.extract().key
1
>>> min_heap.insert(4, 4)
>>> min_heap.extract().key
3

>>> max_heap = TernaryHeap(heap_property='max')
>>> max_heap.insert(1, 1)
>>> max_heap.insert(5, 5)
>>> max_heap.insert(7, 7)
>>> min_heap.insert(3, 3)
>>> max_heap.extract().key
7
>>> max_heap.insert(6, 6)
>>> max_heap.extract().key
6

References

1

https://en.wikipedia.org/wiki/D-ary_heap

2

https://ece.uwaterloo.ca/~dwharder/aads/Algorithms/d-ary_heaps/Ternary_heaps/

heap
d
heap_property
__module__ = 'pydatastructs.trees.heaps'
class pydatastructs.DHeap(elements=None, heap_property='min', d=4)

Represents D-ary Heap.

Parameters

elements (list, tuple, Array) – Optional, by default ‘None’. list/tuple/Array of initial TreeNode in Heap.

heap_propertystr

If the key stored in each node is either greater than or equal to the keys in the node’s children then pass ‘max’. If the key stored in each node is either less than or equal to the keys in the node’s children then pass ‘min’. By default, the heap property is set to ‘min’.

Examples

>>> from pydatastructs.trees.heaps import DHeap
>>> min_heap = DHeap(heap_property="min", d=3)
>>> min_heap.insert(1, 1)
>>> min_heap.insert(5, 5)
>>> min_heap.insert(7, 7)
>>> min_heap.extract().key
1
>>> min_heap.insert(4, 4)
>>> min_heap.extract().key
4

>>> max_heap = DHeap(heap_property='max', d=2)
>>> max_heap.insert(1, 1)
>>> max_heap.insert(5, 5)
>>> max_heap.insert(7, 7)
>>> max_heap.extract().key
7
>>> max_heap.insert(6, 6)
>>> max_heap.extract().key
6

References

1

https://en.wikipedia.org/wiki/D-ary_heap

insert(key, data=None)

Insert a new element to the heap according to heap property.

Parameters

  • key – The key for comparison.

  • data – The data to be inserted.

Returns

Return type

None

extract()

Extract root element of the Heap.

Returns

  • root_element (TreeNode) – The TreeNode at the root of the heap, if the heap is not empty.

  • None – If the heap is empty.

__str__()

Return str(self).

property is_empty

Checks if the heap is empty.

heap
d
heap_property
__module__ = 'pydatastructs.trees.heaps'
class pydatastructs.BinomialHeap(root_list=None)

Represents binomial heap.

Parameters

root_list (list/tuple/Array) – By default, [] The list of BinomialTree object references in sorted order.

Examples

>>> from pydatastructs import BinomialHeap
>>> b = BinomialHeap()
>>> b.insert(1, 1)
>>> b.insert(2, 2)
>>> b.find_minimum().key
1
>>> b.find_minimum().children[0].key
2

References

1

https://en.wikipedia.org/wiki/Binomial_heap

merge_tree(tree1, tree2)

Merges two BinomialTree objects.

Parameters
merge(other_heap)

Merges current binomial heap with the given binomial heap.

Parameters

other_heap (BinomialHeap) –

insert(key, data=None)

Inserts new node with the given key and data.

key

The key of the node which can be operated upon by relational operators.

data

The data to be stored in the new node.

find_minimum(**kwargs)

Finds the node with the minimum key.

Returns

min_node

Return type

BinomialTreeNode

delete_minimum()

Deletes the node with minimum key.

property is_empty
decrease_key(node, new_key)

Decreases the key of the given node.

Parameters

  • node (BinomialTreeNode) – The node whose key is to be reduced.

  • new_key – The new key of the given node, should be less than the current key.

delete(node)

Deletes the given node.

Parameters

node (BinomialTreeNode) – The node which is to be deleted.

root_list
__module__ = 'pydatastructs.trees.heaps'