09. Priority Queues.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 9. Priority Queues"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This chapter introduces the concept of Priority Queues (most important of which is Heap data structures), their implications, and efficiency. It also presents three new sorting algorithms: Selection and Inertion Sort, as well as Heap Sort (based on the heap desctibed in the chapter)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Important Data Structures and Algorithms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Empty(Exception):\n",
    "    pass\n",
    "\n",
    "# my implementation of the Heap\n",
    "# without the additional 'container' class as described in the book\n",
    "# I think it brings unnecessary complexity to the code\n",
    "class Heap:\n",
    "\n",
    "    def __init__(self):\n",
    "        self._data = []\n",
    "\n",
    "    def __len__(self):\n",
    "        return len(self._data)\n",
    "\n",
    "    def print_data(self):\n",
    "        print(self._data)\n",
    "\n",
    "    def is_empty(self):\n",
    "        return len(self) == 0\n",
    "\n",
    "    def _parent(self, i):\n",
    "        return (i - 1) // 2\n",
    "\n",
    "    def _left(self, i):\n",
    "        return 2*i + 1\n",
    "\n",
    "    def _right(self, i):\n",
    "        return 2*i + 2\n",
    "\n",
    "    def _has_left(self, i):\n",
    "        return self._left(i) < len(self._data)\n",
    "\n",
    "    def _has_right(self, i):\n",
    "        return self._right(i) < len(self._data)\n",
    "\n",
    "    def _swap(self, i, j):\n",
    "        self._data[j], self._data[i] = self._data[i], self._data[j]\n",
    "\n",
    "    def _swap_up(self, i):\n",
    "        parent = self._parent(i)\n",
    "        if self._data[parent][1] > self._data[i][1] and i > 0:\n",
    "            self._swap(parent, i)\n",
    "            self._swap_up(parent)\n",
    "\n",
    "    def _swap_down(self, i):\n",
    "        if self._has_left(i):\n",
    "            left = self._left(i)\n",
    "            smallest = left\n",
    "            if self._has_right(i):\n",
    "                right = self._right(i)\n",
    "                if self._data[right][1] < self._data[left][1]:\n",
    "                    smallest = right\n",
    "            if self._data[smallest][1] < self._data[i][1]:\n",
    "                self._swap(smallest, i)\n",
    "                self._swap_down(smallest)\n",
    "        \n",
    "    def min(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('The heap is empty')\n",
    "        return self._data[0]\n",
    "\n",
    "    def remove_min(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('The heap is empty')\n",
    "        answer = self._data[0]\n",
    "        self._data[0] = self._data[-1]\n",
    "        del self._data[-1]\n",
    "        self._swap_down(0)\n",
    "        return answer\n",
    "    \n",
    "    def add(self, k, v):\n",
    "        self._data.append((k, v))\n",
    "        self._swap_up(len(self)-1)\n",
    "        \n",
    "    \n",
    "# Selection Sort implementation\n",
    "def selection_sort(A):\n",
    "    n = len(A)\n",
    "    for i in range(n):\n",
    "        min = i\n",
    "        for j in range(i+1, n):\n",
    "            if A[j] < A[min]:\n",
    "                min = j\n",
    "        A[i], A[min] = A[min], A[i]\n",
    "    return A\n",
    "\n",
    "# Insertion Sort implementation\n",
    "def insertion_sort(A):\n",
    "    n = len(A)\n",
    "    for i in range(1, n):\n",
    "        for j in range(i, 0, -1):\n",
    "            if A[j] < A[j-1]:\n",
    "                A[j], A[j-1] = A[j-1], A[j]\n",
    "            else:\n",
    "                break\n",
    "    return A\n",
    "\n",
    "# Heap Sort implementation\n",
    "\n",
    "# basically a _swap_up(self, i) method from the Heap class but modified for a random list A\n",
    "def heapify(A, n, i):\n",
    "    largest = i\n",
    "    left = 2*i + 1\n",
    "    right = 2*i + 2\n",
    "    if left < n and A[left] > A[i]:\n",
    "        largest = left\n",
    "    if right < n and A[right] > A[largest]:\n",
    "        largest = right\n",
    "    if i != largest:\n",
    "        A[largest], A[i] = A[i], A[largest]\n",
    "        heapify(A, n, largest)\n",
    "            \n",
    "\n",
    "def heap_sort(A):\n",
    "    n = len(A)\n",
    "    start = n // 2 - 1 # we start at the first node which has children\n",
    "    for i in range(start, -1, -1): # create a heap\n",
    "        heapify(A, n, i)  \n",
    "    for j in range(n-1, 0, -1): # put the largest numbers at the end and rearange the rest\n",
    "        A[j], A[0] = A[0], A[j]\n",
    "        heapify(A, j, 0) \n",
    "    return A\n",
    "    \n",
    "# using additional heap\n",
    "# less code, but results in O(n) space complexity instead of O(1)\n",
    "def heap_sort_not_inplace(A):\n",
    "    n = len(A)\n",
    "    sorted_A = [0] * n\n",
    "    h = Heap()\n",
    "    for i in range(n):\n",
    "        h.add('', A[i])\n",
    "    for i in range(n):\n",
    "        element = h.remove_min()[1]\n",
    "        sorted_A[i] = element\n",
    "    return sorted_A\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Reinforcement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### R-9.7"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Illustrate the execution of the selection-sort algorithm on the following input sequence: ${(22,15,36,44,10,3,9,13,29,25)}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "# with priority queue\n",
    "# phase 1\n",
    "# (22, 15, 36, 44, 10, 3, 9, 13, 29, 25) -> ()\n",
    "# (5, 36, 44, 10, 3, 9, 13, 29, 25) -> (22)\n",
    "# ..................\n",
    "# () -> (22, 15, 36, 44, 10, 3, 9, 13, 29, 25)\n",
    "# phase 2\n",
    "# (0) <- (22, 15, 36, 44, 10, 3, 9, 13, 29, 25)\n",
    "# (3) <- (22, 15, 36, 44, 10, 9, 13, 29, 25)\n",
    "# (3, 9) <- (22, 15, 36, 44, 10, 13, 29, 25)\n",
    "# .................\n",
    "# (3, 9, 10, 13, 15, 22, 25, 29, 36, 44) <- ()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### R-9.8"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Illustrate the execution of the insertion-sort algorithm on the input sequence of the previous problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "# with priority queue\n",
    "# phase 1\n",
    "# (22, 15, 36, 44, 10, 3, 9, 13, 29, 25) -> ()\n",
    "# (22, 15, 36, 44, 10, 9, 13, 29, 25) -> (3)\n",
    "# (22, 15, 36, 44, 10, 13, 29, 25) -> (3, 9)\n",
    "# () -> (3, 9, 10, 13, 15, 22, 25, 29, 36, 44)\n",
    "# ..................\n",
    "# phase 2\n",
    "# () <- (3, 9, 10, 13, 15, 22, 25, 29, 36, 44)\n",
    "# (3) <- (9, 10, 13, 15, 22, 25, 29, 36, 44)\n",
    "# (3, 9) <- (10, 13, 15, 22, 25, 29, 36, 44)\n",
    "# ..................\n",
    "# (3, 9, 10, 13, 15, 22, 25, 29, 36, 44) <- ()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### R-9.12"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider a situation in which a user has numeric keys and wishes to have a priority queue that is maximum-oriented. How could a standard (minoriented) priority queue be used for such a purpose?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "# you can add elements to the minoriented priority queue with the negative sign\n",
    "# then retrieve minimum value from the priority queue and take the absolute value of it\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Creativity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### C-9.26"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Show how to implement the stack ADT using only a priority queue and one additional integer instance variable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "class StackUsingHeap:\n",
    "\n",
    "    def __init__(self):\n",
    "        self._data = Heap()\n",
    "        self._i = 0\n",
    "\n",
    "    def __len__(self):\n",
    "        return len(self._data)\n",
    "\n",
    "    def is_empty(self):\n",
    "        return len(self._data) == 0\n",
    "      \n",
    "    def top(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('The stack is empty')\n",
    "        return self._data.min()[0]\n",
    "\n",
    "    def push(self, k):\n",
    "        self._data.add(k, self.i)\n",
    "        self._i -= 1\n",
    "\n",
    "    def pop(self):\n",
    "        if self.is_empty == True:\n",
    "            raise Empty('The stack is empty')\n",
    "        self._i += 1\n",
    "        return self._data.remove_min()[0]\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### C-9.27"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Show how to implement the FIFO queue ADT using only a priority queue and one additional integer instance variable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "class QueueUsingHeap:\n",
    "\n",
    "    def __init__(self):\n",
    "        self._data = Heap()\n",
    "        self._i = 0\n",
    "\n",
    "    def __len__(self):\n",
    "        return len(self._data)\n",
    "      \n",
    "    def first(self):\n",
    "        if len(self._data) == 0:\n",
    "            raise Empty('The queue is empty')\n",
    "        return self._data.min()[0]\n",
    "\n",
    "    def dequeue(self):\n",
    "        if len(self._data) == 0:\n",
    "            raise Empty('The queue is empty')\n",
    "        self._i -= 1\n",
    "        return self._data.remove_min()[0]\n",
    "  \n",
    "    def enqueue(self, k):\n",
    "        self._data.add(k, self.i)\n",
    "        self._i += 1\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### C-9.29"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Reimplement the SortedPriorityQueue using a Python list. Make sure to maintain remove min’s ${O(1)}$ performance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SortedPriorityQueue:\n",
    "\n",
    "    def __init__(self):\n",
    "        self._data = []\n",
    "\n",
    "    def __len__(self):\n",
    "        return len(self._data)\n",
    "  \n",
    "    def is_empty(self):\n",
    "        return len(self._data) == 0\n",
    "\n",
    "    def add(self, k, v):\n",
    "        if self.is_empty():\n",
    "            self._data.append((k, v))\n",
    "            return\n",
    "        for i in range(len(self)):\n",
    "            if k > self._data[i][0]:\n",
    "                self._data.insert(i, (k, v))\n",
    "                return\n",
    "            else:\n",
    "                continue\n",
    "        self._data.append((k, v))\n",
    "\n",
    "    def min(self):\n",
    "        return self._data[-1]\n",
    "\n",
    "    def remove_min(self):\n",
    "        return self._data.pop()\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### C-9.47"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Describe an in-place version of the selection-sort algorithm for an array that uses only ${O(1)}$ space for instance variables in addition to the array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [],
   "source": [
    "# I included this algorithm is in 'Important' section already with O(1) space-complexity\n",
    "# but I repeat it here for convenience\n",
    "def selection_sort(A):\n",
    "    n = len(A)\n",
    "    for i in range(n):\n",
    "        min = i\n",
    "        for j in range(i+1, n):\n",
    "            if A[j] < A[min]:\n",
    "                min = j\n",
    "        A[i], A[min] = A[min], A[i]\n",
    "    return A\n"
   ]
  }
 ],
 "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}