SHARE
TWEET

Untitled

a guest Oct 19th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. {
  2.  "cells": [
  3.   {
  4.    "cell_type": "markdown",
  5.    "metadata": {},
  6.    "source": [
  7.     "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",
  8.     "\n",
  9.     "Make sure you fill in any place that says `YOUR CODE HERE` or \"YOUR ANSWER HERE\", as well as your name and collaborators below:"
  10.    ]
  11.   },
  12.   {
  13.    "cell_type": "code",
  14.    "execution_count": null,
  15.    "metadata": {},
  16.    "outputs": [],
  17.    "source": [
  18.     "NAME = \"Carlos Rafael Garduño Acolt\"\n",
  19.     "COLLABORATORS = \"\""
  20.    ]
  21.   },
  22.   {
  23.    "cell_type": "markdown",
  24.    "metadata": {},
  25.    "source": [
  26.     "---"
  27.    ]
  28.   },
  29.   {
  30.    "cell_type": "markdown",
  31.    "metadata": {
  32.     "deletable": false,
  33.     "editable": false,
  34.     "nbgrader": {
  35.      "checksum": "274b43d88d65df3de28733d850616dca",
  36.      "grade": false,
  37.      "grade_id": "cell-3f3ec0504e39b023",
  38.      "locked": true,
  39.      "schema_version": 1,
  40.      "solution": false
  41.     }
  42.    },
  43.    "source": [
  44.     "# CS110 Pre-class Work 4.1\n",
  45.     "\n",
  46.     "## Question 1. (Exercise 6.5-1 from Cormen et al.)\n",
  47.     "\n",
  48.     "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"
  49.    ]
  50.   },
  51.   {
  52.    "cell_type": "markdown",
  53.    "metadata": {
  54.     "deletable": false,
  55.     "nbgrader": {
  56.      "checksum": "a7f20996d6e22ca2d544500769888784",
  57.      "grade": true,
  58.      "grade_id": "cell-7de130b1caacd3ab",
  59.      "locked": false,
  60.      "points": 0,
  61.      "schema_version": 1,
  62.      "solution": true
  63.     }
  64.    },
  65.    "source": [
  66.     ">A=⟨15,13,9,5,12,8,7,4,0,6,2,1⟩\n",
  67.     "\n",
  68.     "The program will first look for the greatest (max) element in the array by comparing all of them.  \n",
  69.     "\n",
  70.     "Then it will return it:\n",
  71.     "\n",
  72.     ">MAX = 15\n",
  73.     "\n",
  74.     "Finally, it will also remove it from the array:\n",
  75.     "\n",
  76.     ">A=⟨13,9,5,12,8,7,4,0,6,2,1⟩\n"
  77.    ]
  78.   },
  79.   {
  80.    "cell_type": "markdown",
  81.    "metadata": {
  82.     "deletable": false,
  83.     "editable": false,
  84.     "nbgrader": {
  85.      "checksum": "d60dd22e7498fab87e01bedd8064d513",
  86.      "grade": false,
  87.      "grade_id": "cell-6cb98701e5a82f6b",
  88.      "locked": true,
  89.      "schema_version": 1,
  90.      "solution": false
  91.     }
  92.    },
  93.    "source": [
  94.     "## Question 2. (Exercise 6.5-2 from Cormen et al.)\n",
  95.     "\n",
  96.     "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$."
  97.    ]
  98.   },
  99.   {
  100.    "cell_type": "markdown",
  101.    "metadata": {
  102.     "deletable": false,
  103.     "nbgrader": {
  104.      "checksum": "3652f0e0f430ec440dd4899558426c74",
  105.      "grade": true,
  106.      "grade_id": "cell-74f212522535433a",
  107.      "locked": false,
  108.      "points": 0,
  109.      "schema_version": 1,
  110.      "solution": true
  111.     }
  112.    },
  113.    "source": [
  114.     ">A=⟨15,13,9,5,12,8,7,4,0,6,2,1⟩\n",
  115.     "\n",
  116.     "The code will first take the value given for the key and add it at the end of the heap:\n",
  117.     "\n",
  118.     ">A=⟨15,13,9,5,12,8,7,4,0,6,2,1,10⟩\n",
  119.     "\n",
  120.     "Then it will call on HEAP-INCREASE-KEY in order to set the new key on its correct place so that the max-heap property stays true (parent nodes being equal to or larget than their children nodes):\n",
  121.     "\n",
  122.     "The program will compare the new element with its parent and will bubble up until it finds the new key's right place.\n",
  123.     "\n",
  124.     ">A=⟨15,13,9,5,12,8,7,4,0,6,2,1,10⟩\n",
  125.     "\n",
  126.     "The new key will swap twice with its parents; first with 8 and then with 9, and will end up in place A[2] as the right chilf of the root node.\n",
  127.     "\n",
  128.     ">A=⟨15,13,9,5,12,10,7,4,0,6,2,1,8⟩\n",
  129.     "\n",
  130.     ">A=⟨15,13,10,5,12,9,7,4,0,6,2,1,8⟩\n",
  131.     "\n",
  132.     "\n",
  133.     "\n",
  134.     "\n"
  135.    ]
  136.   },
  137.   {
  138.    "cell_type": "markdown",
  139.    "metadata": {
  140.     "deletable": false,
  141.     "editable": false,
  142.     "nbgrader": {
  143.      "checksum": "a986c9c7d690f05369df23660265d2a0",
  144.      "grade": false,
  145.      "grade_id": "cell-65c8d2b5e2e9deff",
  146.      "locked": true,
  147.      "schema_version": 1,
  148.      "solution": false
  149.     }
  150.    },
  151.    "source": [
  152.     "## Question 3. Implementing Priority Queues Using Max and Min Heap Data Structures \n",
  153.     "\n",
  154.     "The next cell contains a Python implementation of a very basic priority queue based on a max heap data structure.<br>\n",
  155.     "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.) "
  156.    ]
  157.   },
  158.   {
  159.    "cell_type": "code",
  160.    "execution_count": 2,
  161.    "metadata": {
  162.     "deletable": false,
  163.     "editable": false,
  164.     "nbgrader": {
  165.      "checksum": "dae9240440201b16c0ddd0180b223363",
  166.      "grade": false,
  167.      "grade_id": "cell-834cafc3878bd920",
  168.      "locked": true,
  169.      "schema_version": 1,
  170.      "solution": false
  171.     }
  172.    },
  173.    "outputs": [],
  174.    "source": [
  175.     "# \n",
  176.     "# Defining some basic binary tree functions\n",
  177.     "#\n",
  178.     "def left(i):         # left(i): takes as input the array index of a parent node in the binary tree and \n",
  179.     "    return 2*i + 1   #          returns the array index of its left child.\n",
  180.     "\n",
  181.     "def right(i):        # right(i): takes as input the array index of a parent node in the binary tree and \n",
  182.     "    return 2*i + 2   #           returns the array index of its right child.\n",
  183.     "\n",
  184.     "def parent(i):       # parent(i): takes as input the array index of a node in the binary tree and\n",
  185.     "    return (i-1)//2  #            returns the array index of its parent\n",
  186.     "\n",
  187.     "\n",
  188.     "# Defining the Python class MaxHeapq to implement a max heap data structure.\n",
  189.     "# Every Object in this class has two attributes:\n",
  190.     "#           - heap : A Python list where key values in the max heap are stored\n",
  191.     "#           - heap_size: An integer counter of the number of keys present in the max heap\n",
  192.     "class MaxHeapq:\n",
  193.     "    \"\"\" \n",
  194.     "    This class implements properties and methods that support a max priority queue data structure\n",
  195.     "    \"\"\"  \n",
  196.     "    # Class initialization method. Use: heapq_var = MaxHeapq()\n",
  197.     "    def __init__(self):        \n",
  198.     "        self.heap       = []\n",
  199.     "        self.heap_size  = 0\n",
  200.     "\n",
  201.     "    # This method returns the highest key in the priority queue. \n",
  202.     "    #   Use: key_var = heapq_var.max()\n",
  203.     "    def maxk(self):              \n",
  204.     "        return self.heap[0]     \n",
  205.     "    \n",
  206.     "    # This method implements the INSERT key into a priority queue operation\n",
  207.     "    #   Use: heapq_var.heappush(key)\n",
  208.     "    def heappush(self, key):   \n",
  209.     "        \"\"\"\n",
  210.     "        Inserts the value of key onto the priority queue, maintaining the max heap invariant.\n",
  211.     "        \"\"\"\n",
  212.     "        self.heap.append(-float(\"inf\"))\n",
  213.     "        self.increase_key(self.heap_size,key)\n",
  214.     "        self.heap_size+=1\n",
  215.     "        \n",
  216.     "    # This method implements the INCREASE_KEY operation, which modifies the value of a key\n",
  217.     "    # in the max priority queue with a higher value. \n",
  218.     "    #   Use heapq_var.increase_key(i, new_key)\n",
  219.     "    def increase_key(self, i, key): \n",
  220.     "        if key < self.heap[i]:\n",
  221.     "            raise ValueError('new key is smaller than the current key')\n",
  222.     "        self.heap[i] = key\n",
  223.     "        while i > 0 and self.heap[parent(i)] < self.heap[i]:\n",
  224.     "            j = parent(i)\n",
  225.     "            holder = self.heap[j]\n",
  226.     "            self.heap[j] = self.heap[i]\n",
  227.     "            self.heap[i] = holder\n",
  228.     "            i = j    \n",
  229.     "            \n",
  230.     "    # This method implements the MAX_HEAPIFY operation for the max priority queue. The input is \n",
  231.     "    # the array index of the root node of the subtree to be heapify.\n",
  232.     "    #   Use heapq_var.heapify(i)        \n",
  233.     "    def heapify(self, i):\n",
  234.     "        l = left(i)\n",
  235.     "        r = right(i)\n",
  236.     "        heap = self.heap\n",
  237.     "        if l <= (self.heap_size-1) and heap[l]>heap[i]:\n",
  238.     "            largest = l\n",
  239.     "        else:\n",
  240.     "            largest = i\n",
  241.     "        if r <= (self.heap_size-1) and heap[r] > heap[largest]:\n",
  242.     "            largest = r\n",
  243.     "        if largest != i:\n",
  244.     "            heap[i], heap[largest] = heap[largest], heap[i]\n",
  245.     "            self.heapify(largest)\n",
  246.     "\n",
  247.     "    # This method implements the EXTRACT_MAX operation. It returns the largest key in \n",
  248.     "    # the max priority queue and removes this key from the max priority queue.\n",
  249.     "    #   Use key_var = heapq_var.heappop() \n",
  250.     "    def heappop(self):\n",
  251.     "        if self.heap_size < 1:\n",
  252.     "            raise ValueError('Heap underflow: There are no keys in the priority queue ')\n",
  253.     "        maxk = self.heap[0]\n",
  254.     "        self.heap[0] = self.heap[-1]\n",
  255.     "        self.heap.pop()\n",
  256.     "        self.heap_size-=1\n",
  257.     "        self.heapify(0)\n",
  258.     "        return maxk"
  259.    ]
  260.   },
  261.   {
  262.    "cell_type": "markdown",
  263.    "metadata": {
  264.     "deletable": false,
  265.     "editable": false,
  266.     "nbgrader": {
  267.      "checksum": "0fe80b7551c447558abc43ec307de37e",
  268.      "grade": false,
  269.      "grade_id": "cell-2462e8ce46926058",
  270.      "locked": true,
  271.      "schema_version": 1,
  272.      "solution": false
  273.     }
  274.    },
  275.    "source": [
  276.     "## Instructions and Tasks.\n",
  277.     "The goal of these tasks is for you to learn how to implement, build, and manage priority queues in Python. \n",
  278.     "\n",
  279.     "First, let us practice building a max priority queue from a random list of keys.<br> \n",
  280.     "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",
  281.     "\n",
  282.     "### Task 0.\n",
  283.     "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."
  284.    ]
  285.   },
  286.   {
  287.    "cell_type": "markdown",
  288.    "metadata": {
  289.     "deletable": false,
  290.     "nbgrader": {
  291.      "checksum": "d96ebcf5802ceeb1a33e34c5a5afe211",
  292.      "grade": true,
  293.      "grade_id": "cell-5e0b898075b25073",
  294.      "locked": false,
  295.      "points": 0,
  296.      "schema_version": 1,
  297.      "solution": true
  298.     }
  299.    },
  300.    "source": [
  301.     "Yes, it is a valid max priority queue, as it is also a valid max-heap data structure:\n",
  302.     "\n",
  303.     "If we check, the max-heap property is true for all elements:\n",
  304.     "\n",
  305.     ">100 > 6 and 100 > 8\n",
  306.     "\n",
  307.     ">6 > 3 and 6 > 2\n",
  308.     "\n",
  309.     ">8 > -5 and 8 > 4\n",
  310.     "\n",
  311.     "\n"
  312.    ]
  313.   },
  314.   {
  315.    "cell_type": "markdown",
  316.    "metadata": {
  317.     "deletable": false,
  318.     "editable": false,
  319.     "nbgrader": {
  320.      "checksum": "0a9b4ea61e7caa5bbeb1fa79575f31f9",
  321.      "grade": false,
  322.      "grade_id": "cell-01e1945386d515a2",
  323.      "locked": true,
  324.      "schema_version": 1,
  325.      "solution": false
  326.     }
  327.    },
  328.    "source": [
  329.     "### Task 1.\n",
  330.     "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."
  331.    ]
  332.   },
  333.   {
  334.    "cell_type": "code",
  335.    "execution_count": 3,
  336.    "metadata": {
  337.     "deletable": false,
  338.     "editable": false,
  339.     "nbgrader": {
  340.      "checksum": "da3a43089e2db1466a2db091855b07e0",
  341.      "grade": false,
  342.      "grade_id": "cell-e301a5a468f9b84e",
  343.      "locked": true,
  344.      "schema_version": 1,
  345.      "solution": false
  346.     }
  347.    },
  348.    "outputs": [
  349.     {
  350.      "name": "stdout",
  351.      "output_type": "stream",
  352.      "text": [
  353.       "[100, 6, 8, 3, 2, -5, 4]\n"
  354.      ]
  355.     }
  356.    ],
  357.    "source": [
  358.     "# GOAL: BUILD HEAP FROM [4,3,6,8,2,-5,100]\n",
  359.     "#   Study the following lines of code, execute the cell and make sure you understand how the\n",
  360.     "#   Python implementation of the MaxHeapq is used here and the output from these lines.\n",
  361.     "A = [4,3,6,8,2,-5,100]\n",
  362.     "my_heap = MaxHeapq()\n",
  363.     "\n",
  364.     "for key in A:\n",
  365.     "    my_heap.heappush(key)\n",
  366.     "\n",
  367.     "print(my_heap.heap)"
  368.    ]
  369.   },
  370.   {
  371.    "cell_type": "markdown",
  372.    "metadata": {
  373.     "deletable": false,
  374.     "editable": false,
  375.     "nbgrader": {
  376.      "checksum": "c3ea1d8efdd3151a6a3bb4f027f292b7",
  377.      "grade": false,
  378.      "grade_id": "cell-cf7dd96ee4eb3c43",
  379.      "locked": true,
  380.      "schema_version": 1,
  381.      "solution": false
  382.     }
  383.    },
  384.    "source": [
  385.     "### Task 2. \n",
  386.     "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",
  387.     "\n"
  388.    ]
  389.   },
  390.   {
  391.    "cell_type": "code",
  392.    "execution_count": 14,
  393.    "metadata": {
  394.     "deletable": false,
  395.     "nbgrader": {
  396.      "checksum": "5cfb440b6fd86152d8ec5aaf1b166156",
  397.      "grade": false,
  398.      "grade_id": "cell-8f1991aebb9ab87c",
  399.      "locked": false,
  400.      "schema_version": 1,
  401.      "solution": true
  402.     }
  403.    },
  404.    "outputs": [
  405.     {
  406.      "name": "stdout",
  407.      "output_type": "stream",
  408.      "text": [
  409.       "[12, 10, 6, 9, 7, -5, -6, 4, 8, 3, 1, -10]\n"
  410.      ]
  411.     }
  412.    ],
  413.    "source": [
  414.     "A = [6,4,7,9,10,-5,-6,12,8,3,1,-10]\n",
  415.     "my_heap = MaxHeapq()\n",
  416.     "\n",
  417.     "for key in A:\n",
  418.     "    my_heap.heappush(key)\n",
  419.     "\n",
  420.     "my_heap_list = my_heap.heap\n",
  421.     "\n",
  422.     "print(my_heap_list)\n"
  423.    ]
  424.   },
  425.   {
  426.    "cell_type": "code",
  427.    "execution_count": 12,
  428.    "metadata": {
  429.     "deletable": false,
  430.     "editable": false,
  431.     "nbgrader": {
  432.      "checksum": "26429f9e44e6cc1038e2742a4d470879",
  433.      "grade": true,
  434.      "grade_id": "cell-fa85b4b29f6da1af",
  435.      "locked": true,
  436.      "points": 1,
  437.      "schema_version": 1,
  438.      "solution": false
  439.     }
  440.    },
  441.    "outputs": [],
  442.    "source": [
  443.     "# Please ignore this cell. This cell is for us to implement the tests \n",
  444.     "# to see if your code works properly. "
  445.    ]
  446.   },
  447.   {
  448.    "cell_type": "markdown",
  449.    "metadata": {
  450.     "deletable": false,
  451.     "editable": false,
  452.     "nbgrader": {
  453.      "checksum": "9f8056e40f22478e49e5dbf9b316cb44",
  454.      "grade": false,
  455.      "grade_id": "cell-630703ffa2b4b776",
  456.      "locked": true,
  457.      "schema_version": 1,
  458.      "solution": false
  459.     }
  460.    },
  461.    "source": [
  462.     "### Task 3.\n",
  463.     "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`."
  464.    ]
  465.   },
  466.   {
  467.    "cell_type": "code",
  468.    "execution_count": 40,
  469.    "metadata": {
  470.     "deletable": false,
  471.     "nbgrader": {
  472.      "checksum": "0cd32eb273c3524ad096e0817d58fac3",
  473.      "grade": false,
  474.      "grade_id": "cell-927eee0091ce8d12",
  475.      "locked": false,
  476.      "schema_version": 1,
  477.      "solution": true
  478.     }
  479.    },
  480.    "outputs": [],
  481.    "source": [
  482.     "class MinHeapq:\n",
  483.     "    \"\"\" \n",
  484.     "    This class implements properties and methods that support a min priority queue data structure\n",
  485.     "    \"\"\"  \n",
  486.     "    # Class initialization method. Use: heapq_var = MinHeapq()\n",
  487.     "    def __init__(self):        \n",
  488.     "        self.heap       = []\n",
  489.     "        self.heap_size  = 0\n",
  490.     "\n",
  491.     "    # This method returns the lowest key in the priority queue. \n",
  492.     "    #   Use: key_var = heapq_var.min()\n",
  493.     "    def mink(self):              \n",
  494.     "        return self.heap[0]     \n",
  495.     "    \n",
  496.     "    # This method implements the INSERT key into a priority queue operation\n",
  497.     "    #   Use: heapq_var.heappush(key)\n",
  498.     "    def heappush(self, key):   \n",
  499.     "        \"\"\"\n",
  500.     "        Inserts the value of key onto the priority queue, maintaining the max heap invariant.\n",
  501.     "        \"\"\"\n",
  502.     "        self.heap.append(-float(\"inf\"))\n",
  503.     "        self.decrease_key(self.heap_size,key)\n",
  504.     "        self.heap_size+=1\n",
  505.     "        \n",
  506.     "    # This method implements the DECREASE_KEY operation, which modifies the value of a key\n",
  507.     "    # in the min priority queue with a lower value. \n",
  508.     "    #   Use heapq_var.decrease_key(i, new_key)\n",
  509.     "    def decrease_key(self, i, key): \n",
  510.     "        if key < self.heap[i]:\n",
  511.     "            raise ValueError('new key is smaller than the current key')\n",
  512.     "        self.heap[i] = key\n",
  513.     "        while i > 0 and self.heap[parent(i)] > self.heap[i]:\n",
  514.     "            j = parent(i)\n",
  515.     "            holder = self.heap[j]\n",
  516.     "            self.heap[j] = self.heap[i]\n",
  517.     "            self.heap[i] = holder\n",
  518.     "            i = j    \n",
  519.     "            \n",
  520.     "    # This method implements the MIN_HEAPIFY operation for the min priority queue. The input is \n",
  521.     "    # the array index of the root node of the subtree to be heapify.\n",
  522.     "    #   Use heapq_var.heapify(i)        \n",
  523.     "    def heapify(self, i):\n",
  524.     "        l = left(i)\n",
  525.     "        r = right(i)\n",
  526.     "        heap = self.heap\n",
  527.     "        if l >= (self.heap_size-1) and heap[l]<heap[i]:\n",
  528.     "            smallest = l\n",
  529.     "        else:\n",
  530.     "            smallest = i\n",
  531.     "        if r >= (self.heap_size-1) and heap[r] < heap[largest]:\n",
  532.     "            smallest = r\n",
  533.     "        if smallest != i:\n",
  534.     "            heap[i], heap[smallest] = heap[smallest], heap[i]\n",
  535.     "            self.heapify(smallest)\n",
  536.     "\n",
  537.     "    # This method implements the EXTRACT_MIN operation. It returns the smallest key in \n",
  538.     "    # the min priority queue and removes this key from the min priority queue.\n",
  539.     "    #   Use key_var = heapq_var.heappop() \n",
  540.     "    def heappop(self):\n",
  541.     "        if self.heap_size < 1:\n",
  542.     "            raise ValueError('Heap underflow: There are no keys in the priority queue ')\n",
  543.     "        maxk = self.heap[0]\n",
  544.     "        self.heap[0] = self.heap[-1]\n",
  545.     "        self.heap.pop()\n",
  546.     "        self.heap_size-=1\n",
  547.     "        self.heapify(0)\n",
  548.     "        return maxk"
  549.    ]
  550.   },
  551.   {
  552.    "cell_type": "code",
  553.    "execution_count": 41,
  554.    "metadata": {
  555.     "deletable": false,
  556.     "editable": false,
  557.     "nbgrader": {
  558.      "checksum": "24bca6c047b8f9473f8bc38c57d6b0b5",
  559.      "grade": true,
  560.      "grade_id": "cell-94922952c1f6d73e",
  561.      "locked": true,
  562.      "points": 1,
  563.      "schema_version": 1,
  564.      "solution": false
  565.     }
  566.    },
  567.    "outputs": [],
  568.    "source": [
  569.     "# Please ignore this cell. This cell is for us to implement the tests \n",
  570.     "# to see if your code works properly. "
  571.    ]
  572.   },
  573.   {
  574.    "cell_type": "markdown",
  575.    "metadata": {
  576.     "deletable": false,
  577.     "editable": false,
  578.     "nbgrader": {
  579.      "checksum": "549d036086c8cfaf3a1c121c840a84be",
  580.      "grade": false,
  581.      "grade_id": "cell-a1d697aca93c202c",
  582.      "locked": true,
  583.      "schema_version": 1,
  584.      "solution": false
  585.     }
  586.    },
  587.    "source": [
  588.     "### Task 4. \n",
  589.     "\n",
  590.     "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`."
  591.    ]
  592.   },
  593.   {
  594.    "cell_type": "code",
  595.    "execution_count": 42,
  596.    "metadata": {
  597.     "deletable": false,
  598.     "nbgrader": {
  599.      "checksum": "ce29dba864f0d616282d83cf6c2dab9f",
  600.      "grade": false,
  601.      "grade_id": "cell-bc27d7bf8580d64a",
  602.      "locked": false,
  603.      "schema_version": 1,
  604.      "solution": true
  605.     }
  606.    },
  607.    "outputs": [
  608.     {
  609.      "name": "stdout",
  610.      "output_type": "stream",
  611.      "text": [
  612.       "[-10, 1, -6, 8, 3, -5, 4, 12, 9, 10, 6, 7]\n"
  613.      ]
  614.     }
  615.    ],
  616.    "source": [
  617.     "A = [6,4,7,9,10,-5,-6,12,8,3,1,-10]\n",
  618.     "my_heap = MinHeapq()\n",
  619.     "\n",
  620.     "for key in A:\n",
  621.     "    my_heap.heappush(key)\n",
  622.     "\n",
  623.     "my_heap_list = my_heap.heap\n",
  624.     "\n",
  625.     "print(my_heap_list)"
  626.    ]
  627.   },
  628.   {
  629.    "cell_type": "code",
  630.    "execution_count": null,
  631.    "metadata": {
  632.     "deletable": false,
  633.     "editable": false,
  634.     "nbgrader": {
  635.      "checksum": "c40c41c7c84c918a52ef50cac5992600",
  636.      "grade": true,
  637.      "grade_id": "cell-c76c6d24fa297106",
  638.      "locked": true,
  639.      "points": 1,
  640.      "schema_version": 1,
  641.      "solution": false
  642.     }
  643.    },
  644.    "outputs": [],
  645.    "source": [
  646.     "# Please ignore this cell. This cell is for us to implement the tests \n",
  647.     "# to see if your code works properly. "
  648.    ]
  649.   }
  650.  ],
  651.  "metadata": {
  652.   "kernelspec": {
  653.    "display_name": "Python 3",
  654.    "language": "python",
  655.    "name": "python3"
  656.   },
  657.   "language_info": {
  658.    "codemirror_mode": {
  659.     "name": "ipython",
  660.     "version": 3
  661.    },
  662.    "file_extension": ".py",
  663.    "mimetype": "text/x-python",
  664.    "name": "python",
  665.    "nbconvert_exporter": "python",
  666.    "pygments_lexer": "ipython3",
  667.    "version": "3.7.0"
  668.   }
  669.  },
  670.  "nbformat": 4,
  671.  "nbformat_minor": 2
  672. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top