i having real trouble using custom-made heap class functions used in priority queue class. having trouble on functions heap class use "enqueue", "dequeue", "front" , "size" functions priorityqueue. know "enqueue" need use insert function, don't know how go because have priority. me out need in order make priorityqueue class use functions heap class in order work properly? have been stuck on awhile , keep finding answers include using built in python functions such queue , heapq.
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 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 # puts 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 so working stated having trouble on how make priority queue out of this? know asking code wrong, i'm desperate me out here? have basic rundown on want priority code do..
#priorityqueue.py myheap import heap class priorityqueue(object): def __init__(self): self.heap = none def enqueue(self, item, priority): '''post: item inserted specified priority in pq.''' self.heap.insert((priority, item)) def first(self): '''post: returns not remove highest priority item pq.''' return self.heap[0] def dequeue(self): '''post: removes , returns highest priority item pq.''' if self.heap none: raise valueerror("this queue empty.") self.heap.delete_max() def size(self): '''post: returns number of items in pq.''' return self.size this got far not know if entirely correct. me out?
i edited code current version of it.
since presumably homework, can give hints, easier done comments. since ended being thorough series of hints i'm summarizing them answer here.
for part, methods in priorityqueue class map methods you've implemented in heap class:
priorityqueue.enqueue()maps pretty heap.insert()priorityqueue.first()not have corresponding heap method, can still implemented in 1 line. need return maximum value, @ specific place in heap.priorityqueue.dequeue()little more complicated. needs save value of top item first can return after callingheap.delete_max()- the heap class has
size()method,priorityqueue.size()can call, instead of maintaining separate size variable withinpriorityqueueclass.
additionally, need init function, should create new heap object maintained class.
in order make iterator, you'll need make new class. need maintain integer variable (let's call self.index), indicating current place in queue. you'll want method increases self.index , returns value @ previous index location. should it.
