"""Module containing a priority queue that can remove arbitrary items."""
from basic_priority_queue import BasicPriorityQueue

class ChangePriorityQueue(BasicPriorityQueue):
"""Implementation of a binary max-heap based priority queue with remove
item functionality.
You can assume that all items will be unique.
Priorities may not be unique.
The heap ordering is based solely on the priorities, that is you should
only use priority when comparing nodes, NOT the full (priority, item) tuples.
"""

def __init__(self, initial_items=None, initial_priorities=None):
   """Makes a new priority queue containing initial_items and uses
   the corresponding position in initial_priorities as the priority
   for each item.
   If initial_priorities is not provided then the priority for each
   item is simply set to the item's index in the initial_items list.
   Your code should keep track of any key comparisons that are made
   by using self._comparisons += 1
   """
   self._item_indices = dict()

   if initial_items is not None:
         for index, item in enumerate(initial_items):
            self._item_indices[item] = index
         items = []
         for i in range(len(initial_items)):
            item = initial_items[i]
            if initial_priorities is not None:
               priority = initial_priorities[i]
            else:
               priority = i
            record = (priority, item)
            items.append(record)
         # the super's __init__ will heapify, etc, from here...
         super().__init__(items)
   else:
         # start with empty queue.
         super().__init__()

def insert(self, item):
   """Insert cannot be used in change_priority_queue as the priority must
   be explicitly given, use .insert_with_priority instead.
   """
   raise TypeError(
         "Also need priority. Call insert_with_priority instead!")

def _swap_items(self, index, swap_index):
   """Swaps the items at the given indices in the heap and updates
   the _item_indices dictionary to be consistent with the change.
   """
   # ---start student section---
   self._item_indices[self._items[index][1]] = swap_index
   self._item_indices[self._items[swap_index][1]] = index

   self._items[index], self._items[swap_index] = self._items[swap_index], self._items[index]

   # ===end student section===

def _max_child_index(self, index):
   """Returns the index of the first child with the maximal priority value
   of any child of the node at the given index.
   If no such maximal child exists -1 is returned, ie, if there are no children.
   Note: this method is very similar to the basic priority queue but it
   needs to now look at the priotity value in the tuple that is store in each node.
   """
   # ---start student section---
   child_indices = self._children_indices(index)
   if len(child_indices) == 0:
         return -1
   max_child_index = child_indices[0]
   for i in child_indices[1:]:
         item = self._items[i][1]
         max_item = self._items[max_child_index][1]
         self._comparisons += 1
         if item > max_item:
            max_child_index = i
   return max_child_index
   # ===end student section===

def _sift_up(self, index):
   """Moves the item at the given index up through the heap until it finds
   the correct place for it. That is, the item is moved up through the heap
   while its priority is larger than its parent's priority.
   Notice the beauty of recursion.
   To carry out the sift up, the function simply swaps with the parent
   if needed and then sifts up from the parent...
   NOTE: This is very similar to the method in the basic class
   but this method should use the priorty to compare.
   Remember each node now store a (priority, item) tuple.
   The heap ordering is based solely on the priorities, that is you should
   only use priority when comparing nodes, NOT the full (priority, item) tuples.
   """
   # ---start student section---
   parent_index = self._parent_index(index)
   # remember max_child is -1 if there aren't any children
   if parent_index >= 0:
         self._comparisons += 1
         if self._items[index][0] > self._items[parent_index][0]:
            self._swap_items(index, parent_index)
            self._sift_up(parent_index)

   # ===end student section

Assignment #3 - Distance Calculator Objectives Code a script / pr...