i implementing priority queue using max-heap data structure in python. i'm using several names have numbers associated them priority (9 being highest , 1 being lowest). issue facing when dequeue item priority queue, not dequeue item highest priority. assume means there problem enqueue , not inserting items correct position in heap based on priority. if me fix this, appreciated.
my priority queue code:
from heap import heap class priorityq(object): def __init__(self): self.pq = heap() def enqueue(self, priority, item): self.pq.insert((priority, item)) def dequeue(self): if self.pq.size() == 0: raise valueerror("empty queue") return self.pq.delete_max() def first(self): return self.pq.get_max() def size(self): return self.pq.size() def main(): myheap = priorityq() print(myheap.size()) myheap.enqueue(8, "kaneda") myheap.enqueue(6, "masaru") myheap.enqueue(9, "akira") myheap.enqueue(4, " kei") myheap.enqueue(5, "takashi") myheap.enqueue(2, "shikishima") myheap.enqueue(3, "kiyoko") myheap.enqueue(1, "yamagata") myheap.enqueue(7, "tetsuo") print(myheap.first()) print(myheap.size()) myheap.dequeue() print(myheap.first()) print(myheap.size()) myheap.dequeue() print(myheap.first()) print(myheap.size()) myheap.dequeue() print(myheap.first()) print(myheap.size()) myheap.dequeue() print(myheap.first()) print(myheap.size()) myheap.dequeue() print(myheap.first()) print(myheap.size()) myheap.dequeue() print(myheap.first()) print(myheap.size()) myheap.dequeue() print(myheap.first()) print(myheap.size()) myheap.dequeue() print(myheap.first()) print(myheap.size()) myheap.dequeue() print(myheap.first()) print(myheap.size()) output after run code , call main:
0 (9, 'akira') 9 (7, 'tetsuo') 8 (5, 'takashi') 7 (4, 'kei') 6 (3, 'kiyoko') 5 (2, 'shikishima') 4 (1, 'yamagata') 3 (1, 'yamagata') 2 (1, 'yamagata') 1 none 0 max-heap code (provided textbook):
# heap.py class heap(object): #------------------------------------------------------------ def __init__(self, items=none): '''post: heap created specified items''' self.heap = [none] if items none: self.heap_size = 0 else: self.heap += items self.heap_size = len(items) self._build_heap() #------------------------------------------------------------ def size(self): '''post: returns number of items in heap''' return self.heap_size #------------------------------------------------------------ def _heapify(self, position): '''pre: items 0 position - 1 satisfy heap property post: heap property satisfied entire heap''' item = self.heap[position] while position * 2 <= self.heap_size: child = position * 2 # if right child, determine maximum of 2 children if (child != self.heap_size , self.heap[child+1] > self.heap[child]): child += 1 if self.heap[child] > item: self.heap[position] = self.heap[child] position = child else: break self.heap[position] = item #------------------------------------------------------------ def delete_max(self): '''pre: heap property satisfied post: maximum element in heap removed , returned''' if self.heap_size > 0: max_item = self.heap[1] self.heap[1] = self.heap[self.heap_size] self.heap_size -= 1 self.heap.pop() if self.heap_size > 0: self._heapify(1) return max_item def get_max(self): if self.heap_size > 0: max_item = self.heap[1] self.heap[1] = self.heap[self.heap_size] if self.heap_size > 0: self._heapify(1) return max_item #------------------------------------------------------------ def insert(self, item): '''pre: heap property satisfied post: item inserted in proper location in heap''' self.heap_size += 1 # extend length of list self.heap.append(none) position = self.heap_size parent = position // 2 while parent > 0 , self.heap[parent] < item: # move item down self.heap[position] = self.heap[parent] position = parent parent = position // 2 # put new item in correct spot self.heap[position] = item #------------------------------------------------------------ def _build_heap(self): '''pre: self.heap has values in 1 self.heap_size post: heap property satisfied entire heap''' # 1 through self.heap_size in range(self.heap_size // 2, 0, -1): # stops @ 1 self._heapify(i) #------------------------------------------------------------ def heapsort(self): '''pre: heap property satisfied post: items sorted in self.heap[1:self.sorted_size]''' sorted_size = self.heap_size in range(0, sorted_size - 1): # since delete_max calls pop remove item, need # append dummy value avoid illegal index. self.heap.append(none) item = self.delete_max() self.heap[sorted_size - i] = item
your problem seems in enqueue.
def enqueue(self, item, priority): self.pq.insert(item) the priority parameter not used @ all. instead, heap using string comparisons.
this state of heap before dequeue:
[none, 'yamagata', 'tetsuo', 'shikishima', 'takashi', 'masaru', 'akira', 'kiyoko', 'kei', 'kaneda'] 