{
"metadata": {
"name": "",
"signature": "sha256:f213ff4fe3150e369b8ba77a058a36b9c6a812a3ac3196b559e262346daafa7b"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 1,
"metadata": {},
"source": [
"Chapter 12 : Heaps "
]
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Example 12.1 Page no : 592"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
" \n",
"class Node: \n",
" def __init__(self,key):\n",
" # constructorJava Code for Heaps\n",
" self.iData = key\n",
" \n",
" def getKey(self):\n",
" return self.iData\n",
"\n",
" def setKey(self,i):\n",
" self.iData = i\n",
"\n",
"class Heap:\n",
" def __init__(self,mx):\n",
" self.maxSize = mx\n",
" self.currentSize = 0\n",
" self.heapArray = []\n",
" for i in range(self.maxSize):\n",
" self.heapArray.append(Node(0))\n",
"\n",
" def isEmpty(self):\n",
" return self.currentSize==0\n",
"\n",
" def insert(self,key):\n",
" if(self.currentSize==self.maxSize):\n",
" return False\n",
" newNode = Node(key)\n",
" self.heapArray[self.currentSize] = newNode\n",
" self.trickleUp(self.currentSize)\n",
" self.currentSize += 1\n",
" return True\n",
"\n",
" def trickleUp(self,index):\n",
" parent = (index-1) / 2\n",
" bottom = self.heapArray[index]\n",
" while( index > 0 and self.heapArray[parent].getKey() < bottom.getKey() ):\n",
" self.heapArray[index] = self.heapArray[parent] # move it down\n",
" index = parent\n",
" parent = (parent-1) / 2\n",
" self.heapArray[index] = bottom\n",
"\n",
" def remove(self): # delete item with max key\n",
" # (assumes non-empty list)\n",
" root = self.heapArray[0]\n",
" self.currentSize -= 1\n",
" self.heapArray[0] = self.heapArray[self.currentSize]\n",
" self.trickleDown(0)\n",
" return root\n",
"\n",
" def trickleDown(self,index):\n",
" top = self.heapArray[index] # save root\n",
" while(index < self.currentSize/2): # while node has at\n",
" leftChild = 2*index+1\n",
" rightChild = leftChild+1 # find larger child\n",
" if(rightChild < self.currentSize and self.heapArray[leftChild].getKey() < self.heapArray[rightChild].getKey()):\n",
" largerChild = rightChild\n",
" else:\n",
" largerChild = leftChild\n",
" if( top.getKey() >= self.heapArray[largerChild].getKey() ):\n",
" break\n",
" # shift child up\n",
" self.heapArray[index] = self.heapArray[largerChild]\n",
" index = largerChild # go down\n",
"\n",
" self.heapArray[index] = top # root to indexJava Code for Heaps\n",
" \n",
" def change(self,index,newValue):\n",
" if(index<0 or index>=self.currentSize):\n",
" return False\n",
" oldValue = self.heapArray[index].getKey() # remember old\n",
" self.heapArray[index].setKey(newValue) # change to new\n",
" if(oldValue < newValue): # if raised,\n",
" trickleUp(index) # trickle it up\n",
" else: # if lowered,\n",
" trickleDown(index) # trickle it down\n",
" return True\n",
"\n",
" def displayHeap(self):\n",
" print 'self.heapArray: ', # array format\n",
" for m in range(self.currentSize):\n",
" if(self.heapArray[m] != None):\n",
" print self.heapArray[m].getKey(),\n",
" else:\n",
" print '-- ' ,\n",
" print ''\n",
" nBlanks = 32\n",
" itemsPerRow = 1\n",
" column = 0\n",
" j = 0\n",
" # current item\n",
" dots = '...............................'\n",
" print dots+dots\n",
" # dotted top line\n",
" while(self.currentSize > 0):\n",
" if(column == 0):\n",
" for k in range(nBlanks):\n",
" print ' ' ,\n",
" print self.heapArray[j].getKey() ,\n",
" j += 1 \n",
" if(j == self.currentSize):\n",
" break # done?\n",
" column += 1\n",
" if(column==itemsPerRow): # end of row?\n",
" nBlanks /= 2 # half the blanks\n",
" itemsPerRow *= 2 # twice the items\n",
" column = 0 # start over on\n",
" print ''\n",
" else: # next item on row\n",
" for k in range(nBlanks*2-2):\n",
" print ' ', # interim blanks\n",
" print '\\n' +dots+dots \n",
"\n",
"theHeap = Heap(31) # make a Heap max size 31\n",
"theHeap.insert(70)\n",
"theHeap.insert(40)\n",
"theHeap.insert(50)\n",
"theHeap.insert(20)\n",
"theHeap.insert(60)\n",
"theHeap.insert(100)\n",
"theHeap.insert(80)\n",
"theHeap.insert(30)\n",
"theHeap.insert(10)\n",
"theHeap.insert(90)\n",
"while(True):\n",
" print 'Enter first letter of show, insert, remove, change: ',\n",
" choice = raw_input()\n",
" if choice == 's':\n",
" theHeap.displayHeap()\n",
" elif choice == 'i':\n",
" print 'Enter value to key to insert: '\n",
" value = int(raw_input())\n",
" success = theHeap.insert(value)\n",
" if not success:\n",
" print \"Can't insert heap full\"\n",
" elif choice == 'f':\n",
" print 'Enter key value to find: ',\n",
" value = int(raw_input())\n",
" aDataItem = theHashTable.find(aKey)\n",
" if(aDataItem != None):\n",
" print 'Found ' , aKey\n",
" else:\n",
" print 'Could not find ' , aKey\n",
" elif choice=='r':\n",
" if not theHeap.isEmpty():\n",
" theHeap.remove()\n",
" else:\n",
" print \"Can't remove heap empty\"\n",
" elif choice=='c':\n",
" print 'Enter current index of item: ',\n",
" value = int(raw_input())\n",
" print \"Enter new key: \",\n",
" value2 = int(raw_input())\n",
" success = theHeap.change(value, value2)\n",
" if( not success ):\n",
" print 'Invalid index'\n",
" else:\n",
" print \"Invalid entry\"\n",
" break "
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
" Enter first letter of show, insert, remove, change: "
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"s\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
" self.heapArray: 100 90 80 30 60 50 70 20 10 40 \n",
"..............................................................\n",
" 100 \n",
" 90 80 \n",
" 30 60 50 70 \n",
" 20 10 40 \n",
"..............................................................\n",
"Enter first letter of show, insert, remove, change: "
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"i\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
" Enter value to key to insert: \n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"53\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter first letter of show, insert, remove, change: "
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"s\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
" self.heapArray: 100 90 80 30 60 50 70 20 10 40 53 \n",
"..............................................................\n",
" 100 \n",
" 90 80 \n",
" 30 60 50 70 \n",
" 20 10 40 53 \n",
"..............................................................\n",
"Enter first letter of show, insert, remove, change: "
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"r\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
" Enter first letter of show, insert, remove, change: "
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"s\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
" self.heapArray: 90 60 80 30 53 50 70 20 10 40 \n",
"..............................................................\n",
" 90 \n",
" 60 80 \n",
" 30 53 50 70 \n",
" 20 10 40 \n",
"..............................................................\n",
"Enter first letter of show, insert, remove, change: "
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
" Invalid entry\n"
]
}
],
"prompt_number": 2
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Example 12.2 Page no : 605"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
" \n",
"class Node: \n",
" def __init__(self,key):\n",
" # constructorJava Code for Heaps\n",
" self.iData = key\n",
" \n",
" def getKey(self):\n",
" return self.iData\n",
"\n",
" def setKey(self,i):\n",
" self.iData = i\n",
"\n",
"class Heap:\n",
" def __init__(self,mx):\n",
" self.maxSize = mx\n",
" self.currentSize = 0\n",
" self.heapArray = []\n",
" for i in range(self.maxSize):\n",
" self.heapArray.append(Node(0))\n",
"\n",
" def isEmpty(self):\n",
" return self.currentSize==0\n",
"\n",
" def insert(self,key):\n",
" if(self.currentSize==self.maxSize):\n",
" return False\n",
" newNode = Node(key)\n",
" self.heapArray[self.currentSize] = newNode\n",
" self.trickleUp(self.currentSize)\n",
" self.currentSize += 1\n",
" return True\n",
"\n",
" def remove(self): # delete item with max key\n",
" # (assumes non-empty list)\n",
" root = self.heapArray[0]\n",
" self.currentSize -= 1\n",
" self.heapArray[0] = self.heapArray[self.currentSize]\n",
" self.trickleDown(0)\n",
" return root\n",
"\n",
" def trickleDown(self,index):\n",
" top = self.heapArray[index] # save root\n",
" while(index < self.currentSize/2): # while node has at\n",
" leftChild = 2*index+1\n",
" rightChild = leftChild+1 # find larger child\n",
" if(rightChild < self.currentSize and self.heapArray[leftChild].getKey() < self.heapArray[rightChild].getKey()):\n",
" largerChild = rightChild\n",
" else:\n",
" largerChild = leftChild\n",
" if( top.getKey() >= self.heapArray[largerChild].getKey() ):\n",
" break\n",
" # shift child up\n",
" self.heapArray[index] = self.heapArray[largerChild]\n",
" index = largerChild # go down\n",
" self.heapArray[index] = top # root to indexJava Code for Heaps\n",
"\n",
" def displayHeap(self):\n",
" print 'self.heapArray: ', # array format\n",
" for m in range(self.currentSize):\n",
" if(self.heapArray[m] != None):\n",
" print self.heapArray[m].getKey(),\n",
" else:\n",
" print '-- ' ,\n",
" print ''\n",
" nBlanks = 32\n",
" itemsPerRow = 1\n",
" column = 0\n",
" j = 0\n",
" # current item\n",
" dots = '...............................'\n",
" print dots+dots\n",
" # dotted top line\n",
" while(self.currentSize > 0):\n",
" if(column == 0):\n",
" for k in range(nBlanks):\n",
" print ' ' ,\n",
" print self.heapArray[j].getKey() ,\n",
" j += 1 \n",
" if(j == self.currentSize):\n",
" break # done?\n",
" column += 1\n",
" if(column==itemsPerRow): # end of row?\n",
" nBlanks /= 2 # half the blanks\n",
" itemsPerRow *= 2 # twice the items\n",
" column = 0 # start over on\n",
" print ''\n",
" else: # next item on row\n",
" for k in range(nBlanks*2-2):\n",
" print ' ', # interim blanks\n",
" print '\\n' +dots+dots \n",
" \n",
" def displayArray(self):\n",
" for j in range(self.maxSize):\n",
" print self.heapArray[j].getKey() ,\n",
" print ''\n",
"\n",
" def insertAt(self,index,newNode):\n",
" self.heapArray[index] = newNode\n",
"\n",
" def incrementSize(self):\n",
" self.currentSize += 1\n",
"\n",
"\n",
"print 'Enter number of items: ',\n",
"size = int(raw_input())\n",
"theHeap = Heap(size)\n",
"import random\n",
"for j in range(size): # fill array with\n",
" r = int(random.random()*100)\n",
" newNode = Node(r)\n",
" theHeap.insertAt(j, newNode)\n",
" theHeap.incrementSize()\n",
"print 'Random: ',\n",
"theHeap.displayArray() # display random array\n",
"j = size/2 - 1\n",
"while j >= 0:\n",
" theHeap.trickleDown(j)\n",
" j -= 1\n",
"print 'Heap: ',\n",
"theHeap.displayArray()\n",
"theHeap.displayHeap()\n",
"j = size - 1\n",
"while j >= 0:\n",
" biggestNode = theHeap.remove()\n",
" theHeap.insertAt(j, biggestNode)\n",
" j -= 1\n",
" \n",
"print 'Sorted: ',\n",
"theHeap.displayArray()"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter number of items: "
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"10\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
" Random: 21 55 43 65 70 16 47 22 51 73 \n",
"Heap: 73 70 47 65 55 16 43 22 51 21 \n",
"self.heapArray: 73 70 47 65 55 16 43 22 51 21 \n",
"..............................................................\n",
" 73 \n",
" 70 47 \n",
" 65 55 16 43 \n",
" 22 51 21 \n",
"..............................................................\n",
"Sorted: 16 21 22 43 47 51 55 65 70 73 \n"
]
}
],
"prompt_number": 3
},
{
"cell_type": "code",
"collapsed": false,
"input": [],
"language": "python",
"metadata": {},
"outputs": []
}
],
"metadata": {}
}
]
}