Lab-02-Heaps, Heapsort, and Priority Queue.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Heaps, Heapsort, and Priority Queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this assignment, we look at an important data structure known as heap. Throughout the assignment, we assume that the input list is composed of pairs $(k, v)$ where $k$ is the weight and $v$ is the value. We want to manipulate the elements only based on the keys."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Helper functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random as rnd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Do NOT modify this cell!\n",
    "\n",
    "# Helper functions\n",
    "\n",
    "def toss_coin(p=0.5):\n",
    "    r = rnd.random()\n",
    "    if r <= p:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "\n",
    "def get_random_list(max_length=1000, min_length=0, key_start=0):\n",
    "    n = rnd.randint(min_length, max_length)\n",
    "    \n",
    "    values = list( range(n) )\n",
    "    rnd.shuffle( values )\n",
    "    \n",
    "    rls = []\n",
    "    \n",
    "    i = 0\n",
    "    while True:\n",
    "        # Toss a fair coin and decide whether to include this key or not.\n",
    "        if toss_coin():\n",
    "            rls.append( (key_start, values[i]) )\n",
    "            i += 1\n",
    "            \n",
    "            if i >= n:\n",
    "                break\n",
    "        \n",
    "        # Again toss a biased coin (p=0.9) to decide whether to increment the key.\n",
    "        if toss_coin(0.8):\n",
    "            key_start += 1\n",
    "            \n",
    "    rls2 = rls[:]\n",
    "    rnd.shuffle(rls2)\n",
    "    return rls2, rls\n",
    "    \n",
    "    \n",
    "def test_sort(sort_fn = None):\n",
    "    a = []\n",
    "    sort_fn(a)\n",
    "    assert a==[]\n",
    "\n",
    "    for i in range(10):\n",
    "        a, asorted = get_random_list(max_length=20, min_length=5, key_start=-10)\n",
    "        sort_fn(a)\n",
    "        assert [x[0] for x in a] == [x[0] for x in asorted]\n",
    "    \n",
    "\n",
    "    for i in range(5):\n",
    "        a, asorted = get_random_list(max_length=1000, min_length=100, key_start=-100)\n",
    "        sort_fn(a)\n",
    "        assert [x[0] for x in a] == [x[0] for x in asorted]\n",
    "        \n",
    "    print(\"Everything works!\")\n",
    "\n",
    "\n",
    "def test_heap_prop(heap, count):\n",
    "    for i in range(count):\n",
    "        l = 2*i + 1\n",
    "        r = 2*i + 2\n",
    "        if l < count and heap[i][0] < heap[l][0]:\n",
    "            return False\n",
    "        if r < count and heap[i][0] < heap[r][0]:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "\n",
    "def test_heap_prop_mult(make_heap_fn = None):\n",
    "    for i in range(10):\n",
    "        a, _ = get_random_list(max_length=20, min_length=5, key_start=-10)\n",
    "        make_heap_fn(a)\n",
    "        assert test_heap_prop(a, len(a))\n",
    "\n",
    "    for i in range(5):\n",
    "        a, _ = get_random_list(max_length=1000, min_length=100, key_start=-100)\n",
    "        make_heap_fn(a)\n",
    "        assert test_heap_prop(a, len(a))\n",
    "            \n",
    "    print(\"Everything works!\")\n",
    "            \n",
    "        \n",
    "def priority_queue_sort(a, pq_cls = None):\n",
    "    pq = pq_cls()\n",
    "    asorted = []\n",
    "    \n",
    "    for k, v in a:\n",
    "        pq.insert(k, v)\n",
    "    \n",
    "    while not pq.empty():\n",
    "        asorted.append(pq.extract_max())\n",
    "        \n",
    "    asorted.reverse()\n",
    "    return asorted\n",
    "    \n",
    "        \n",
    "def priority_queue_check(pq_cls = None):\n",
    "    for i in range(10):\n",
    "        a, asorted = get_random_list(max_length=20, min_length=5, key_start=-10)\n",
    "        a = priority_queue_sort(a, pq_cls)\n",
    "        \n",
    "        assert [x[0] for x in a] == [x[0] for x in asorted]\n",
    "    \n",
    "\n",
    "    for i in range(5):\n",
    "        a, asorted = get_random_list(max_length=1000, min_length=100, key_start=-100)\n",
    "        a = priority_queue_sort(a, pq_cls)\n",
    "        \n",
    "        assert [x[0] for x in a] == [x[0] for x in asorted]\n",
    "        \n",
    "    print(\"Everything works!\")\n",
    "  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Heap Functions\n",
    "\n",
    "Here we implement the heap functions _heapify_ and _make-heap_. In particular we would be implementing them for a max heap."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parent(i):\n",
    "    return (i - 1) // 2\n",
    "\n",
    "def left(i):\n",
    "    return 2*i + 1\n",
    "\n",
    "def right(i):\n",
    "    return 2*i + 2\n",
    "\n",
    "def heapify(alist, i, heap_size):\n",
    "    # Make sure that element at index i is at its proper place\n",
    "    \n",
    "    # Your code after this\n",
    "    \n",
    "    \n",
    "def make_heap(alist):\n",
    "    # Use heapify in order to make the elements in alist is in proper max-heap order.\n",
    "    \n",
    "    # Your code after this\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test. Do NOT modify this cell!\n",
    "\n",
    "test_heap_prop_mult(make_heap_fn = make_heap)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Heapsort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using the heap functions defined above, implement the heapsort."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def heap_sort(alist):\n",
    "    \n",
    "    # Your code after this.\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test. Do NOT modify this cell!\n",
    "\n",
    "test_sort( sort_fn = heap_sort )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Priority Queue\n",
    "\n",
    "Next, we will use the heap data structure. Here we start using Python classes for convenience. Please pay attention to the syntax."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class PriorityQueue:\n",
    "    def __init__(self):\n",
    "        self.heap = []\n",
    "        self.heap_size = 0\n",
    "        \n",
    "    def empty(self):\n",
    "        return self.heap_size == 0\n",
    "        \n",
    "    def maximum(self):\n",
    "        return self.heap[0]\n",
    "    \n",
    "    def extract_max(self):\n",
    "        # Return the maximum and remove it from the heap. Update self._heap_size as needed.\n",
    "        # You Code after this\n",
    "        \n",
    "    def update_key(self, i, key):\n",
    "        # Update the key of the element self._heap[i] to key. Make sure that the heap property is maintained.\n",
    "        \n",
    "    def insert(self, key, value):\n",
    "        # Insert (key, value) into the key so that the heap property is maintained. Update the self._heap_size as needed.\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test. Do NOT modify this cell!\n",
    "\n",
    "priority_queue_check( pq_cls = PriorityQueue )"
   ]
  }
 ],
 "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}