i having problem code. keep getting following error:
attributeerror: 'nonetype' object has no attribute 'insert' could tell me why getting error? here code , snippit causing problem below that.
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 that main heap function need take functions from. part of code giving me trouble.
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 here priorityqueue class calls functions , helps me implement them priority queue.
from 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 heap.size() none: raise valueerror("error queue empty.") self.first() self.heap.delete_max() def size(self): '''post: returns number of items in pq.''' return heap.size() so in code enqueue calls insert function.
def enqueue(self, item, priority): '''post: item inserted specified priority in pq.''' self.heap.insert(priority, item) finally here test code:
from priorityqueue import priorityqueue pq = priorityqueue() pq.enqueue(1, 200) pq.enqueue(2, 450) pq.enqueue(3, 204) it simple fix, know why keep getting attribute error?
that's because initialize self.heap none:
class priorityqueue(object): def __init__(self): self.heap = none you should initialize heap():
class priorityqueue(object): def __init__(self): self.heap = heap() your code has other issues:
you should call self.heap.insert 1 parameter (you're calling two):
def enqueue(self, item, priority): '''post: item inserted specified priority in pq.''' self.heap.insert((priority, item)) you should use self.heap.size(), not heap.size():
if self.heap.size() == 0: raise valueerror("error queue empty.") and also
def size(self): '''post: returns number of items in pq.''' return self.heap.size() you should return value self.heap.delete_max():
def dequeue(self): '''post: removes , returns highest priority item pq.''' if self.heap.size() == 0: raise valueerror("error queue empty.") return self.heap.delete_max() first must return [1] element in heap, because [0] none:
def first(self): '''post: returns not remove highest priority item pq.''' return self.heap.heap[1] 