steven-tey · September 30, 2019 15:59
diff --git a/CS110 Session 4.1 Pre-Class Work.ipynb b/CS110 Session 4.1 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": "274b43d88d65df3de28733d850616dca",
     "grade": false,
     "grade_id": "cell-3f3ec0504e39b023",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# CS110 Pre-class Work 4.1\n",
    "\n",
    "## Question 1. (Exercise 6.5-1 from Cormen et al.)\n",
    "\n",
    "Illustrate the operation of $HEAP-EXTRACT-MAX$ on the heap $A= \\langle 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1 \\rangle$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "a7f20996d6e22ca2d544500769888784",
     "grade": true,
     "grade_id": "cell-7de130b1caacd3ab",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "The operation$HEAP-EXTRACT-MAX$ first checks the length of heap A to make sure that it is smaller than 1 (contains no elements). We know that heap A is a max heap, and therefoer the first element is the biggest element. Thus, the operation assigns the key in the first index (15) as the ``max`` value. It then replaces 15 with the element in the last index, 1. Then, it reduces the length of the heap by 1. Lastly, it performs the function $MAX-HEAPIFY$ on the new heap to make it into a max heap again. The max element, in this case 15, is returned."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "d60dd22e7498fab87e01bedd8064d513",
     "grade": false,
     "grade_id": "cell-6cb98701e5a82f6b",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 2. (Exercise 6.5-2 from Cormen et al.)\n",
    "\n",
    "Illustrate the operation of $MAX-HEAP-INSERT(A, 10)$ on the heap $A=\\langle 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1\\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "3652f0e0f430ec440dd4899558426c74",
     "grade": true,
     "grade_id": "cell-74f212522535433a",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "The operation $MAX-HEAP-INSERT(A, 10)$ first increases the length of heap A by 1, and assigns the new index with the sentinel value of $-\\infty$. It then performs the $HEAP-INCREASE-KEY(A, i, key)$ on the new heap, with $i$ being the length of heap A (12) and $key$ being 10 . What this function does is it first checks if the key is smaller than the value at the last index of heap A, which is impossible, because that last value is $-\\infty$. It then replaces the $-\\infty$ value at the last position with the key, 10, and then performs a while loop that does the following:\n",
    "\n",
    "While $i$ is larger than 1 (descending order) and the value of the parent of the number with index $i$ is smaller than the number with index $i$ itself, the algorithm will exchange the number with its parent. Now, we assign the parent index to the original child index $i$. \n",
    "\n",
    "Basically what this does is it's doing $MAX-HEAPIFY$ again to get the new number 10 all the way up where it should be positioned in the max heap."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "a986c9c7d690f05369df23660265d2a0",
     "grade": false,
     "grade_id": "cell-65c8d2b5e2e9deff",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 3. Implementing Priority Queues Using Max and Min Heap Data Structures \n",
    "\n",
    "The next cell contains a Python implementation of a very basic priority queue based on a max heap data structure.<br>\n",
    "Please read and follow the <b>Instructions and Tasks</b> that are included below the next cell. These instructions and exercises will guide you through the Python code (i.e., <i><b>skip the Python code for now</b></i> and first proceed to read the instructions below the cell containing the Python code.) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "dae9240440201b16c0ddd0180b223363",
     "grade": false,
     "grade_id": "cell-834cafc3878bd920",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# \n",
    "# Defining some basic binary tree functions\n",
    "#\n",
    "def left(i):         # left(i): takes as input the array index of a parent node in the binary tree and \n",
    "    return 2*i + 1   #          returns the array index of its left child.\n",
    "\n",
    "def right(i):        # right(i): takes as input the array index of a parent node in the binary tree and \n",
    "    return 2*i + 2   #           returns the array index of its right child.\n",
    "\n",
    "def parent(i):       # parent(i): takes as input the array index of a node in the binary tree and\n",
    "    return (i-1)//2  #            returns the array index of its parent\n",
    "\n",
    "\n",
    "# Defining the Python class MaxHeapq to implement a max heap data structure.\n",
    "# Every Object in this class has two attributes:\n",
    "#           - heap : A Python list where key values in the max heap are stored\n",
    "#           - heap_size: An integer counter of the number of keys present in the max heap\n",
    "class MaxHeapq:\n",
    "    \"\"\" \n",
    "    This class implements properties and methods that support a max priority queue data structure\n",
    "    \"\"\"  \n",
    "    # Class initialization method. Use: heapq_var = MaxHeapq()\n",
    "    def __init__(self):        \n",
    "        self.heap       = []\n",
    "        self.heap_size  = 0\n",
    "\n",
    "    # This method returns the highest key in the priority queue. \n",
    "    #   Use: key_var = heapq_var.max()\n",
    "    def maxk(self):              \n",
    "        return self.heap[0]     \n",
    "    \n",
    "    # This method implements the INSERT key into a priority queue operation\n",
    "    #   Use: heapq_var.heappush(key)\n",
    "    def heappush(self, key):   \n",
    "        \"\"\"\n",
    "        Inserts the value of key onto the priority queue, maintaining the max heap invariant.\n",
    "        \"\"\"\n",
    "        self.heap.append(-float(\"inf\"))\n",
    "        self.increase_key(self.heap_size,key)\n",
    "        self.heap_size+=1\n",
    "        \n",
    "    # This method implements the INCREASE_KEY operation, which modifies the value of a key\n",
    "    # in the max priority queue with a higher value. \n",
    "    #   Use heapq_var.increase_key(i, new_key)\n",
    "    def increase_key(self, i, key): \n",
    "        if key < self.heap[i]:\n",
    "            raise ValueError('new key is smaller than the current key')\n",
    "        self.heap[i] = key\n",
    "        while i > 0 and self.heap[parent(i)] < self.heap[i]:\n",
    "            j = parent(i)\n",
    "            holder = self.heap[j]\n",
    "            self.heap[j] = self.heap[i]\n",
    "            self.heap[i] = holder\n",
    "            i = j    \n",
    "            \n",
    "    # This method implements the MAX_HEAPIFY operation for the max priority queue. The input is \n",
    "    # the array index of the root node of the subtree to be heapify.\n",
    "    #   Use heapq_var.heapify(i)        \n",
    "    def heapify(self, i):\n",
    "        l = left(i)\n",
    "        r = right(i)\n",
    "        heap = self.heap\n",
    "        if l <= (self.heap_size-1) and heap[l]>heap[i]:\n",
    "            largest = l\n",
    "        else:\n",
    "            largest = i\n",
    "        if r <= (self.heap_size-1) and heap[r] > heap[largest]:\n",
    "            largest = r\n",
    "        if largest != i:\n",
    "            heap[i], heap[largest] = heap[largest], heap[i]\n",
    "            self.heapify(largest)\n",
    "\n",
    "    # This method implements the EXTRACT_MAX operation. It returns the largest key in \n",
    "    # the max priority queue and removes this key from the max priority queue.\n",
    "    #   Use key_var = heapq_var.heappop() \n",
    "    def heappop(self):\n",
    "        if self.heap_size < 1:\n",
    "            raise ValueError('Heap underflow: There are no keys in the priority queue ')\n",
    "        maxk = self.heap[0]\n",
    "        self.heap[0] = self.heap[-1]\n",
    "        self.heap.pop()\n",
    "        self.heap_size-=1\n",
    "        self.heapify(0)\n",
    "        return maxk"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "0fe80b7551c447558abc43ec307de37e",
     "grade": false,
     "grade_id": "cell-2462e8ce46926058",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Instructions and Tasks.\n",
    "The goal of these tasks is for you to learn how to implement, build, and manage priority queues in Python. \n",
    "\n",
    "First, let us practice building a max priority queue from a random list of keys.<br> \n",
    "For example, given a list of keys: [4,3,6,8,2,-5,100], we want to obtain a max priority queue that looks like this: [100, 6, 8, 3, 2, -5, 4], recall that in a max priority list the highest key should be on top (given priority). \n",
    "\n",
    "### Task 0.\n",
    "Check whether the list [100, 6, 8, 3, 2, -5, 4] is indeed a max priority queue. Recall that a max priority queue data structure is based on a max heap data structure. Give a short explanation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "d96ebcf5802ceeb1a33e34c5a5afe211",
     "grade": true,
     "grade_id": "cell-5e0b898075b25073",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "Yes, the list [100, 6, 8, 3, 2, -5, 4] is indeed a max priority queue. If we draw it out, it resembles a max heap, with the biggest element at the very top of the heap and all the child elements are smaller than their parent element in the heap. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "0a9b4ea61e7caa5bbeb1fa79575f31f9",
     "grade": false,
     "grade_id": "cell-01e1945386d515a2",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### Task 1.\n",
    "The following cell uses the Python implementation of a max priority queue. This a good time to review the Python code above and then follow the rest of these instructions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "da3a43089e2db1466a2db091855b07e0",
     "grade": false,
     "grade_id": "cell-e301a5a468f9b84e",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[100, 6, 8, 3, 2, -5, 4]\n"
     ]
    }
   ],
   "source": [
    "# GOAL: BUILD HEAP FROM [4,3,6,8,2,-5,100]\n",
    "#   Study the following lines of code, execute the cell and make sure you understand how the\n",
    "#   Python implementation of the MaxHeapq is used here and the output from these lines.\n",
    "A = [4,3,6,8,2,-5,100]\n",
    "my_heap = MaxHeapq()\n",
    "\n",
    "for key in A:\n",
    "    my_heap.heappush(key)\n",
    "\n",
    "print(my_heap.heap)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "c3ea1d8efdd3151a6a3bb4f027f292b7",
     "grade": false,
     "grade_id": "cell-cf7dd96ee4eb3c43",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### Task 2. \n",
    "Given the list [6,4,7,9,10,-5,-6,12,8,3,1,-10], build a max heap. You should store the Python list that represents the max heap in a variable named `my_heap_list`.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "5cfb440b6fd86152d8ec5aaf1b166156",
     "grade": false,
     "grade_id": "cell-8f1991aebb9ab87c",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[12, 10, 6, 9, 7, -5, -6, 4, 8, 3, 1, -10]\n"
     ]
    }
   ],
   "source": [
    "B = [6,4,7,9,10,-5,-6,12,8,3,1,-10]\n",
    "my_heap_list = MaxHeapq()\n",
    "\n",
    "for key in B:\n",
    "    my_heap_list.heappush(key)\n",
    "\n",
    "print(my_heap_list.heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "26429f9e44e6cc1038e2742a4d470879",
     "grade": true,
     "grade_id": "cell-fa85b4b29f6da1af",
     "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": "9f8056e40f22478e49e5dbf9b316cb44",
     "grade": false,
     "grade_id": "cell-630703ffa2b4b776",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### Task 3.\n",
    "Using the Python code that implements the class `MaxHeapq` as a reference, build a class `MinHeapq`, a min priority queue. Your class should contain the following method: `mink`, `heappush`, `decrease_key`, `heapify`, and `heappop`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "0cd32eb273c3524ad096e0817d58fac3",
     "grade": false,
     "grade_id": "cell-927eee0091ce8d12",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# \n",
    "# Defining some basic binary tree functions\n",
    "#\n",
    "def left(i):         # left(i): takes as input the array index of a parent node in the binary tree and \n",
    "    return 2*i + 1   #          returns the array index of its left child.\n",
    "\n",
    "def right(i):        # right(i): takes as input the array index of a parent node in the binary tree and \n",
    "    return 2*i + 2   #           returns the array index of its right child.\n",
    "\n",
    "def parent(i):       # parent(i): takes as input the array index of a node in the binary tree and\n",
    "    return (i-1)//2  #            returns the array index of its parent\n",
    "\n",
    "\n",
    "# Defining the Python class MinHeapq to implement a min heap data structure.\n",
    "# Every Object in this class has two attributes:\n",
    "#           - heap : A Python list where key values in the min heap are stored\n",
    "#           - heap_size: An integer counter of the number of keys present in the min heap\n",
    "class MinHeapq:\n",
    "    \"\"\" \n",
    "    This class implements properties and methods that support a max priority queue data structure\n",
    "    \"\"\"  \n",
    "    # Class initialization method. Use: heapq_var = MaxHeapq()\n",
    "    def __init__(self):        \n",
    "        self.heap       = []\n",
    "        self.heap_size  = 0\n",
    "\n",
    "    # This method returns the smallest key in the priority queue. \n",
    "    #   Use: key_var = heapq_var.max()\n",
    "    def mink(self):\n",
    "        return self.heap[0]     \n",
    "    \n",
    "    # This method implements the INSERT key into a priority queue operation\n",
    "    #   Use: heapq_var.heappush(key)\n",
    "    def heappush(self, key):   \n",
    "        \"\"\"\n",
    "        Inserts the value of key onto the priority queue, maintaining the max heap invariant.\n",
    "        \"\"\"\n",
    "        self.heap.append(float(\"inf\"))\n",
    "        self.decrease_key(self.heap_size,key)\n",
    "        self.heap_size+=1\n",
    "        \n",
    "    # This method implements the DECREASE_KEY operation, which modifies the value of a key\n",
    "    # in the min priority queue with a smaller value. \n",
    "    #   Use heapq_var.increase_key(i, new_key)\n",
    "    def decrease_key(self, i, key): \n",
    "        if key > self.heap[i]:\n",
    "            raise ValueError('new key is larger than the current key')\n",
    "        self.heap[i] = key\n",
    "        while i > 0 and self.heap[parent(i)] > self.heap[i]:\n",
    "            self.heap[parent(i)],self.heap[i] = self.heap[i], self.heap[parent(i)]\n",
    "            i = parent(i)    \n",
    "            \n",
    "    # This method implements the MIN_HEAPIFY operation for the min priority queue. The input is \n",
    "    # the array index of the root node of the subtree to be heapify.\n",
    "    #   Use heapq_var.heapify(i)        \n",
    "    def min_heapify(self, i): #need to change to minheapify\n",
    "        l = left(i)\n",
    "        r = right(i)\n",
    "        heap = self.heap\n",
    "        if l <= (self.heap_size-1) and heap[l] < heap[i]:\n",
    "            smallest = l\n",
    "        else:\n",
    "            smallest = i\n",
    "        if r <= (self.heap_size-1) and heap[r] < heap[smallest]:\n",
    "            smallest = r\n",
    "        if smallest != i:\n",
    "            heap[i], heap[smallest] = heap[smallest], heap[i]\n",
    "            self.min_heapify(smallest)\n",
    "\n",
    "    # This method implements the EXTRACT_MIN operation. It returns the smallest key in \n",
    "    # the min priority queue and removes this key from the min priority queue.\n",
    "    #   Use key_var = heapq_var.heappop() \n",
    "    def heappop(self): #don't need to change\n",
    "        if self.heap_size < 1:\n",
    "            raise ValueError('Heap underflow: There are no keys in the priority queue ')\n",
    "        mink = self.heap[0]\n",
    "        self.heap[0] = self.heap[-1]\n",
    "        self.heap.pop()\n",
    "        self.heap_size-=1\n",
    "        self.min_heapify(0)\n",
    "        return mink"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "24bca6c047b8f9473f8bc38c57d6b0b5",
     "grade": true,
     "grade_id": "cell-94922952c1f6d73e",
     "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": "549d036086c8cfaf3a1c121c840a84be",
     "grade": false,
     "grade_id": "cell-a1d697aca93c202c",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### Task 4. \n",
    "\n",
    "Use your `MinHeapq` implementation to build a min priority queue out of the list [6,4,7,9,10,-5,-6,12,8,3,1,-10]. You should store the Python list that represents the min heap in a variable named `my_heap_list`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "ce29dba864f0d616282d83cf6c2dab9f",
     "grade": false,
     "grade_id": "cell-bc27d7bf8580d64a",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-10, 1, -6, 8, 3, -5, 4, 12, 9, 10, 6, 7]\n"
     ]
    }
   ],
   "source": [
    "# GOAL: BUILD HEAP FROM [6,4,7,9,10,-5,-6,12,8,3,1,-10]\n",
    "#   Study the following lines of code, execute the cell and make sure you understand how the\n",
    "#   Python implementation of the MinHeapq is used here and the output from these lines.\n",
    "C = [6,4,7,9,10,-5,-6,12,8,3,1,-10]\n",
    "my_heap_list = MinHeapq()\n",
    "\n",
    "for key in C:\n",
    "    my_heap_list.heappush(key)\n",
    "\n",
    "print(my_heap_list.heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "c40c41c7c84c918a52ef50cac5992600",
     "grade": true,
     "grade_id": "cell-c76c6d24fa297106",
     "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
 }
	{
	"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": "274b43d88d65df3de28733d850616dca",
	"grade": false,
	"grade_id": "cell-3f3ec0504e39b023",
	"locked": true,
	"schema_version": 1,
	"solution": false
	}
	},
	"source": [
	"# CS110 Pre-class Work 4.1\n",
	"\n",
	"## Question 1. (Exercise 6.5-1 from Cormen et al.)\n",
	"\n",
	"Illustrate the operation of $HEAP-EXTRACT-MAX$ on the heap $A= \\langle 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1 \\rangle$\n"
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {
	"deletable": false,
	"nbgrader": {
	"checksum": "a7f20996d6e22ca2d544500769888784",
	"grade": true,
	"grade_id": "cell-7de130b1caacd3ab",
	"locked": false,
	"points": 0,
	"schema_version": 1,
	"solution": true
	}
	},
	"source": [
	"The operation$HEAP-EXTRACT-MAX$ first checks the length of heap A to make sure that it is smaller than 1 (contains no elements). We know that heap A is a max heap, and therefoer the first element is the biggest element. Thus, the operation assigns the key in the first index (15) as the ``max`` value. It then replaces 15 with the element in the last index, 1. Then, it reduces the length of the heap by 1. Lastly, it performs the function $MAX-HEAPIFY$ on the new heap to make it into a max heap again. The max element, in this case 15, is returned."
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {
	"deletable": false,
	"editable": false,
	"nbgrader": {
	"checksum": "d60dd22e7498fab87e01bedd8064d513",
	"grade": false,
	"grade_id": "cell-6cb98701e5a82f6b",
	"locked": true,
	"schema_version": 1,
	"solution": false
	}
	},
	"source": [
	"## Question 2. (Exercise 6.5-2 from Cormen et al.)\n",
	"\n",
	"Illustrate the operation of $MAX-HEAP-INSERT(A, 10)$ on the heap $A=\\langle 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1\\rangle$."
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {
	"deletable": false,
	"nbgrader": {
	"checksum": "3652f0e0f430ec440dd4899558426c74",
	"grade": true,
	"grade_id": "cell-74f212522535433a",
	"locked": false,
	"points": 0,
	"schema_version": 1,
	"solution": true
	}
	},
	"source": [
	"The operation $MAX-HEAP-INSERT(A, 10)$ first increases the length of heap A by 1, and assigns the new index with the sentinel value of $-\\infty$. It then performs the $HEAP-INCREASE-KEY(A, i, key)$ on the new heap, with $i$ being the length of heap A (12) and $key$ being 10 . What this function does is it first checks if the key is smaller than the value at the last index of heap A, which is impossible, because that last value is $-\\infty$. It then replaces the $-\\infty$ value at the last position with the key, 10, and then performs a while loop that does the following:\n",
	"\n",
	"While $i$ is larger than 1 (descending order) and the value of the parent of the number with index $i$ is smaller than the number with index $i$ itself, the algorithm will exchange the number with its parent. Now, we assign the parent index to the original child index $i$. \n",
	"\n",
	"Basically what this does is it's doing $MAX-HEAPIFY$ again to get the new number 10 all the way up where it should be positioned in the max heap."
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {
	"deletable": false,
	"editable": false,
	"nbgrader": {
	"checksum": "a986c9c7d690f05369df23660265d2a0",
	"grade": false,
	"grade_id": "cell-65c8d2b5e2e9deff",
	"locked": true,
	"schema_version": 1,
	"solution": false
	}
	},
	"source": [
	"## Question 3. Implementing Priority Queues Using Max and Min Heap Data Structures \n",
	"\n",
	"The next cell contains a Python implementation of a very basic priority queue based on a max heap data structure.<br>\n",
	"Please read and follow the <b>Instructions and Tasks</b> that are included below the next cell. These instructions and exercises will guide you through the Python code (i.e., <i><b>skip the Python code for now</b></i> and first proceed to read the instructions below the cell containing the Python code.) "
	]
	},
	{
	"cell_type": "code",
	"execution_count": 2,
	"metadata": {
	"deletable": false,
	"editable": false,
	"nbgrader": {
	"checksum": "dae9240440201b16c0ddd0180b223363",
	"grade": false,
	"grade_id": "cell-834cafc3878bd920",
	"locked": true,
	"schema_version": 1,
	"solution": false
	}
	},
	"outputs": [],
	"source": [
	"# \n",
	"# Defining some basic binary tree functions\n",
	"#\n",
	"def left(i): # left(i): takes as input the array index of a parent node in the binary tree and \n",
	" return 2*i + 1 # returns the array index of its left child.\n",
	"\n",
	"def right(i): # right(i): takes as input the array index of a parent node in the binary tree and \n",
	" return 2*i + 2 # returns the array index of its right child.\n",
	"\n",
	"def parent(i): # parent(i): takes as input the array index of a node in the binary tree and\n",
	" return (i-1)//2 # returns the array index of its parent\n",
	"\n",
	"\n",
	"# Defining the Python class MaxHeapq to implement a max heap data structure.\n",
	"# Every Object in this class has two attributes:\n",
	"# - heap : A Python list where key values in the max heap are stored\n",
	"# - heap_size: An integer counter of the number of keys present in the max heap\n",
	"class MaxHeapq:\n",
	" \"\"\" \n",
	" This class implements properties and methods that support a max priority queue data structure\n",
	" \"\"\" \n",
	" # Class initialization method. Use: heapq_var = MaxHeapq()\n",
	" def __init__(self): \n",
	" self.heap = []\n",
	" self.heap_size = 0\n",
	"\n",
	" # This method returns the highest key in the priority queue. \n",
	" # Use: key_var = heapq_var.max()\n",
	" def maxk(self): \n",
	" return self.heap[0] \n",
	" \n",
	" # This method implements the INSERT key into a priority queue operation\n",
	" # Use: heapq_var.heappush(key)\n",
	" def heappush(self, key): \n",
	" \"\"\"\n",
	" Inserts the value of key onto the priority queue, maintaining the max heap invariant.\n",
	" \"\"\"\n",
	" self.heap.append(-float(\"inf\"))\n",
	" self.increase_key(self.heap_size,key)\n",
	" self.heap_size+=1\n",
	" \n",
	" # This method implements the INCREASE_KEY operation, which modifies the value of a key\n",
	" # in the max priority queue with a higher value. \n",
	" # Use heapq_var.increase_key(i, new_key)\n",
	" def increase_key(self, i, key): \n",
	" if key < self.heap[i]:\n",
	" raise ValueError('new key is smaller than the current key')\n",
	" self.heap[i] = key\n",
	" while i > 0 and self.heap[parent(i)] < self.heap[i]:\n",
	" j = parent(i)\n",
	" holder = self.heap[j]\n",
	" self.heap[j] = self.heap[i]\n",
	" self.heap[i] = holder\n",
	" i = j \n",
	" \n",
	" # This method implements the MAX_HEAPIFY operation for the max priority queue. The input is \n",
	" # the array index of the root node of the subtree to be heapify.\n",
	" # Use heapq_var.heapify(i) \n",
	" def heapify(self, i):\n",
	" l = left(i)\n",
	" r = right(i)\n",
	" heap = self.heap\n",
	" if l <= (self.heap_size-1) and heap[l]>heap[i]:\n",
	" largest = l\n",
	" else:\n",
	" largest = i\n",
	" if r <= (self.heap_size-1) and heap[r] > heap[largest]:\n",
	" largest = r\n",
	" if largest != i:\n",
	" heap[i], heap[largest] = heap[largest], heap[i]\n",
	" self.heapify(largest)\n",
	"\n",
	" # This method implements the EXTRACT_MAX operation. It returns the largest key in \n",
	" # the max priority queue and removes this key from the max priority queue.\n",
	" # Use key_var = heapq_var.heappop() \n",
	" def heappop(self):\n",
	" if self.heap_size < 1:\n",
	" raise ValueError('Heap underflow: There are no keys in the priority queue ')\n",
	" maxk = self.heap[0]\n",
	" self.heap[0] = self.heap[-1]\n",
	" self.heap.pop()\n",
	" self.heap_size-=1\n",
	" self.heapify(0)\n",
	" return maxk"
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {
	"deletable": false,
	"editable": false,
	"nbgrader": {
	"checksum": "0fe80b7551c447558abc43ec307de37e",
	"grade": false,
	"grade_id": "cell-2462e8ce46926058",
	"locked": true,
	"schema_version": 1,
	"solution": false
	}
	},
	"source": [
	"## Instructions and Tasks.\n",
	"The goal of these tasks is for you to learn how to implement, build, and manage priority queues in Python. \n",
	"\n",
	"First, let us practice building a max priority queue from a random list of keys.<br> \n",
	"For example, given a list of keys: [4,3,6,8,2,-5,100], we want to obtain a max priority queue that looks like this: [100, 6, 8, 3, 2, -5, 4], recall that in a max priority list the highest key should be on top (given priority). \n",
	"\n",
	"### Task 0.\n",
	"Check whether the list [100, 6, 8, 3, 2, -5, 4] is indeed a max priority queue. Recall that a max priority queue data structure is based on a max heap data structure. Give a short explanation."
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {
	"deletable": false,
	"nbgrader": {
	"checksum": "d96ebcf5802ceeb1a33e34c5a5afe211",
	"grade": true,
	"grade_id": "cell-5e0b898075b25073",
	"locked": false,
	"points": 0,
	"schema_version": 1,
	"solution": true
	}
	},
	"source": [
	"Yes, the list [100, 6, 8, 3, 2, -5, 4] is indeed a max priority queue. If we draw it out, it resembles a max heap, with the biggest element at the very top of the heap and all the child elements are smaller than their parent element in the heap. "
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {
	"deletable": false,
	"editable": false,
	"nbgrader": {
	"checksum": "0a9b4ea61e7caa5bbeb1fa79575f31f9",
	"grade": false,
	"grade_id": "cell-01e1945386d515a2",
	"locked": true,
	"schema_version": 1,
	"solution": false
	}
	},
	"source": [
	"### Task 1.\n",
	"The following cell uses the Python implementation of a max priority queue. This a good time to review the Python code above and then follow the rest of these instructions."
	]
	},
	{
	"cell_type": "code",
	"execution_count": 3,
	"metadata": {
	"deletable": false,
	"editable": false,
	"nbgrader": {
	"checksum": "da3a43089e2db1466a2db091855b07e0",
	"grade": false,
	"grade_id": "cell-e301a5a468f9b84e",
	"locked": true,
	"schema_version": 1,
	"solution": false
	}
	},
	"outputs": [
	{
	"name": "stdout",
	"output_type": "stream",
	"text": [
	"[100, 6, 8, 3, 2, -5, 4]\n"
	]
	}
	],
	"source": [
	"# GOAL: BUILD HEAP FROM [4,3,6,8,2,-5,100]\n",
	"# Study the following lines of code, execute the cell and make sure you understand how the\n",
	"# Python implementation of the MaxHeapq is used here and the output from these lines.\n",
	"A = [4,3,6,8,2,-5,100]\n",
	"my_heap = MaxHeapq()\n",
	"\n",
	"for key in A:\n",
	" my_heap.heappush(key)\n",
	"\n",
	"print(my_heap.heap)"
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {
	"deletable": false,
	"editable": false,
	"nbgrader": {
	"checksum": "c3ea1d8efdd3151a6a3bb4f027f292b7",
	"grade": false,
	"grade_id": "cell-cf7dd96ee4eb3c43",
	"locked": true,
	"schema_version": 1,
	"solution": false
	}
	},
	"source": [
	"### Task 2. \n",
	"Given the list [6,4,7,9,10,-5,-6,12,8,3,1,-10], build a max heap. You should store the Python list that represents the max heap in a variable named `my_heap_list`.\n",
	"\n"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 4,
	"metadata": {
	"deletable": false,
	"nbgrader": {
	"checksum": "5cfb440b6fd86152d8ec5aaf1b166156",
	"grade": false,
	"grade_id": "cell-8f1991aebb9ab87c",
	"locked": false,
	"schema_version": 1,
	"solution": true
	}
	},
	"outputs": [
	{
	"name": "stdout",
	"output_type": "stream",
	"text": [
	"[12, 10, 6, 9, 7, -5, -6, 4, 8, 3, 1, -10]\n"
	]
	}
	],
	"source": [
	"B = [6,4,7,9,10,-5,-6,12,8,3,1,-10]\n",
	"my_heap_list = MaxHeapq()\n",
	"\n",
	"for key in B:\n",
	" my_heap_list.heappush(key)\n",
	"\n",
	"print(my_heap_list.heap)"
	]
	},
	{
	"cell_type": "code",
	"execution_count": null,
	"metadata": {
	"deletable": false,
	"editable": false,
	"nbgrader": {
	"checksum": "26429f9e44e6cc1038e2742a4d470879",
	"grade": true,
	"grade_id": "cell-fa85b4b29f6da1af",
	"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": "9f8056e40f22478e49e5dbf9b316cb44",
	"grade": false,
	"grade_id": "cell-630703ffa2b4b776",
	"locked": true,
	"schema_version": 1,
	"solution": false
	}
	},
	"source": [
	"### Task 3.\n",
	"Using the Python code that implements the class `MaxHeapq` as a reference, build a class `MinHeapq`, a min priority queue. Your class should contain the following method: `mink`, `heappush`, `decrease_key`, `heapify`, and `heappop`."
	]
	},
	{
	"cell_type": "code",
	"execution_count": 8,
	"metadata": {
	"deletable": false,
	"nbgrader": {
	"checksum": "0cd32eb273c3524ad096e0817d58fac3",
	"grade": false,
	"grade_id": "cell-927eee0091ce8d12",
	"locked": false,
	"schema_version": 1,
	"solution": true
	}
	},
	"outputs": [],
	"source": [
	"# \n",
	"# Defining some basic binary tree functions\n",
	"#\n",
	"def left(i): # left(i): takes as input the array index of a parent node in the binary tree and \n",
	" return 2*i + 1 # returns the array index of its left child.\n",
	"\n",
	"def right(i): # right(i): takes as input the array index of a parent node in the binary tree and \n",
	" return 2*i + 2 # returns the array index of its right child.\n",
	"\n",
	"def parent(i): # parent(i): takes as input the array index of a node in the binary tree and\n",
	" return (i-1)//2 # returns the array index of its parent\n",
	"\n",
	"\n",
	"# Defining the Python class MinHeapq to implement a min heap data structure.\n",
	"# Every Object in this class has two attributes:\n",
	"# - heap : A Python list where key values in the min heap are stored\n",
	"# - heap_size: An integer counter of the number of keys present in the min heap\n",
	"class MinHeapq:\n",
	" \"\"\" \n",
	" This class implements properties and methods that support a max priority queue data structure\n",
	" \"\"\" \n",
	" # Class initialization method. Use: heapq_var = MaxHeapq()\n",
	" def __init__(self): \n",
	" self.heap = []\n",
	" self.heap_size = 0\n",
	"\n",
	" # This method returns the smallest key in the priority queue. \n",
	" # Use: key_var = heapq_var.max()\n",
	" def mink(self):\n",
	" return self.heap[0] \n",
	" \n",
	" # This method implements the INSERT key into a priority queue operation\n",
	" # Use: heapq_var.heappush(key)\n",
	" def heappush(self, key): \n",
	" \"\"\"\n",
	" Inserts the value of key onto the priority queue, maintaining the max heap invariant.\n",
	" \"\"\"\n",
	" self.heap.append(float(\"inf\"))\n",
	" self.decrease_key(self.heap_size,key)\n",
	" self.heap_size+=1\n",
	" \n",
	" # This method implements the DECREASE_KEY operation, which modifies the value of a key\n",
	" # in the min priority queue with a smaller value. \n",
	" # Use heapq_var.increase_key(i, new_key)\n",
	" def decrease_key(self, i, key): \n",
	" if key > self.heap[i]:\n",
	" raise ValueError('new key is larger than the current key')\n",
	" self.heap[i] = key\n",
	" while i > 0 and self.heap[parent(i)] > self.heap[i]:\n",
	" self.heap[parent(i)],self.heap[i] = self.heap[i], self.heap[parent(i)]\n",
	" i = parent(i) \n",
	" \n",
	" # This method implements the MIN_HEAPIFY operation for the min priority queue. The input is \n",
	" # the array index of the root node of the subtree to be heapify.\n",
	" # Use heapq_var.heapify(i) \n",
	" def min_heapify(self, i): #need to change to minheapify\n",
	" l = left(i)\n",
	" r = right(i)\n",
	" heap = self.heap\n",
	" if l <= (self.heap_size-1) and heap[l] < heap[i]:\n",
	" smallest = l\n",
	" else:\n",
	" smallest = i\n",
	" if r <= (self.heap_size-1) and heap[r] < heap[smallest]:\n",
	" smallest = r\n",
	" if smallest != i:\n",
	" heap[i], heap[smallest] = heap[smallest], heap[i]\n",
	" self.min_heapify(smallest)\n",
	"\n",
	" # This method implements the EXTRACT_MIN operation. It returns the smallest key in \n",
	" # the min priority queue and removes this key from the min priority queue.\n",
	" # Use key_var = heapq_var.heappop() \n",
	" def heappop(self): #don't need to change\n",
	" if self.heap_size < 1:\n",
	" raise ValueError('Heap underflow: There are no keys in the priority queue ')\n",
	" mink = self.heap[0]\n",
	" self.heap[0] = self.heap[-1]\n",
	" self.heap.pop()\n",
	" self.heap_size-=1\n",
	" self.min_heapify(0)\n",
	" return mink"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 9,
	"metadata": {
	"deletable": false,
	"editable": false,
	"nbgrader": {
	"checksum": "24bca6c047b8f9473f8bc38c57d6b0b5",
	"grade": true,
	"grade_id": "cell-94922952c1f6d73e",
	"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": "549d036086c8cfaf3a1c121c840a84be",
	"grade": false,
	"grade_id": "cell-a1d697aca93c202c",
	"locked": true,
	"schema_version": 1,
	"solution": false
	}
	},
	"source": [
	"### Task 4. \n",
	"\n",
	"Use your `MinHeapq` implementation to build a min priority queue out of the list [6,4,7,9,10,-5,-6,12,8,3,1,-10]. You should store the Python list that represents the min heap in a variable named `my_heap_list`."
	]
	},
	{
	"cell_type": "code",
	"execution_count": 10,
	"metadata": {
	"deletable": false,
	"nbgrader": {
	"checksum": "ce29dba864f0d616282d83cf6c2dab9f",
	"grade": false,
	"grade_id": "cell-bc27d7bf8580d64a",
	"locked": false,
	"schema_version": 1,
	"solution": true
	}
	},
	"outputs": [
	{
	"name": "stdout",
	"output_type": "stream",
	"text": [
	"[-10, 1, -6, 8, 3, -5, 4, 12, 9, 10, 6, 7]\n"
	]
	}
	],
	"source": [
	"# GOAL: BUILD HEAP FROM [6,4,7,9,10,-5,-6,12,8,3,1,-10]\n",
	"# Study the following lines of code, execute the cell and make sure you understand how the\n",
	"# Python implementation of the MinHeapq is used here and the output from these lines.\n",
	"C = [6,4,7,9,10,-5,-6,12,8,3,1,-10]\n",
	"my_heap_list = MinHeapq()\n",
	"\n",
	"for key in C:\n",
	" my_heap_list.heappush(key)\n",
	"\n",
	"print(my_heap_list.heap)"
	]
	},
	{
	"cell_type": "code",
	"execution_count": null,
	"metadata": {
	"deletable": false,
	"editable": false,
	"nbgrader": {
	"checksum": "c40c41c7c84c918a52ef50cac5992600",
	"grade": true,
	"grade_id": "cell-c76c6d24fa297106",
	"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
	}