| 7 | |
| 8 | |
| 9 | class PriorityQueue: |
| 10 | def __init__(self): |
| 11 | self.elements = [] |
| 12 | self.set = set() |
| 13 | |
| 14 | def minkey(self): |
| 15 | if not self.empty(): |
| 16 | return self.elements[0][0] |
| 17 | else: |
| 18 | return float("inf") |
| 19 | |
| 20 | def empty(self): |
| 21 | return len(self.elements) == 0 |
| 22 | |
| 23 | def put(self, item, priority): |
| 24 | if item not in self.set: |
| 25 | heapq.heappush(self.elements, (priority, item)) |
| 26 | self.set.add(item) |
| 27 | else: |
| 28 | # update |
| 29 | # print("update", item) |
| 30 | temp = [] |
| 31 | (pri, x) = heapq.heappop(self.elements) |
| 32 | while x != item: |
| 33 | temp.append((pri, x)) |
| 34 | (pri, x) = heapq.heappop(self.elements) |
| 35 | temp.append((priority, item)) |
| 36 | for pro, xxx in temp: |
| 37 | heapq.heappush(self.elements, (pro, xxx)) |
| 38 | |
| 39 | def remove_element(self, item): |
| 40 | if item in self.set: |
| 41 | self.set.remove(item) |
| 42 | temp = [] |
| 43 | (pro, x) = heapq.heappop(self.elements) |
| 44 | while x != item: |
| 45 | temp.append((pro, x)) |
| 46 | (pro, x) = heapq.heappop(self.elements) |
| 47 | for prito, yyy in temp: |
| 48 | heapq.heappush(self.elements, (prito, yyy)) |
| 49 | |
| 50 | def top_show(self): |
| 51 | return self.elements[0][1] |
| 52 | |
| 53 | def get(self): |
| 54 | (priority, item) = heapq.heappop(self.elements) |
| 55 | self.set.remove(item) |
| 56 | return (priority, item) |
| 57 | |
| 58 | |
| 59 | def consistent_heuristic(p: TPos, goal: TPos): |