Docs Min Heap on GitHub

Min Heap¶

A heap is a binary tree that stores a collection of nodes. Each node must satisfy two additional properties:

1. Heap-Order Property: It is a relational property defined in terms of the value stored at the node. So, for every node, other than the root, the value stored at the node is greater than or equal to the value stored at the node’s parent. As a consequence of the heap-order property, the value encountered on a path from the root to a leaf node are in nondecreasing order. Also, the minimum value is always stored at the root of the MinHeap(). This makes it easy to locate such a node when get_min() or remove_min() is called, as it is informally said to be at the top of the heap. Hence, the name “Min Heap”

2. Perfect Binary Tree Property: It is a structural property defined in terms of the shape of heap itself. A binary tree is perfect if all its levels are completely filled. So, given an n inserted items, the height of the heap should be log(n) at most.

⏱ Time-Complexity¶

The following table sums up all the different public functionality in this class and also provides the worst-case time complexity along side with the optimal time complexity that I will try to reach in future releases Insha’Allah. Generally, we are going to use the following indicators in the table:

n is the number of nodes currently in the min heap.
h is the height of the heap which approximatley equals to log(n).

Method	Description	Worst-case	Optimal
is_empty()	Checks if the Min Heap is empty.	O(1)	O(1)
__len__()	Returns the number of nodes in the Min Heap.	O(1)	O(1)
__repr__()	Represents the Min Heap as a string.	O(n)	O(n)
__iter__()	Iterates over the Min Heap.	O(n)	O(n)
__contains__()	Checks the existence of the given item.	O(n)	O(n)
clear()	Clears the whole Min Heap instance.	O(1)	O(1)
to_list()	Converts the Min Heap instance to list.	O(1)	O(1)
get_min()	Gets the minimum number in the Min Heap.	O(1)	O(1)
get_max()	Gets the maximum number in the Min Heap.	O(n)	O(n)
insert()	Inserts a certain value to the Min Heap.	O(h)	O(h)
remove()	Removes a certain value from the Min Heap.	O(h)	O(h)
remove_min()	Removes the minimum value from the Min Heap.	O(1)	O(1)
remove_max()	Removes a certain value from the Min Heap.	O(n)	O(n)

☕️ API¶

Here are all of the public methods that can be used with MinHeap() objects:

class extra.trees.min_heap.MinHeap¶

A Min heap is a perfect binary tree that stores a collection of nodes. Each node stores a value greater than or equal to the value strored at the node’s parent.

__contains__(num)¶

Searches the MinHeap() for the given value and returns True if the value exists and False if not in linear time.

Parameters:	find_val (int or float) – The value to be searched for in the MinHeap() instance.
Returns:	Returns True if the value exists in the MinHeap() instance and False if not.
Return type:	bool

Example

>>> min_heap = MinHeap.heapify([2, 4, 3, 7, 9, 0, 1])
>>> min_heap
    __0__
   /     \
  4       1
 / \     / \
7   9    3   2
>>> 9 in min_heap
True
>>> 5 in min_heap
False
>>> 50 in min_heap
False

__init__()¶

Creates an empty MinHeap() object!!

Example

>>> min_heap = MinHeap()
>>> type(min_heap)
<class 'extra.trees.min_heap.MinHeap'>
>>> min_heap
/ \

__iter__()¶

Iterates over the MinHeap() instance and returns a generator of the heap node values in breadth-first manner.

Yields:	int or float – The number stored at each node in the instance.

Example

>>> min_heap = MinHeap.heapify([2, 4, 3, 7, 9, 0, 1])
>>> min_heap
    __0__
   /     \
  4       1
 / \     / \
7   9    3   2
>>> for value in min_heap:
...     print(value, end=',')
0,4,1,7,9,3,2,

__len__()¶

Gets the length of the MinHeap() instance in constant time.

Returns:	The length of the MinHeap() instance. Length is the number of tree nodes in the instance.
Return type:	int

Example

>>> min_heap = MinHeap.heapify([2, 4, 3, 7, 9, 0, 1])
>>> min_heap
    __0__
   /     \
  4       1
 / \     / \
7   9    3   2
>>> len(min_heap)
7

__repr__()¶

Represents the MinHeap() instance as a string.

Returns:	The string-representation of the MinHeap() instance.
Return type:	str

Example

>>> min_heap = MinHeap.heapify([2, 4, 3, 7, 9, 0, 1])
>>> min_heap
    __0__
   /     \
  4       1
 / \     / \
7   9    3   2

clear()¶

Removes all nodes within the MinHeap() instance in constant time.

Example

>>> min_heap = MinHeap.heapify([2, 4, 3, 7, 9, 0, 1])
>>> min_heap
    __0__
   /     \
  4       1
 / \     / \
7   9    3   2
>>> min_heap.clear()
>>> min_heap
/ \
>>> min_heap.is_empty()
True

get_max()¶

Gets the maximum value in the MinHeap() instance in linear time. The maximum value can be found at the deepest level of the MinHeap() instance.

Returns:	The masximum numeric value in the MinHeap() instance.
Return type:	int or float
Raises:	IndexError: – In case the MinHeap() instance is empty.

Example

>>> min_heap = MinHeap.heapify([2, 4, 3, 7, 9, 0, 1])
>>> min_heap
    __0__
   /     \
  4       1
 / \     / \
