CS110 Session 3.2 Pre-Class Work (Final)

CS110 Session 3.2 Pre-Class Work.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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "NAME = Steven Tey\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": {
    "deletable": false,
    "nbgrader": {
     "checksum": "b4db406d794de2ca2c0ee97172df6c5f",
     "grade": true,
     "grade_id": "cell-b1f821b034b44619",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "(Answer in comment).\n",
    "\n",
    "No, this is not a valid max heap, as some of the nodes are larger in value than their parents. For example, at the bottom level of the heap (height 0), both 92 and 76 are bigger than their parent, 16.\n",
    "\n",
    "To transform this into a valid max heap, we will have to perform a couple of transformations:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Therefore, the corresponding array that stores the valid max-heap is:\n",
    "\n",
    "(Answer in comment).\n",
    "\n",
    "`H_max_heap = [92, 85, 85, 76, 39, 30, 49, 16, 49, 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": [
    "A.heapsize is basically the number of elements inside the heap array. The local variable \"largest\" is basically a constantly iterating and updating variable that changes as the largest term floats up to the root of the heap."
   ]
  },
  {
   "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": 17,
   "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",
    "    return (2*i + 1)\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "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": 19,
   "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",
    "    return (2*i + 2)\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "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": 113,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "437f86fe310bc360e4cff404a25821e4",
     "grade": false,
     "grade_id": "cell-52289253a243341b",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def heapify(heap, i):\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    - heap: a list of floats. Assume that the heap size is the length of the heap.\n",
    "    \n",
    "    No output is needed. This function should modify (if necessary) heap in-place.\n",
    "    \"\"\"\n",
    "    largest = i #initialize the largest element as the root element\n",
    "    l = left(i) # from the video, we learned that left = 2*i + 1 \n",
    "    r = right(i) # from the video, we learned that right = 2*i + 1 \n",
    "    \n",
    "    if (l <= len(heap)-1 and heap[l] > heap[i]): # to check if left child of root exists and is greater than root \n",
    "        largest = l\n",
    "    else:\n",
    "        largest = i\n",
    "    if (r <= len(heap)-1 and heap[r] > heap[largest]): # to check if right child of root exists and is \n",
    "                                                     # greater than root \n",
    "        largest = r\n",
    "    if largest != i:\n",
    "        heap[i],heap[largest] = heap[largest],heap[i] # swap the roots, if needed\n",
    "            \n",
    "        heapify(heap, largest) #heapify the root (recurrence)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "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": "code",
   "execution_count": 115,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "A = [39, 85, 85, 16, 49, 7, 49, 92, 76, 15, 21, 30, 29, 31, 28]\n",
    "heapify(A,0)\n",
    "print(A == [85, 49, 85, 16, 39, 7, 49, 92, 76, 15, 21, 30, 29, 31, 28])"
   ]
  },
  {
   "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": 130,
   "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",
    "    \"\"\"\n",
    "    Input:\n",
    "    - A: a list of floats.\n",
    "    \n",
    "    No output is needed. The function should turn A into a valid max heap, in-place.\n",
    "    \"\"\"\n",
    "    for i in range((len(A)//2)+1, -1, -1):\n",
    "        heapify(A, i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "3ac35aff291e838fe69f72be6f27e762",
     "grade": true,
     "grade_id": "cell-5dc147b837da3f7e",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "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": "code",
   "execution_count": 133,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "A = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]\n",
    "build_max_heap(A)\n",
    "print(A == [16, 14, 10, 8, 7, 9, 3, 2, 4, 1])"
   ]
  },
  {
   "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": 134,
   "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",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    - heap: a list of floats. Assume that the heap size is the length of the heap.\n",
    "    \n",
    "    No output is needed. This function should modify (if necessary) heap in-place.\n",
    "    \"\"\"\n",
    "    smallest = i #initialize the largest element as the root element\n",
    "    l = left(i) # from the video, we learned that left = 2*i + 1 \n",
    "    r = right(i) # from the video, we learned that right = 2*i + 1 \n",
    "    \n",
    "    if (l <= len(heap)-1 and heap[l] < heap[i]): # to check if left child of root exists and is greater than root \n",
    "        smallest = i\n",
    "    else:\n",
    "        smallest = l\n",
    "    if (r <= len(heap)-1 and heap[r] < heap[smallest]): # to check if right child of root exists and is \n",
    "                                                     # greater than root \n",
    "        smallest = r\n",
    "    if smallest != i:\n",
    "        heap[i],heap[smallest] = heap[smallest],heap[i] # swap the roots, if needed\n",
    "            \n",
    "        min_heapify(heap, smallest) #heapify the root (recurrence)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "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(A):\n",
    "    \"\"\"\n",
    "    Input:\n",
    "    - A: a list of floats.\n",
    "    \n",
    "    No output is needed. The function should turn A into a valid min heap, in-place.\n",
    "    \"\"\"\n",
    "    for i in range((len(A)//2)+1, -1, -1):\n",
    "        min_heapify(A, i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}

The initial heap:

Step by step of the heap becoming a valid max heap