class Node:
def __init__(self,key):
# constructorJava Code for Heaps
self.iData = key
def getKey(self):
return self.iData
def setKey(self,i):
self.iData = i
class Heap:
def __init__(self,mx):
self.maxSize = mx
self.currentSize = 0
self.heapArray = []
for i in range(self.maxSize):
self.heapArray.append(Node(0))
def isEmpty(self):
return self.currentSize==0
def insert(self,key):
if(self.currentSize==self.maxSize):
return False
newNode = Node(key)
self.heapArray[self.currentSize] = newNode
self.trickleUp(self.currentSize)
self.currentSize += 1
return True
def trickleUp(self,index):
parent = (index-1) / 2
bottom = self.heapArray[index]
while( index > 0 and self.heapArray[parent].getKey() < bottom.getKey() ):
self.heapArray[index] = self.heapArray[parent] # move it down
index = parent
parent = (parent-1) / 2
self.heapArray[index] = bottom
def remove(self): # delete item with max key
# (assumes non-empty list)
root = self.heapArray[0]
self.currentSize -= 1
self.heapArray[0] = self.heapArray[self.currentSize]
self.trickleDown(0)
return root
def trickleDown(self,index):
top = self.heapArray[index] # save root
while(index < self.currentSize/2): # while node has at
leftChild = 2*index+1
rightChild = leftChild+1 # find larger child
if(rightChild < self.currentSize and self.heapArray[leftChild].getKey() < self.heapArray[rightChild].getKey()):
largerChild = rightChild
else:
largerChild = leftChild
if( top.getKey() >= self.heapArray[largerChild].getKey() ):
break
# shift child up
self.heapArray[index] = self.heapArray[largerChild]
index = largerChild # go down
self.heapArray[index] = top # root to indexJava Code for Heaps
def change(self,index,newValue):
if(index<0 or index>=self.currentSize):
return False
oldValue = self.heapArray[index].getKey() # remember old
self.heapArray[index].setKey(newValue) # change to new
if(oldValue < newValue): # if raised,
trickleUp(index) # trickle it up
else: # if lowered,
trickleDown(index) # trickle it down
return True
def displayHeap(self):
print 'self.heapArray: ', # array format
for m in range(self.currentSize):
if(self.heapArray[m] != None):
print self.heapArray[m].getKey(),
else:
print '-- ' ,
print ''
nBlanks = 32
itemsPerRow = 1
column = 0
j = 0
# current item
dots = '...............................'
print dots+dots
# dotted top line
while(self.currentSize > 0):
if(column == 0):
for k in range(nBlanks):
print ' ' ,
print self.heapArray[j].getKey() ,
j += 1
if(j == self.currentSize):
break # done?
column += 1
if(column==itemsPerRow): # end of row?
nBlanks /= 2 # half the blanks
itemsPerRow *= 2 # twice the items
column = 0 # start over on
print ''
else: # next item on row
for k in range(nBlanks*2-2):
print ' ', # interim blanks
print '\n' +dots+dots
theHeap = Heap(31) # make a Heap max size 31
theHeap.insert(70)
theHeap.insert(40)
theHeap.insert(50)
theHeap.insert(20)
theHeap.insert(60)
theHeap.insert(100)
theHeap.insert(80)
theHeap.insert(30)
theHeap.insert(10)
theHeap.insert(90)
while(True):
print 'Enter first letter of show, insert, remove, change: ',
choice = raw_input()
if choice == 's':
theHeap.displayHeap()
elif choice == 'i':
print 'Enter value to key to insert: '
value = int(raw_input())
success = theHeap.insert(value)
if not success:
print "Can't insert heap full"
elif choice == 'f':
print 'Enter key value to find: ',
value = int(raw_input())
aDataItem = theHashTable.find(aKey)
if(aDataItem != None):
print 'Found ' , aKey
else:
print 'Could not find ' , aKey
elif choice=='r':
if not theHeap.isEmpty():
theHeap.remove()
else:
print "Can't remove heap empty"
elif choice=='c':
print 'Enter current index of item: ',
value = int(raw_input())
print "Enter new key: ",
value2 = int(raw_input())
success = theHeap.change(value, value2)
if( not success ):
print 'Invalid index'
else:
print "Invalid entry"
break
class Node:
def __init__(self,key):
# constructorJava Code for Heaps
self.iData = key
def getKey(self):
return self.iData
def setKey(self,i):
self.iData = i
class Heap:
def __init__(self,mx):
self.maxSize = mx
self.currentSize = 0
self.heapArray = []
for i in range(self.maxSize):
self.heapArray.append(Node(0))
def isEmpty(self):
return self.currentSize==0
def insert(self,key):
if(self.currentSize==self.maxSize):
return False
newNode = Node(key)
self.heapArray[self.currentSize] = newNode
self.trickleUp(self.currentSize)
self.currentSize += 1
return True
def remove(self): # delete item with max key
# (assumes non-empty list)
root = self.heapArray[0]
self.currentSize -= 1
self.heapArray[0] = self.heapArray[self.currentSize]
self.trickleDown(0)
return root
def trickleDown(self,index):
top = self.heapArray[index] # save root
while(index < self.currentSize/2): # while node has at
leftChild = 2*index+1
rightChild = leftChild+1 # find larger child
if(rightChild < self.currentSize and self.heapArray[leftChild].getKey() < self.heapArray[rightChild].getKey()):
largerChild = rightChild
else:
largerChild = leftChild
if( top.getKey() >= self.heapArray[largerChild].getKey() ):
break
# shift child up
self.heapArray[index] = self.heapArray[largerChild]
index = largerChild # go down
self.heapArray[index] = top # root to indexJava Code for Heaps
def displayHeap(self):
print 'self.heapArray: ', # array format
for m in range(self.currentSize):
if(self.heapArray[m] != None):
print self.heapArray[m].getKey(),
else:
print '-- ' ,
print ''
nBlanks = 32
itemsPerRow = 1
column = 0
j = 0
# current item
dots = '...............................'
print dots+dots
# dotted top line
while(self.currentSize > 0):
if(column == 0):
for k in range(nBlanks):
print ' ' ,
print self.heapArray[j].getKey() ,
j += 1
if(j == self.currentSize):
break # done?
column += 1
if(column==itemsPerRow): # end of row?
nBlanks /= 2 # half the blanks
itemsPerRow *= 2 # twice the items
column = 0 # start over on
print ''
else: # next item on row
for k in range(nBlanks*2-2):
print ' ', # interim blanks
print '\n' +dots+dots
def displayArray(self):
for j in range(self.maxSize):
print self.heapArray[j].getKey() ,
print ''
def insertAt(self,index,newNode):
self.heapArray[index] = newNode
def incrementSize(self):
self.currentSize += 1
print 'Enter number of items: ',
size = int(raw_input())
theHeap = Heap(size)
import random
for j in range(size): # fill array with
r = int(random.random()*100)
newNode = Node(r)
theHeap.insertAt(j, newNode)
theHeap.incrementSize()
print 'Random: ',
theHeap.displayArray() # display random array
j = size/2 - 1
while j >= 0:
theHeap.trickleDown(j)
j -= 1
print 'Heap: ',
theHeap.displayArray()
theHeap.displayHeap()
j = size - 1
while j >= 0:
biggestNode = theHeap.remove()
theHeap.insertAt(j, biggestNode)
j -= 1
print 'Sorted: ',
theHeap.displayArray()