cs110_pcw_3_2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before you turn this problem in, make sure everything runs as expected. First, **restart the kernel** (in the menubar, select Kernel$\\rightarrow$Restart) and then **run all cells** (in the menubar, select Cell$\\rightarrow$Run All).\n",
    "\n",
    "Make sure you fill in any place that says `YOUR CODE HERE` or \"YOUR ANSWER HERE\", as well as your name and collaborators below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "NAME = \"Verina Armanyous\"\n",
    "COLLABORATORS = \"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "1090720698e48f7dfc9df7cd4b80574c",
     "grade": false,
     "grade_id": "cell-7eb07d86e7defd94",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# CS110 Pre-class Work 3.2\n",
    "\n",
    "## Question 1.\n",
    "Given the array `H=[39, 85, 85, 16, 49, 7, 49, 92, 76, 15, 21, 30, 29, 31, 28]`, perform the following operations:\n",
    "1. Draw the corresponding binary tree of H. Is the binary tree a valid max heap? Explain your answer.\n",
    "2. Using as a model the drawing examples illustrated in Figure 6.2 of Cormen et al.,  draw a step-by-step transformation of the array above into a valid max heap. \n",
    "3. Now that you have obtained a valid max heap, write out the corresponding array that stores the valid max-heap.\n",
    "\n",
    "Use as many cells as you wish for this question."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1- That's not a valid max heap because not all the parent nodes are greater than the child nodes. For instance, we see that the root of the tree is \"39\" which is less than the two child nodes \"85\", and \"85\". Also, we can see that the condition for the max heap which is all child nodes are supposed to be less than or equal the parent node is not meet among all nodes of the tree. And that is why this tree isn't a valid max heap."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "b4db406d794de2ca2c0ee97172df6c5f",
     "grade": true,
     "grade_id": "cell-b1f821b034b44619",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "![title](firstheap.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2-A step-by-step transformation of the array above into a valid max heap. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![title](secondheap.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![title](thirdheap.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![title](fourheap.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![title](final.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3- The corresponding array that stores the valid max-heap, arr= [85,49,85,92,39,30,49,16,76,15,21,7,29,31,28]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "5f4f7806e0dca417bbd35743ff694dee",
     "grade": false,
     "grade_id": "cell-1d9ef3625bdd556d",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 2. \n",
    "Consider the following questions on the $MAX-HEAPIFY$ operation.\n",
    "### Question 2a.\n",
    "\n",
    "In the pseudocode of $MAX-HEAPIFY$ (Cormen et al., p.154, or you can view it [here](https://drive.google.com/open?id=1e_3jsX4-qQCfZXKMok_T6LPFh9FwtmT5)), what does A.heap-size mean and what is the idea behind the local variable largest? \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "8d8b7cdabce48f4b8b4429ea7fafe13a",
     "grade": true,
     "grade_id": "cell-06106b81a909b9e6",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "The heap-size represents the no. of elements in the heap that are sorted in the array. It could be within the range of 0<= heap size <= length of a list. \n",
    "\n",
    "The variable largest stores the index of the largest element among the right, left and parent at each step."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "b85f44c1afefc375fc36d41458e9e8da",
     "grade": false,
     "grade_id": "cell-c274a369170d9c75",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### Question 2b.\n",
    "The functions $LEFT(i)$ and $RIGHT(i)$, lines 1 and 2 in the $MAX-HEAPIFY$ pseudocode, return the array index of the left and right child, respectively, of a node in a binary tree. From reading Section 6.1, you know that the input to both functions is an integer number, $i$, which corresponds to the array index of the parent node in the array. Review Section 6.1 for more information. Write a Python implementation of the functions $LEFT(i)$ and $RIGHT(i)$ by filling in the cells below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "de40c348d2617b4d3e44fae18c1389ce",
     "grade": false,
     "grade_id": "cell-2efd4017321c8d48",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def left(i):\n",
    "    l= (2*i)+1\n",
    "    return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "a7a9d607eb7f71f1151b83972ff0c0fb",
     "grade": true,
     "grade_id": "cell-507ddbab62e6a32c",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Please ignore this cell. This cell is for us to implement the tests \n",
    "# to see if your code works properly. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "9cb29b6fcee2e02b85efad7065632bd9",
     "grade": false,
     "grade_id": "cell-b7e5ceeacaeaf1b8",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def right(i):\n",
    "    r = (2*i) +2\n",
    "    return r \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "db02f794412224105f1ddc365ed7d2b9",
     "grade": true,
     "grade_id": "cell-c24867515653788a",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Please ignore this cell. This cell is for us to implement the tests \n",
    "# to see if your code works properly. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "6b956caaed539971565797cd7b977fb4",
     "grade": false,
     "grade_id": "cell-ede2c6c59d13f051",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### Question 2c.\n",
    "Write a Python implementation of the MAX-HEAPIFY operation using the pseudocode above, and your newly written functions, `left` and `right`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "437f86fe310bc360e4cff404a25821e4",
     "grade": false,
     "grade_id": "cell-52289253a243341b",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def heapify(A, i): #heap is the array and i is the index of the parent\n",
    "    l = left(i) # find the index of the left child\n",
    "    r = right(i) #find the index of the right child\n",
    "    largest = 0 #initialize the variable largest\n",
    "    #that will later hold the largest value among the parent, left child, and right child\n",
    "    if A[l]>A[i] and l < len(A): #if the left child is larger than the parent\n",
    "        largest = l #assign the index of the left child to the variable largest\n",
    "    else: \n",
    "        largest = i #otherwise assign the index (i) of the parent to the variable largest\n",
    "    if A[r] > A[largest] and r < len(A): # if the right child is larger than the value of the \n",
    "        #element that has index \"largest\"\n",
    "        largest = r #assign the index of the right child to the variable largest\n",
    "    if largest != i: #if the variable largest is not equal the parent \n",
    "        A[i], A[largest] = A[largest], A[i] # then swap the parent with the largest value\n",
    "        heapify (A, largest) #recursion: calling the function to do the same but with the new index\n",
    "    \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "1324f2f1d6c279abfbb60df89bb4503e",
     "grade": true,
     "grade_id": "cell-7f63745ff34b881b",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "A = [39, 85, 85, 16, 49, 7, 49, 92, 76, 15, 21, 30, 29, 31, 28]\n",
    "heapify(A,0)\n",
    "assert(A == [85, 49, 85, 16, 39, 7, 49, 92, 76, 15, 21, 30, 29, 31, 28])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "f3fbda39f18c774ac14e5c959b90370b",
     "grade": false,
     "grade_id": "cell-d2e6b91e47491b21",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 3. \n",
    "Next, write a Python implementation of the BUILD_MAX_HEAP operation using the pseudocode provided in Section 6.3 of Cormen et. al. Test your Python implementation using the array in problem 1, and make sure your Python codes produce a valid max heap."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "3b25ccceae833d7b33202f027074e3d5",
     "grade": false,
     "grade_id": "cell-9237da6268a5e3eb",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def build_max_heap(A):\n",
    "    #call heapify for each element in the array moving backwards and starting from the last element \n",
    "    for i in range(len(A),-1,-1):\n",
    "        heapify(A,i)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "3ac35aff291e838fe69f72be6f27e762",
     "grade": true,
     "grade_id": "cell-5dc147b837da3f7e",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "ename": "IndexError",
     "evalue": "list index out of range",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mIndexError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-9-ee91f00716e1>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0mA\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;36m4\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m3\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m16\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m9\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m10\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m14\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m8\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m7\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0mbuild_max_heap\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mA\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      3\u001b[0m \u001b[0;32massert\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mA\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;36m16\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m14\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m10\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m8\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m7\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m9\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m3\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m4\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-8-34f62cc7bc70>\u001b[0m in \u001b[0;36mbuild_max_heap\u001b[0;34m(A)\u001b[0m\n\u001b[1;32m      2\u001b[0m     \u001b[0;31m#call heapify for each element in the array moving backwards and starting from the last element\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mA\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m         \u001b[0mheapify\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mA\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      5\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-6-bc4090af7142>\u001b[0m in \u001b[0;36mheapify\u001b[0;34m(A, i)\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mlargest\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m0\u001b[0m \u001b[0;31m#initialize the variable largest\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m     \u001b[0;31m#that will later hold the largest value among the parent, left child, and right child\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m     \u001b[0;32mif\u001b[0m \u001b[0mA\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m>\u001b[0m\u001b[0mA\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;32mand\u001b[0m \u001b[0ml\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mA\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;31m#if the left child is larger than the parent\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      7\u001b[0m         \u001b[0mlargest\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0ml\u001b[0m \u001b[0;31m#assign the index of the left child to the variable largest\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      8\u001b[0m     \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mIndexError\u001b[0m: list index out of range"
     ]
    }
   ],
   "source": [
    "A = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]\n",
    "build_max_heap(A)\n",
    "assert(A == [16, 14, 10, 8, 7, 9, 3, 2, 4, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hi professor! it says index error: list index out of range. I tired debugging it by checking that I have the correct indices in the code but couldn't make it work. So, why does it say that and how can I fix it?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "c996bb21edeef2d4946ddd03b78159ea",
     "grade": false,
     "grade_id": "cell-8fa5348173dad225",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 4. \n",
    "\n",
    "Lastly, write Python implementations of the $MIN-HEAPIFY$ and $BUILD-MIN-HEAP$ operations for a min heap data structure. You can use your $MAX-HEAPIFY$ and $BUILD-MAX-HEAP$ Python function as models, just remember that the latter two functions support operations for the max heap data structure. Test your Python implementation of $BUILD-MIN-HEAP$ using the array in problem 1, and make sure your Python codes produce a valid min heap. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "2d3d509af26d1c25fa2caa6b4f02d337",
     "grade": false,
     "grade_id": "cell-d86943f127876fc8",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def min_heapify(heap, i):\n",
    "    l = left(i) # find the index of the left child\n",
    "    r = right(i) #find the index of the right child\n",
    "    smallest = 0 #initialize the variable largest\n",
    "    #that will later hold the smallest value among the parent, left child, and right child\n",
    "    if heap[l]<heap[i] and l < len(heap): #if the left child is smaller than the parent\n",
    "        smallest = l #assign the index of the left child to the variable largest\n",
    "    else: \n",
    "        smallest = i #otherwise assign the index (i) of the parent to the variable largest\n",
    "    if heap[r] < heap[smallest] and r < len(heap): # if the right child is smaller than the value \n",
    "        #of the element that has index \"smallest\"\n",
    "        smallest = r #assign the index of the right child to the variable smallest\n",
    "    if smallest != i: #if the variable smallest is not equal the parent \n",
    "        heap[i], heap[smallest] = heap[smallest], heap[i] # then swap the parent with the smallest value\n",
    "        #min_heapify (heap, smallest) #recursion: calling the function to do the same but with the new index\n",
    " \n",
    "    return heap,smallest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "#The code worked well when I commented the recurssion part (the last line of code before the return).\n",
    "#However when it was part of the code it showed an error, and I tried to figure out \n",
    "#the reason behind it but I couln't solve the error. It said in the error message \n",
    "#that the function is out of range, but it seemed fine to me when I used paper to \n",
    "#visualize the implementation of the code. So, I was wondering why that happened. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "f066ec74b8334b1177c123b51b68e53b",
     "grade": false,
     "grade_id": "cell-6efa45e3956ad0b8",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def build_min_heap(heap):\n",
    "    #call min heapify for each element moving backwards starting from \n",
    "    #the end of the list \n",
    "    for i in range(len(heap),-1,-1):\n",
    "        min_heapify(heap,i)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "8645e43d1c1d94c49a14c4e624488ef6",
     "grade": true,
     "grade_id": "cell-7e64941402f819c2",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Please ignore this cell. This cell is for us to implement the tests \n",
    "# to see if your code works properly. "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}