Module dalpy.heaps

This module holds classes and functions related to heaps and priority queues.

This module contains PriorityQueue, an implementation of a priority queue, and PriorityQueueUnderflowError, an error raised by PriorityQueue. This module also contains the function build_min_heap() which modifies the elements of an Array so that they construct a min heap.

Examples

Initializing, adding, and removing elements from a PriorityQueue:

q = PriorityQueue()
q.insert('a', 2)
q.insert('b', 1)
q.extract_min()

The following code will raise a PriorityQueueUnderflowError because the second extract min is done on an empty PriorityQueue:

q.extract_min()
q.extract_min()

Functions

def build_min_heap(arr)

Modifies an Array so that its elements make up a min heap.

This method does not return a copy of the provided Array whose elements make up a heap, it modifies it in place. Furthermore, all the elements (starting from index 0) are in a min heap. This method runs in O(n) time where n is the length of the input Array.

Args

arr

The input Array. Its elements should be comparable with <, >=, etc.

Raises

TypeError

If arr is not an Array'.

Classes

class PriorityQueue

This class represents a minimum priority queue.

One may assume that this PriorityQueue has no maximum capacity.

Examples

To initialize a PriorityQueue:

q = PriorityQueue()

To add elements to q:

q.insert('a', 2)
q.insert('b', 1)

To remove and return the minimum priority element of q (in this case x = 'b'):

x = q.extract_min()

To see the minimum priority element of q (in this case y = 'a'):

y = q.front()

To decrease the priority of an element in q:

q.decrease_key('a', 0)

Initializes an empty PriorityQueue in O(1) time.

Methods

def decrease_key(self, element, new_priority)

Decreases the priority of an element in this PriorityQueue.

This operation runs in O(log(n)) time where n is the size of this PriorityQueue.

Args

element

The element whose priority is being updated.

new_priority

The new priority of element. It should be <= its existing priority.

Raises

ValueError

If element is not in this PriorityQueue or new_priority is greater than the existing priority of element.

def extract_min(self)

Removes the minimum priority element of this PriorityQueue.

This operation runs in O(log(n)) time where n is the size of this PriorityQueue.

Returns

The element with the minimum priority in this PriorityQueue.

Raises

PriorityQueueUnderflowError

If this PriorityQueue is empty.

def insert(self, element, priority)

Inserts an element into the PriorityQueue with an associated priority.

This operation runs in O(log(n)) time where n is the size of this Queue.

Args

element

An element to add to this PriorityQueue. This can be of any type.

priority

The integer priority element should have in this PriorityQueue.

def is_empty(self)

Returns whether this PriorityQueue is empty in O(1) time w/r/t the size of this PriorityQueue.

Returns

True if this PriorityQueue is empty, False otherwise.

def minimum(self)

Gets the minimum priority element of this PriorityQueue.

This operation runs in O(1) time with respect to the size of this PriorityQueue.

Returns

The element with the minimum priority in this PriorityQueue.

Raises

PriorityQueueUnderflowError

If this PriorityQueue is empty.

def size(self)

Returns the size of this PriorityQueue in O(1) time w/r/t the size of this PriorityQueue.

Returns

The integer number of elements in this PriorityQueue.

class PriorityQueueUnderflowError (operation)

This class is used by PriorityQueue to raise errors for operations done on an empty PriorityQueue.

Initializes a PriorityQueueUnderflowError that will be raised associated with a PriorityQueue operation.

Args

operation

a string specifying the operation to raise an error on

Ancestors

• builtins.Exception
• builtins.BaseException