Chapter 12 : Heaps

Example 12.1 Page no : 592

In [2]:
 
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        
 Enter first letter of show, insert, remove, change: s
 self.heapArray:  100 90 80 30 60 50 70 20 10 40 
..............................................................
                                                                100 
                                90                                                             80 
                30                             60                             50                             70 
        20             10             40 
..............................................................
Enter first letter of show, insert, remove, change: i
 Enter value to key to insert: 
53
Enter first letter of show, insert, remove, change: s
 self.heapArray:  100 90 80 30 60 50 70 20 10 40 53 
..............................................................
                                                                100 
                                90                                                             80 
                30                             60                             50                             70 
        20             10             40             53 
..............................................................
Enter first letter of show, insert, remove, change: r
 Enter first letter of show, insert, remove, change: s
 self.heapArray:  90 60 80 30 53 50 70 20 10 40 
..............................................................
                                                                90 
                                60                                                             80 
                30                             53                             50                             70 
        20             10             40 
..............................................................
Enter first letter of show, insert, remove, change: 
 Invalid entry

Example 12.2 Page no : 605

In [3]:
 
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()
Enter number of items: 10
 Random:  21 55 43 65 70 16 47 22 51 73 
Heap:  73 70 47 65 55 16 43 22 51 21 
self.heapArray:  73 70 47 65 55 16 43 22 51 21 
..............................................................
                                                                73 
                                70                                                             47 
                65                             55                             16                             43 
        22             51             21 
..............................................................
Sorted:  16 21 22 43 47 51 55 65 70 73 
In [ ]: