{ "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": {} } ] }