Skip to main content

​
Heap

A max heap implementation where the largest element is always at the root.

​
Constructor

Heap()
Create an empty max heap. Example: 
from ucx_dsa import Heap

heap = Heap()

​
Class Methods

​
from_list(mylist)

Create a heap from a list of elements. 
Heap.from_list(mylist)
​
mylist
list
required
The list of elements to be inserted into the heap.
​
return
Heap
An instance of the heap with all elements from the list inserted.
Example: 
from ucx_dsa import Heap

heap = Heap.from_list([3, 1, 4, 1, 5, 9, 2, 6])
print(heap.peek())  # Output: 9
Time Complexity: O(n log n) where n is the number of elements

​
Methods

​
raw_view()

Return the heap in its internal array representation. 
heap.raw_view()
​
return
list
The list representation of the heap.
Example: 
from ucx_dsa import Heap

heap = Heap.from_list([3, 1, 4])
print(heap.raw_view())  # Output: [4, 1, 3]
Time Complexity: O(1)

​
root()

Get the root value (maximum value in a max heap). 
heap.root()
​
return
any
The root node’s value, or None if the heap is empty.
Example: 
from ucx_dsa import Heap

heap = Heap.from_list([3, 1, 4, 1, 5])
print(heap.root())  # Output: 5
Time Complexity: O(1)

​
peek()

Get the max value of the max heap (same as root()). 
heap.peek()
​
return
any
The maximum value in the heap.
Example: 
from ucx_dsa import Heap

heap = Heap.from_list([10, 20, 30])
print(heap.peek())  # Output: 30
Time Complexity: O(1)

​
last()

Get the last node of the max heap. 
heap.last()
​
return
any
The last node’s value, or None if the heap is empty.
Example: 
from ucx_dsa import Heap

heap = Heap.from_list([5, 3, 7])
print(heap.last())  # Returns the last element in the internal array
Time Complexity: O(1)

​
left_index(index)

Get the index of the left child node. 
heap.left_index(index)
​
index
int
required
The index of the parent node.
​
return
int
The index of the left child.
Time Complexity: O(1)

​
right_index(index)

Get the index of the right child node. 
heap.right_index(index)
​
index
int
required
The index of the parent node.
​
return
int
The index of the right child.
Time Complexity: O(1)

​
parent_index(index)

Get the index of the parent node. 
heap.parent_index(index)
​
index
int
required
The index of the child node.
​
return
int
The index of the parent node.
Time Complexity: O(1)

​
has_left(index)

Check if the current node has a left child. 
heap.has_left(index)
​
index
int
required
The index of the node.
​
return
bool
True if the node has a left child, False otherwise.
Time Complexity: O(1)

​
has_right(index)

Check if the current node has a right child. 
heap.has_right(index)
​
index
int
required
The index of the node.
​
return
bool
True if the node has a right child, False otherwise.
Time Complexity: O(1)

​
has_parent(index)

Check if a node has a parent node. 
heap.has_parent(index)
​
index
int
required
The index of the node.
​
return
bool
True if the node has a parent, False otherwise.
Time Complexity: O(1)

​
insert(value)

Insert a value into the heap. 
heap.insert(value)
​
value
any
required
The value to insert.
Example: 
from ucx_dsa import Heap

heap = Heap()
heap.insert(10)
heap.insert(20)
heap.insert(15)

print(heap.peek())  # Output: 20
Time Complexity: O(log n)

​
heapify_up(index)

Perform heapify up operation starting at a given index. This maintains the max heap property by moving an element up the tree. 
heap.heapify_up(index)
​
index
int
required
The starting index.
Time Complexity: O(log n)

​
pop()

Return the value of the root node (max value) and remove it from the heap. 
heap.pop()
​
return
any
The maximum value from the heap.
Raises:
  • Exception: If the heap is empty
Example: 
from ucx_dsa import Heap

heap = Heap.from_list([5, 3, 7, 1])
max_val = heap.pop()
print(max_val)  # Output: 7
print(heap.peek())  # Output: 5
Time Complexity: O(log n)

​
heapify_down(index)

Perform heapify down operation starting at a given index. This maintains the max heap property by moving an element down the tree. 
heap.heapify_down(index)
​
index
int
required
The starting index.
Time Complexity: O(log n)

​
enumerate()

Return the enumeration of the heap. 
heap.enumerate()
​
return
enumerate
Enumeration of the heap’s internal array.
Example: 
from ucx_dsa import Heap

heap = Heap.from_list([3, 1, 4])
for index, value in heap.enumerate():
    print(f"Index {index}: {value}")
Time Complexity: O(1) to create, O(n) to iterate

​
count()

Return the number of items in the heap. 
heap.count()
​
return
int
The number of items in the heap.
Example: 
from ucx_dsa import Heap

heap = Heap.from_list([1, 2, 3, 4])
print(heap.count())  # Output: 4
Time Complexity: O(1)

​
is_empty()

Check if the heap has any items. 
heap.is_empty()
​
return
bool
True if the heap has no items, False otherwise.
Example: 
from ucx_dsa import Heap

heap = Heap()
print(heap.is_empty())  # Output: True

heap.insert(5)
print(heap.is_empty())  # Output: False
Time Complexity: O(1)

​
print()

Print the contents of the heap in level-order. 
heap.print()
Example: 
from ucx_dsa import Heap

heap = Heap.from_list([1, 2, 3, 4, 5])
heap.print()
# Output:
# 5
# 4 3
# 1 2

​
to_sorted_list()

Return a sorted list from the heap (descending order for max heap). 
heap.to_sorted_list()
​
return
list
A sorted list in descending order.
Example: 
from ucx_dsa import Heap

heap = Heap.from_list([3, 1, 4, 1, 5, 9, 2])
print(heap.to_sorted_list())  # Output: [9, 5, 4, 3, 2, 1, 1]
Time Complexity: O(n log n)

​
extract_max()

Return the value of the root node (max value) and remove it from the heap. Alias for pop(). 
heap.extract_max()
​
return
any
The maximum value from the heap.
Example: 
from ucx_dsa import Heap

heap = Heap.from_list([10, 20, 30])
max_val = heap.extract_max()
print(max_val)  # Output: 30
Time Complexity: O(log n)

​
Special Methods

​
__repr__()

Return string representation of the heap in order of priority. 
str(heap)
repr(heap)
​
return
str
String showing elements in descending order of priority.
Example: 
from ucx_dsa import Heap

heap = Heap.from_list([3, 1, 4])
print(heap)  # Output: [4 3 1]

​
__len__()

Get the number of items in the heap. 
len(heap)
​
return
int
Number of items in the heap.
Example: 
from ucx_dsa import Heap

heap = Heap.from_list([1, 2, 3])
print(len(heap))  # Output: 3
Time Complexity: O(1)

​
__eq__(other)

Compare two Heap objects for value-based equality. 
heap1 == heap2
​
other
Heap
required
The other heap to compare against.
​
return
bool
True if both are Heap instances and their internal arrays are equal.
Example: 
from ucx_dsa import Heap

heap1 = Heap.from_list([1, 2, 3])
heap2 = Heap.from_list([1, 2, 3])

print(heap1 == heap2)  # Output: True
Time Complexity: O(n)

Build docs developers (and LLMs) love

Get started for freeTalk to us