cs110_pcw_4_1.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": "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 Heap_Extract_Max removes the max value from the heap and return it then it takes the last element in the heap and puts at the root. Then it calls heapify to compare the root with the child nodes and ensure the root has the largest value."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![title](1.png)"
   ]
  },
  {
   "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": [
    "This function inserts a new element to the end of the list, and it keeps compares the new value to its parent value. If the new value is less the parent node, the elements are exchanged. In worst case, the new element might climb up to the root of the heap."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![title](2.jpg)"
   ]
  },
  {
   "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": [
    "This list is a max priority queue because it meets the maximum heap condition (all parent nodes are greater than or equal child nodes). In this particular case, we find that 100 is greater than 6 & 8; 6 is greater than 3 % 2; and 8 is greater than -5 & 4. "
   ]
  },
  {
   "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": [
      "[47, 10, 12, 8, 1, -6, 9, 6, 3, -5, -10]\n"
     ]
    }
   ],
   "source": [
    "alist = [6,47,9,10,-5,-6,12,8,3,1,-10] #define the list \n",
    "my_heap = MaxHeapq() #create a variable that holds an object of the class MaxHeap so we could acess the \n",
    "                    #functions and variables in it\n",
    "for key in alist: # for each element in the list, do the following\n",
    "    my_heap.heappush(key) # perform the method heappush \n",
    "my_heap_list = my_heap.heap #store the result in a new variable\n",
    "\n",
    "print(my_heap_list) #print the min priority queue of the alist\n",
    "\n",
    "    \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "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": 6,
   "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",
    "\n",
    "class MinHeapq:\n",
    "  \n",
    "    # Class initialization method. Use: heapq_var = MinHeapq()\n",
    "    def __init__(self):        \n",
    "        self.heap       = []\n",
    "        self.heap_size  = 0\n",
    "\n",
    "    # This method returns the lowest key in the priority queue. \n",
    "\n",
    "    def mink(self):              \n",
    "        return self.heap[0]     \n",
    "    \n",
    "    # This method implements the INSERT key into a priority queue operation\n",
    "\n",
    "    def heappush(self, key):   \n",
    "\n",
    "        self.heap.append(float(\"inf\"))\n",
    "        self.decrease_key(self.heap_size,key)\n",
    "        self.heap_size+=1\n",
    "        \n",
    "\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",
    "            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 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 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",
    "            Lowest = l\n",
    "        else:\n",
    "            Lowest = i\n",
    "        if r <= (self.heap_size-1) and heap[r] < heap[Lowest]:\n",
    "            Lowest = r\n",
    "        if Lowest != i:\n",
    "            heap[i], heap[Lowest] = heap[Lowest], heap[i]\n",
    "            self.heapify(Lowest)\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": "code",
   "execution_count": 7,
   "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": 8,
   "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, -6, -5, 6, 1, 9, 12, 47, 8, 10, 3]\n"
     ]
    }
   ],
   "source": [
    "alist = [6,47,9,10,-5,-6,12,8,3,1,-10] #define the list \n",
    "my_heap = MinHeapq() #create a variable that holds an object of the class MinHeap so we could acess the \n",
    "                    #functions and variables in it\n",
    "for key in alist: # for each element in the list, do the following\n",
    "    my_heap.heappush(key) # perform the method heappush \n",
    "my_heap_list = my_heap.heap #store the result in a new variable\n",
    "\n",
    "print(my_heap_list) #print the min priority queue of the alist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}