data_structures.heap.heap_generic

Classes

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

Functions

test_heap(→ None)

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]