def pq_split_key(source, key): """ ------------------------------------------------------- Splits a priority queue into two depending on an external priority key. The source priority queue is empty when the method ends. Use: target1, target2 = pq_split_key(source, key) ------------------------------------------------------- Parameters: source - a priority queue (Priority_Queue) key - a data object (?) Returns: target1 - a priority queue that contains all values with priority higher than key (Priority_Queue) target2 - priority queue that contains all values with priority lower than or equal to key (Priority_Queue) ------------------------------------------------------- """

This function uses a priority queue, meaning you may manipulate the queue using only the queue interface methods: insert, remove, is_empty, and peek. You may not use or refer to the internal Priority Queue elements such as _values.

The code about priority queue:

class Priority_Queue:

def __init__(self): """ ------------------------------------------------------- Initializes an empty priority queue. Use: pq = Priority_Queue() ------------------------------------------------------- Returns: a new Priority_Queue object (Priority_Queue) ------------------------------------------------------- """ self._values = [] self._first = None

def is_empty(self): """ ------------------------------------------------------- Determines if the priority queue is empty. Use: b = pq.is_empty() ------------------------------------------------------- Returns: True if priority queue is empty, False otherwise. ------------------------------------------------------- """ return len(self._values) == 0

def __len__(self): """ ------------------------------------------------------- Returns the length of the priority queue. Use: n = len(pq) ------------------------------------------------------- Returns: the number of values in the priority queue. ------------------------------------------------------- """ return len(self._values)

def insert(self, value): """ ------------------------------------------------------- A copy of value is appended to the end of the the priority queue Python list, and _first is updated as appropriate to the index of value with the highest priority. Use: pq.insert(value) ------------------------------------------------------- Parameters: value - a data element (?) Returns: None ------------------------------------------------------- """ self._values.append(deepcopy(value)) if self._first is None: self._first = 0 elif value < self._values[self._first]: self._first = len(self._values) - 1

# your code here

return

def peek(self): """ ------------------------------------------------------- Peeks at the highest priority value of the priority queue. Use: v = pq.peek() ------------------------------------------------------- Returns: value - a copy of the highest priority value in the priority queue - the value is not removed from the priority queue. (?) ------------------------------------------------------- """ assert len(self._values) > 0, "Cannot peek at an empty priority queue" value = deepcopy(self._values[self._first]) # your code here

return value

def remove(self): """ ------------------------------------------------------- Removes and returns the highest priority value from the priority queue. Use: value = pq.remove() ------------------------------------------------------- Returns: value - the highest priority value in the priority queue - the value is removed from the priority queue. (?) ------------------------------------------------------- """ assert len(self._values) > 0, "Cannot remove from an empty priority queue" value = self._values.pop(self._first) n = len(self._values) if n == 0: self._first = None else: self._first = 0 for i in range(1, n): if self._values[self._first] > self._values[i]: self._first = i return value

def _set_first(self): """ ------------------------------------------------------- Private helper function to set the value of _first. _first is the index of the value with the highest priority in the priority queue. None if queue is empty. Use: self._set_first() ------------------------------------------------------- Returns: None ------------------------------------------------------- """ n = len(self._values) if n == 0: self._first = None else: self._first = 0 for i in range(1, n): if self._values[i]

def __iter__(self): """ FOR TESTING ONLY ------------------------------------------------------- Generates a Python iterator. Iterates through the priority queue from front to rear. Not in priority order. Use: for value in pq: ------------------------------------------------------- Returns: value - the next value in the priority queue (?) ------------------------------------------------------- """ for value in self._values: yield value