Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def _sift_down(self, index):
- """ Swap with smallest child if needed
- and sift_down from that child index if swapped.
- """
- # ---start student section---
- if self._indices_of_children(index) != []:
- min_child = self._index_of_min_child(self._indices_of_children(index))
- self.comparisons += 1
- if self._data[min_child].priority < self._data[index].priority:
- self._swap(min_child, index)
- self._sift_down(min_child)
- # ===end student section===
- def _heapify(self, start_data):
- """ Turn the existing data into a heap in O(n log n) time. """
- for car in start_data:
- self.enqueue(car)
- def _fast_heapify(self, data):
- """ Turn the existing data into a heap in O(n) time. """
- # ---start student section---
- for car in data:
- assert isinstance(car, Car)
- self._data.append(car)
- for num in range((len(self._data)//self.num_children)-1,-1,-1):
- self._sift_down(num)
- # ===end student section===
- def enqueue(self, car):
- """ Add a car to the queue. """
- # We first make sure that we're only including Cars
- assert isinstance(car, Car)
- # ---start student section---
- self._data.append(car)
- self._sift_up(len(self._data)-1)
- # ===end student section===
- def dequeue(self):
- """ Take the min priority Car off the queue and return the Car object
- Must raise IndexError("Can't dequeue from empty queue!") if the queue is empty.
- """
- # ---start student section---
- if len(self._data) < 1:
- raise IndexError("Can't dequeue from empty queue!")
- dequeued_value = self._data[0]
- self._data[0] = self._data[-1]
- self._data.pop()
- self._sift_down(0)
- return dequeued_value
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement