diff options
Diffstat (limited to 'Data_Structures_and_Algorithms_in_Java/ch12.ipynb')
| -rw-r--r-- | Data_Structures_and_Algorithms_in_Java/ch12.ipynb | 158 |
1 files changed, 158 insertions, 0 deletions
diff --git a/Data_Structures_and_Algorithms_in_Java/ch12.ipynb b/Data_Structures_and_Algorithms_in_Java/ch12.ipynb new file mode 100644 index 00000000..8343fffc --- /dev/null +++ b/Data_Structures_and_Algorithms_in_Java/ch12.ipynb @@ -0,0 +1,158 @@ +{ + "metadata": { + "name": "ch12" + }, + "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": "'''\nexample 12.1\ndemonstrates heaps\n'''\n\nclass 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\nclass 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\ntheHeap = Heap(31) # make a Heap max size 31\ntheHeap.insert(70)\ntheHeap.insert(40)\ntheHeap.insert(50)\ntheHeap.insert(20)\ntheHeap.insert(60)\ntheHeap.insert(100)\ntheHeap.insert(80)\ntheHeap.insert(30)\ntheHeap.insert(10)\ntheHeap.insert(90)\nwhile(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..............................................................\nEnter 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..............................................................\nEnter 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..............................................................\nEnter 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": "'''\nexample 12.2\ndemonstrates heap sort\n'''\nclass 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\nclass 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\nprint 'Enter number of items: ',\nsize = int(raw_input())\ntheHeap = Heap(size)\nimport random\nfor 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()\nprint 'Random: ',\ntheHeap.displayArray() # display random array\nj = size/2 - 1\nwhile j >= 0:\n theHeap.trickleDown(j)\n j -= 1\nprint 'Heap: ',\ntheHeap.displayArray()\ntheHeap.displayHeap()\nj = size - 1\nwhile j >= 0:\n biggestNode = theHeap.remove()\n theHeap.insertAt(j, biggestNode)\n j -= 1\n \nprint 'Sorted: ',\ntheHeap.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 \nHeap: 73 70 47 65 55 16 43 22 51 21 \nself.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..............................................................\nSorted: 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": {} + } + ] +}
\ No newline at end of file |