dsa.heap module
Module containing heap (max heap), min heap and priority queue classes.
- class dsa.heap.Heap
Bases:
objectA max heap implementation.
- count()
Return the number of items in the heap.
- Return type:
int- Returns:
The number of items in the heap.
- enumerate()
Return the enumeration of a heap.
- Returns:
Enumeration of a heap.
- classmethod from_list(mylist)
Create a heap from a list of elements. :type mylist:
list:param mylist: The list of elements to be inserted into the heap. :type mylist: list- Returns:
An instance of the heap with all elements from the list inserted.
- Return type:
- has_left(index)
Check if current node has an left child.
- Parameters:
index (int) – The index of the node.
- Return type:
bool- Returns:
Boolean on whether a node has a left child node.
- has_parent(index)
Check if a node has a parent node.
- Parameters:
index (int) – The index of the node.
- Return type:
bool- Returns:
Boolean on whether a node has a parent node.
- has_right(index)
Check if current node has an right child.
- Parameters:
index (int) – The index of the node.
- Return type:
bool- Returns:
Boolean on whether a node has a right child node.
- heapify_down(index)
Perform heapify down starting at a given index.
- Parameters:
index (int) – The starting index.
- heapify_up(index)
Perform heapify up starting at a given index.
- Parameters:
index (int) – The starting index.
- insert(value)
Insert a value into the heap.
- Parameters:
value – The value to insert.
- is_empty()
Check if a heap has any items.
- Return type:
bool- Returns:
True if heap has no items. False if heap has more than 0 items.
- last()
Get the last node of the max heap.
- Returns:
The last node’s value. None if count is 0.
- left_index(index)
Get the index of the left child.
- Parameters:
index (int) – The index of the node.
- Return type:
int- Returns:
Return the index of the left child.
- parent_index(index)
Get the index of the parent node.
- Parameters:
index (int) – The index of the node.
- Return type:
int- Returns:
Return the index of the parent child.
- peek()
Get the max value of the max heap.
- Returns:
The maximum value of the max heap.
- pop()
Return the value of the root node (max value) and remove it from the heap.
- Returns:
Return the value from the root node.
- print()
Print the contents of a heap.
- raw_view()
Return the heap in its array representation.
- Returns:
The list representation of the heap.
- Return type:
list
- right_index(index)
Get the index of the right child.
- Parameters:
index (int) – The index of the node.
- Return type:
int- Returns:
Return the index of the right child.
- root()
Get the root value.
- Returns:
The root node’s value. None if count is 0.
- to_sorted_list()
Return a sorted list from the heap.
- Return type:
list- Returns:
A sorted list.
- class dsa.heap.MinHeap
Bases:
Heap- heapify_down(index)
Perform heapify down starting at a given index.
- Parameters:
index (int) – The starting index.
- heapify_up(index)
Perform heapify up starting at a given index.
- Parameters:
index (int) – The starting index.
- class dsa.heap.PriorityQueue
Bases:
MinHeapA priority queue implementation in Python.
- peek()
Return the highest priority value in the heap.
- Returns:
Return The highest priority value in the heap.
- peek_pair()
Return the highest priority value pair in the heap.
- Return type:
tuple- Returns:
Return the highest priority, value pair (tuple) in the heap.
- pop()
Return and remove the highest priority value in the heap.
- Returns:
Return The highest priority value in the heap.
- pop_pair()
Return and remove the highest priority value pair in the heap.
- Return type:
tuple- Returns:
Return the highest priority, value pair (tuple) in the heap.
- push(priority, item)
Insert an item with a priority into the priority queue.
- Parameters:
priority (int) – Priority of item.
item – The item to insert.
- to_string_with_priority()
Return string representation of a heap in order of priority.