| 9 | |
| 10 | |
| 11 | class PriorityQueue: |
| 12 | # Based on Min Heap |
| 13 | def __init__(self): |
| 14 | self.cur_size = 0 |
| 15 | self.array = [] |
| 16 | self.pos = {} # To store the pos of node in array |
| 17 | |
| 18 | def isEmpty(self): |
| 19 | return self.cur_size == 0 |
| 20 | |
| 21 | def min_heapify(self, idx): |
| 22 | lc = self.left(idx) |
| 23 | rc = self.right(idx) |
| 24 | if lc < self.cur_size and self.array(lc)[0] < self.array(idx)[0]: |
| 25 | smallest = lc |
| 26 | else: |
| 27 | smallest = idx |
| 28 | if rc < self.cur_size and self.array(rc)[0] < self.array(smallest)[0]: |
| 29 | smallest = rc |
| 30 | if smallest != idx: |
| 31 | self.swap(idx, smallest) |
| 32 | self.min_heapify(smallest) |
| 33 | |
| 34 | def insert(self, tup): |
| 35 | # Inserts a node into the Priority Queue |
| 36 | self.pos[tup[1]] = self.cur_size |
| 37 | self.cur_size += 1 |
| 38 | self.array.append((sys.maxsize, tup[1])) |
| 39 | self.decrease_key((sys.maxsize, tup[1]), tup[0]) |
| 40 | |
| 41 | def extract_min(self): |
| 42 | # Removes and returns the min element at top of priority queue |
| 43 | min_node = self.array[0][1] |
| 44 | self.array[0] = self.array[self.cur_size - 1] |
| 45 | self.cur_size -= 1 |
| 46 | self.min_heapify(1) |
| 47 | del self.pos[min_node] |
| 48 | return min_node |
| 49 | |
| 50 | def left(self, i): |
| 51 | # returns the index of left child |
| 52 | return 2 * i + 1 |
| 53 | |
| 54 | def right(self, i): |
| 55 | # returns the index of right child |
| 56 | return 2 * i + 2 |
| 57 | |
| 58 | def par(self, i): |
| 59 | # returns the index of parent |
| 60 | return math.floor(i / 2) |
| 61 | |
| 62 | def swap(self, i, j): |
| 63 | # swaps array elements at indices i and j |
| 64 | # update the pos{} |
| 65 | self.pos[self.array[i][1]] = j |
| 66 | self.pos[self.array[j][1]] = i |
| 67 | temp = self.array[i] |
| 68 | self.array[i] = self.array[j] |