Classes¶

Functions¶

Module Contents¶

class data_structures.heap.heap_generic.Heap(key: collections.abc.Callable | None = None)¶

A generic Heap class, can be used as min or max by passing the key function accordingly.

_cmp(i: int, j: int) → bool¶

Compares the two items using default comparison

_get_valid_parent(i: int) → int¶

Returns index of valid parent as per desired ordering among given index and both it’s children

_heapify_down(index: int) → None¶

Fixes the heap in downward direction of given index

_heapify_up(index: int) → None¶

Fixes the heap in upward direction of given index

_left(i: int) → int | None¶

Returns left-child-index of given index if exists else None

_parent(i: int) → int | None¶

Returns parent index of given index if exists else None

_right(i: int) → int | None¶

Returns right-child-index of given index if exists else None

_swap(i: int, j: int) → None¶

Performs changes required for swapping two elements in the heap

delete_item(item: int) → None¶

Deletes given item from heap if present

extract_top() → tuple | None¶

Return top item tuple (Calculated value, item) from heap and removes it as well if present

get_top() → tuple | None¶

Returns top item tuple (Calculated value, item) from heap if present

insert_item(item: int, item_value: int) → None¶

Inserts given item with given value in heap

update_item(item: int, item_value: int) → None¶

Updates given item value in heap if present

arr: list = []¶

key¶

pos_map: dict¶

size = 0¶

data_structures.heap.heap_generic.test_heap() → None¶

>>> h = Heap()  # Max-heap
>>> h.insert_item(5, 34)
>>> h.insert_item(6, 31)
>>> h.insert_item(7, 37)
>>> h.get_top()
[7, 37]
>>> h.extract_top()
[7, 37]
>>> h.extract_top()
[5, 34]
>>> h.extract_top()
[6, 31]
>>> h = Heap(key=lambda x: -x)  # Min heap
>>> h.insert_item(5, 34)
>>> h.insert_item(6, 31)
>>> h.insert_item(7, 37)
>>> h.get_top()
[6, -31]
>>> h.extract_top()
[6, -31]
>>> h.extract_top()
[5, -34]
>>> h.extract_top()
[7, -37]
>>> h.insert_item(8, 45)
>>> h.insert_item(9, 40)
>>> h.insert_item(10, 50)
>>> h.get_top()
[9, -40]
>>> h.update_item(10, 30)
>>> h.get_top()
[10, -30]
>>> h.delete_item(10)
>>> h.get_top()
[9, -40]