Advertisement
Guest User

Untitled

a guest
Oct 19th, 2018
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.94 KB | None | 0 0
  1. def _sift_down(self, index):
  2. """ Swap with smallest child if needed
  3. and sift_down from that child index if swapped.
  4. """
  5. # ---start student section---
  6. if self._indices_of_children(index) != []:
  7. min_child = self._index_of_min_child(self._indices_of_children(index))
  8. self.comparisons += 1
  9. if self._data[min_child].priority < self._data[index].priority:
  10. self._swap(min_child, index)
  11. self._sift_down(min_child)
  12. # ===end student section===
  13.  
  14. def _heapify(self, start_data):
  15. """ Turn the existing data into a heap in O(n log n) time. """
  16. for car in start_data:
  17. self.enqueue(car)
  18.  
  19. def _fast_heapify(self, data):
  20. """ Turn the existing data into a heap in O(n) time. """
  21. # ---start student section---
  22. for car in data:
  23. assert isinstance(car, Car)
  24. self._data.append(car)
  25. for num in range((len(self._data)//self.num_children)-1,-1,-1):
  26. self._sift_down(num)
  27.  
  28.  
  29. # ===end student section===
  30.  
  31. def enqueue(self, car):
  32. """ Add a car to the queue. """
  33. # We first make sure that we're only including Cars
  34. assert isinstance(car, Car)
  35. # ---start student section---
  36. self._data.append(car)
  37. self._sift_up(len(self._data)-1)
  38. # ===end student section===
  39.  
  40. def dequeue(self):
  41. """ Take the min priority Car off the queue and return the Car object
  42.  
  43. Must raise IndexError("Can't dequeue from empty queue!") if the queue is empty.
  44. """
  45. # ---start student section---
  46. if len(self._data) < 1:
  47. raise IndexError("Can't dequeue from empty queue!")
  48. dequeued_value = self._data[0]
  49. self._data[0] = self._data[-1]
  50. self._data.pop()
  51. self._sift_down(0)
  52. return dequeued_value
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement