CS110 Heap structures

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 = \"Tiago Flora\"\n",
    "COLLABORATORS = [\"Ara Mkhoyan\",\"Chloe Gabrielle\"]"
   ]
  },
  {
   "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": [
    "## 1.\n",
    "The binary tree of H is not a valid max heap. It doesn't hold the max-heap property that every parent node should be larger than its children."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![img](https://i.ibb.co/SsCbTRd/CS110-3-2-1.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![img](https://i.ibb.co/9YYRMkd/CS110-3-2-2.jpg)\n",
    "![img](https://i.ibb.co/pRnG7xt/CS110-3-2-3.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.\n",
    "The max-heap version of the array H can be seen in step $k$ of the steps above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "H = [92,85,85,76,49,30,49,16,39,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": [
    "To any array that represents a heap, its heap-size refers to the amount of elements in the heap that are stored within the array. That is why it is used to check if elements to be operated on in the max-heapify algorithm are within the heap. <br>\n",
    "The variable \"largest\" is used to store the maximum value in a set of three nodes: one parent, and its two children. It is used to store the maximum value in the trio that should be moved to the lowest index value."
   ]
  },
  {
   "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": 60,
   "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",
    "    # Returns the index of the left child node\n",
    "    return(2*i+1) # Because Python indexes from 0, we add 1 to 2i to get the left child's index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "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": 62,
   "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",
    "    # Returns the index of the right child node\n",
    "    return(2*i+2) # To get the right index, we add 2 to 2i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "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": 97,
   "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",
    "    # We subtract 1 from the heap_size to avoid index errors\n",
    "    heap_size = len(heap)-1 # Alternatively, we could just use a strictly smaller (< instead of <=) comparison operator with r and l\n",
    "    l = left(i) # Define the left child node's index\n",
    "    r = right(i) # Define the right child node's index\n",
    "    if l <= heap_size and heap[l] > heap[i]: # Check if left child is in the heap and if it is larger than its parent\n",
    "        largest = l\n",
    "    else: # Keep parent node as largest\n",
    "        largest = i\n",
    "    if r <= heap_size and heap[r] > heap[largest]: # Check if right child is in the heap and if it's larger than its parent\n",
    "        largest = r\n",
    "    if largest != i: # In case the parent node does not contain the largest element, swap elements with the child node with the largest element\n",
    "        heap[i], heap[largest] = heap[largest], heap[i]\n",
    "        heapify(heap, largest) # Recursively call heapify until the parent is the largest node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "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": 81,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "3b25ccceae833d7b33202f027074e3d5",
     "grade": false,
     "grade_id": "cell-9237da6268a5e3eb",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "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(math.floor(len(A)/2), -1, -1): # We start from the highest-indexed non-leaf node and heapify from there until the first element\n",
    "        heapify(A, i) # \"Heapifies\" every branch of the heap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "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": "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": 102,
   "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",
    "    # The same rationale for max_heapify applies here for the indices\n",
    "    heap_size = len(heap)-1\n",
    "    l = left(i)\n",
    "    r = right(i)\n",
    "    if l <= heap_size and A[l] < A[i]: # We now check if a child node is smaller than its parent\n",
    "        smallest = l\n",
    "    else:\n",
    "        smallest = i\n",
    "    if r <= heap_size and heap[r] < heap[smallest]:\n",
    "        smallest = r\n",
    "    if smallest != i: # If the smallest is not the parent, swap elements and call the function recursively\n",
    "        heap[i], heap[smallest] = heap[smallest], heap[i]\n",
    "        min_heapify(heap, smallest)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "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(math.floor(len(A)/2), -1, -1): # We iterate from the last parent node up to the top one\n",
    "        min_heapify(A, i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 7, 9, 10, 14, 8, 16]"
      ]
     },
     "execution_count": 104,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]\n",
    "build_min_heap(A)\n",
    "A"
   ]
  },
  {
   "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
}