7   9    3   2
>>> min_heap.get_max()
9

get_min()¶

Gets the minimum value in the MinHeap() instance in constant time. The minimum value can be found at the root of the MinHeap() instance.

Returns:	The minimum numeric value in the MinHeap() instance.
Return type:	int or float
Raises:	IndexError: – In case the MinHeap() instance is empty.

Example

>>> min_heap = MinHeap.heapify([2, 4, 3, 7, 9, 0, 1])
>>> min_heap
    __0__
   /     \
  4       1
 / \     / \
7   9    3   2
>>> min_heap.get_min()
0

classmethod heapify(iterable)¶

A class method which creates a MinHeap() instance using an iterable object in time-complexity of O(n) where n is the number of elements inside the given iterable.

Parameters:	iterable (iterable) – An iterable python object that implements the __iter__ method. For example, list and tuple are both iterables.
Returns:	It returns a MinHeap() instance with input values being inserted.
Return type:	MinHeap()
Raises:	TypeError: – It can be raised in two cases In case the given object isn’t iterable. If one of the elements in the iterable is NOT a number. ValueError: – If one of the iterable elements is None.

Examples

>>> MinHeap.heapify([2, 4, 3, 7, 9, 0, 1])
    __0__
   /     \
  4       1
 / \     / \
7   9    3   2

Using an iterable object with None as one of its elements will raise ValueError

>>> MinHeap.heapify([2, None])
ValueError: Can't use `None` as an element within `extra.MinHeap()`!!

Using a non-iterable object will raise TypeError

>>> MinHeap.heapify(2)
TypeError: The given object isn't iterable!!

Using nested MinHeap() objects will raise TypeError as well

>>> min_heap_1 = MinHeap.heapify([1])
>>> min_heap_2 = MinHeap.heapify([1, min_heap_1])
TypeError: Can't create `extra.MinHeap()` using `extra.MinHeap()`!!

insert(value)¶

Inserts a numeric value in the MinHeap() instance.

Parameters:	value (int or float) – The new numeric value that will be inserted.
Raises:	ValueError: – If the given value is None. TypeError: – If the given value is not a numeric value.

Example

>>> min_heap = MinHeap.heapify([2, 4, 3, 7, 9, 0, 1])
>>> min_heap
    __0__
   /     \
  4       1
 / \     / \
7   9    3   2
>>> min_heap.insert(15)
>>> min_heap.insert(-1)
>>> min_heap
         __-1__
        /      \
     __0        1
    /   \     / \
  _4     9    3   2
 /  \
15   7

is_empty()¶

Checks if the MinHeap() instance is empty or not in constant time.

Returns:	A boolean flag showing if the MinHeap() instance is empty or not. True shows that this instance is empty and False shows it’s not empty.
Return type:	bool

Example

>>> min_heap = MinHeap()
>>> min_heap.is_empty()
True
>>> min_heap.insert(10)
>>> min_heap.is_empty()
False

remove(del_value)¶

Removes the del_value from the MinHeap() instance.

Parameters:	del_value (int or float) – The value to be deleted from the subtree.
Raises:	UserWarning: – If the MinHeap() instance is empty of if the value wasn’t found in the instance.

Example

>>> min_heap = MinHeap.heapify([2, 4, 3, 7, 9, 0, 1])
>>> min_heap
    __0__
   /     \
  4       1
 / \     / \
7   9    3   2
>>> min_heap.remove(0)
>>> min_heap
    __1__
   /     \
  4       2
 / \    /
7   9   3
>>> min_heap.remove(50)
UserWarning: Couldn't find `50` in `extra.MinHeap()`!!

remove_max()¶

Removes the maximum value from the MinHeap() instance which is one of the nodes at the deepest level of the instance.

Raises:	UserWarning: – If the MinHeap() instance is empty of if the value wasn’t found in the instance.

Example

>>> min_heap = MinHeap.heapify([2, 4, 3, 7, 9, 0, 1])
>>> min_heap
    __0__
   /     \
  4       1
 / \    / \
7   9   3   2
>>> min_heap.remove_max()
>>> min_heap
    __0__
   /     \
  4       1
 /       / \
7       3   2

remove_min()¶

Removes the minimum value from the MinHeap() instance which is the root.

Raises:	UserWarning: – If the MinHeap() instance is empty of if the value wasn’t found in the instance.

Example

>>> min_heap = MinHeap.heapify([2, 4, 3, 7, 9, 0, 1])
>>> min_heap
    __0__
   /     \
  4       1
 / \     / \
7   9    3   2
>>> min_heap.remove_min()
>>> min_heap
    __1__
   /     \
  4       2
 / \    /
7   9   3

to_list()¶

Converts the MinHeap() instance to a list where values will be inserted in breadth-first manner.

Returns:	A list object containing the same elements as the MinHeap() instance.
Return type:	list

Example

>>> min_heap = MinHeap.heapify([2, 4, 3, 7, 9, 0, 1])
>>> min_heap
    __0__
   /     \
  4       1
 / \     / \
7   9    3   2
>>> min_heap.to_list()
[0, 4, 1, 7, 9, 3, 2]

Previous Next

2020, anwarvic

Created using Sphinx (1.8.6) with Minoo (Beta 0.9.7) theme.