FibonacciHeap

FibonacciHeap#

class FibonacciHeap#

Bases: Container, Generic[_K, _V]

Fibonacci heap container data structure implementation. The heap property is maintained with respect to priority arguments.

__init__()#

Methods

__init__()

decrease_priority(node, new_priority)

Change priority of the given node and consolidate the heap in a way that the heap property is maintained.

extract_min_node()

Extract node associated with the minimum priority.

find(key)

Find node with the given key from the root list.

get_min_node()

Peek node associated with the minimum priority.

increment_n_ops([increment])

Convenience method to increment n_ops count of the given complexity object.

insert(key, priority)

Insert a given key associated with a comparable priority used to maintain the heap property of the keys.

insert_node(node)

Insert the given HeapNode object to the heap.

reset_n_ops()

Convenience method to reset n_ops count of the given complexity object.

Attributes

average_case_delete_time_complexity

rtype:

str

average_case_insert_time_complexity

rtype:

str

average_case_search_time_complexity

rtype:

str

best_case_delete_description

rtype:

str

best_case_delete_time_complexity

rtype:

str

best_case_insert_description

rtype:

str

best_case_insert_time_complexity

rtype:

str

best_case_search_description

rtype:

str

best_case_search_time_complexity

rtype:

str

is_empty

rtype:

bool

n_ops

rtype:

int

name

rtype:

str

space_complexity

rtype:

str

worst_case_delete_description

rtype:

str

worst_case_delete_time_complexity

rtype:

str

worst_case_insert_description

rtype:

str

worst_case_insert_time_complexity

rtype:

str

worst_case_search_description

rtype:

str

worst_case_search_time_complexity

rtype:

str
property average_case_delete_time_complexity: str#
Return type:

str

property average_case_insert_time_complexity: str#
Return type:

str

property average_case_search_time_complexity: str#
Return type:

str

property best_case_delete_description: str#
Return type:

str

property best_case_delete_time_complexity: str#
Return type:

str

property best_case_insert_description: str#
Return type:

str

property best_case_insert_time_complexity: str#
Return type:

str

property best_case_search_description: str#
Return type:

str

property best_case_search_time_complexity: str#
Return type:

str

decrease_priority(node, new_priority)#

Change priority of the given node and consolidate the heap in a way that the heap property is maintained.

Parameters:

  • node (HeapNode) – Node whose priority is to be decreased.

  • new_priority (int | float) – New priority for the given node.

Return type:

None

extract_min_node()#

Extract node associated with the minimum priority.

Returns:

min_priority_node – The heap node associated with the minimum priority or NoNode() object if the heap is empty.

Return type:

HeapNode | NoNode

find(key)#

Find node with the given key from the root list.

Parameters:

key (_K) – Searched-for key.

Returns:

node – Returns node with the given key or NoNode() object in case such node is not present.

Return type:

HeapNode | NoNode

get_min_node()#

Peek node associated with the minimum priority.

Returns:

min_priority_node – The heap node associated with the minimum priority or NoNode() object if the heap is empty.

Return type:

HeapNode | NoNode

increment_n_ops(increment=1)#

Convenience method to increment n_ops count of the given complexity object.

Return type:

None

insert(key, priority)#

Insert a given key associated with a comparable priority used to maintain the heap property of the keys.

Parameters:

  • key (_K) – Key to insert.

  • priority (_V) – Value to associate the key with. Used to compare the keys and maintain the heap property.

Returns:

heap_node – The inserted heap node.

Return type:

HeapNode

insert_node(node)#

Insert the given HeapNode object to the heap.

Parameters:

node (HeapNode) – The heap node to be inserted.

Returns:

heap_node – The inserted heap node.

Return type:

HeapNode

property is_empty: bool#
Return type:

bool

property n_ops: int#
Return type:

int

property name: str#
Return type:

str

reset_n_ops()#

Convenience method to reset n_ops count of the given complexity object.

Return type:

None

property space_complexity: str#
Return type:

str

property worst_case_delete_description: str#
Return type:

str

property worst_case_delete_time_complexity: str#
Return type:

str

property worst_case_insert_description: str#
Return type:

str

property worst_case_insert_time_complexity: str#
Return type:

str

property worst_case_search_description: str#
Return type:

str

property worst_case_search_time_complexity: str#
Return type:

str