data_structures.heap.binomial_heap

Binomial Heap Reference: Advanced Data Structures, Peter Brass

Classes

BinomialHeap

Min-oriented priority queue implemented with the Binomial Heap data

Node

Node in a doubly-linked binomial tree, containing:

Module Contents

class data_structures.heap.binomial_heap.BinomialHeap(bottom_root=None, min_node=None, heap_size=0)

Min-oriented priority queue implemented with the Binomial Heap data structure implemented with the BinomialHeap class. It supports:

  • Insert element in a heap with n elements: Guaranteed logn, amoratized 1

  • Merge (meld) heaps of size m and n: O(logn + logm)

  • Delete Min: O(logn)

  • Peek (return min without deleting it): O(1)

Example:

Create a random permutation of 30 integers to be inserted and 19 of them deleted >>> import numpy as np >>> permutation = np.random.permutation(list(range(30)))

Create a Heap and insert the 30 integers __init__() test >>> first_heap = BinomialHeap()

30 inserts - insert() test >>> for number in permutation: … first_heap.insert(number)

Size test >>> first_heap.size 30

Deleting - delete() test >>> [int(first_heap.delete_min()) for _ in range(20)] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

Create a new Heap >>> second_heap = BinomialHeap() >>> vals = [17, 20, 31, 34] >>> for value in vals: … second_heap.insert(value)

The heap should have the following structure:

17

/

# 31

/

20 34

/ /

# # # #

preOrder() test >>> “ “.join(str(x) for x in second_heap.pre_order()) “(17, 0) (‘#’, 1) (31, 1) (20, 2) (‘#’, 3) (‘#’, 3) (34, 2) (‘#’, 3) (‘#’, 3)”

printing Heap - __str__() test >>> print(second_heap) 17 -# -31 –20 —# —# –34 —# —#

mergeHeaps() test >>> >>> merged = second_heap.merge_heaps(first_heap) >>> merged.peek() 17

values in merged heap; (merge is inplace) >>> results = [] >>> while not first_heap.is_empty(): … results.append(int(first_heap.delete_min())) >>> results [17, 20, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 31, 34]

__str__()

Overwriting str for a pre-order print of nodes in heap; Performance is poor, so use only for small examples

__traversal(curr_node, preorder, level=0)

Pre-order traversal of nodes

delete_min()

delete min element and return it

insert(val)

insert a value in the heap

is_empty()
merge_heaps(other)

In-place merge of two binomial heaps. Both of them become the resulting merged heap

peek()

return min element without deleting it

pre_order()

Returns the Pre-order representation of the heap including values of nodes plus their level distance from the root; Empty nodes appear as #

bottom_root
min_node
size
class data_structures.heap.binomial_heap.Node(val)
Node in a doubly-linked binomial tree, containing:

  • value

  • size of left subtree

  • link to left, right and parent nodes

merge_trees(other)

In-place merge of two binomial trees of equal size. Returns the root of the resulting tree

left = None
left_tree_size = 0
parent = None
right = None
val