Chapter_06_Heapsort/exercises_6.5.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.5 Priority queues"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.5-1\n",
    "\n",
    "> Illustrate the operation of HEAP-EXTRACT-MAX on the heap $A = \\left \\langle 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1 \\right \\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Return 15 and $A = \\left \\langle 1, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2 \\right \\rangle$,\n",
    "\n",
    "![](img/6.5-1_1.png)\n",
    "\n",
    "MAX-HEAPIFY$(A)$: $A = \\left \\langle 13, 12, 9, 5, 6, 8, 7, 4, 0, 1, 2 \\right \\rangle$.\n",
    "\n",
    "![](img/6.5-1_2.png)\n",
    "\n",
    "![](img/6.5-1_3.png)\n",
    "\n",
    "![](img/6.5-1_4.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.5-2\n",
    "\n",
    "> Illustrate the operation of MAX-HEAP-INSERT$(A, 10)$ on the heap $A = \\left \\langle15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1 \\right \\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Insert: $A = \\left \\langle15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1, -\\infty \\right \\rangle$.\n",
    "\n",
    "![](img/6.5-2_1.png)\n",
    "\n",
    "Increase: $A = \\left \\langle15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1, 10 \\right \\rangle$\n",
    "\n",
    "![](img/6.5-2_2.png)\n",
    "\n",
    "Heapify: \n",
    "\n",
    "$A = \\left \\langle15, 13, 9, 5, 12, 10, 7, 4, 0, 6, 2, 1, 8\\right \\rangle$\n",
    "\n",
    "![](img/6.5-2_3.png)\n",
    "\n",
    "$A = \\left \\langle15, 13, 10, 5, 12, 9, 7, 4, 0, 6, 2, 1, 8\\right \\rangle$\n",
    "\n",
    "![](img/6.5-2_4.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.5-3\n",
    "\n",
    "> Write pseudocode for the procedures HEAP-MINIMUM, HEAP-EXTRACT-MIN, HEAP-DECREASE-KEY, and MIN-HEAP-INSERT that implement a min-priority queue with a min-heap."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def heap_minimum(a):\n",
    "    assert(len(a) > 0)\n",
    "    return a[0]\n",
    "\n",
    "\n",
    "def heap_extract_min(a):\n",
    "    assert(len(a) > 0)\n",
    "    val = a[0]\n",
    "    a[0] = a[-1]\n",
    "    del a[-1]\n",
    "    min_heapify(a, 0)\n",
    "    return val\n",
    "\n",
    "\n",
    "def heap_decrease_key(a, i, key):\n",
    "    assert(key <= a[i])\n",
    "    a[i] = key\n",
    "    while i > 0 and a[i] < a[parent(i)]:\n",
    "        a[i], a[parent(i)] = a[parent(i)], a[i]\n",
    "        i = parent(i)\n",
    "\n",
    "\n",
    "def min_heap_insert(a, key):\n",
    "    a.append(1e100)\n",
    "    heap_decrease_key(a, len(a) - 1, key)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.5-4\n",
    "\n",
    "> Why do we bother setting the key of the inserted node to $-\\infty$ in line 2 of MAXHEAP-INSERT when the next thing we do is increase its key to the desired value?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To make $key \\ge A[i]$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.5-5\n",
    "\n",
    "> Argue the correctness of HEAP-INCREASE-KEY using the following loop invariant:\n",
    "\n",
    ">> At the start of each iteration of the while loop of lines 4–6, the subarray $A[1 \\dots A.heap\\text{-}size]$ satisfies the max-heap property, except that there may be one violation: $A[i]$ may be larger than $A[\\text{PARENT}(i)]$.\n",
    "\n",
    "> You may assume that the subarray $A[1 \\dots A.heap\\text{-}size]$ satisfies the max-heap property at the time HEAP-INCREASE-KEY is called."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Correct."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.5-6\n",
    "\n",
    "> Each exchange operation on line 5 of HEAP-INCREASE-KEY typically requires three assignments. Show how to use the idea of the inner loop of INSERTION-SORT to reduce the three assignments down to just one assignment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def heap_increase_key(a, i, key):\n",
    "    assert(key >= a[i])\n",
    "    while i > 0 and key > a[parent(i)]:\n",
    "        a[i] = a[parent(i)]\n",
    "        i = parent(i)\n",
    "    a[i] = key\n",
    "\n",
    "\n",
    "def max_heap_insert(a, key):\n",
    "    a.append(-1e100)\n",
    "    heap_increase_key(a, len(a) - 1, key)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.5-7\n",
    "\n",
    "> Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.heap = []\n",
    "        self.inc = 0\n",
    "\n",
    "    def push(self, val):\n",
    "        self.inc += 1\n",
    "        min_heap_insert(self.heap, (self.inc, val))\n",
    "\n",
    "    def front(self):\n",
    "        return heap_minimum(self.heap)\n",
    "\n",
    "    def pop(self):\n",
    "        return heap_extract_min(self.heap)\n",
    "\n",
    "\n",
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.heap = []\n",
    "        self.inc = 0\n",
    "\n",
    "    def push(self, val):\n",
    "        self.inc += 1\n",
    "        max_heap_insert(self.heap, (self.inc, val))\n",
    "\n",
    "    def top(self):\n",
    "        return heap_maximum(self.heap)\n",
    "\n",
    "    def pop(self):\n",
    "        return heap_extract_max(self.heap)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.5-8\n",
    "\n",
    "> The operation HEAP-DELETE$(A, i)$ deletes the item in node $i$ from heap $A$. Give an implementation of HEAP-DELETE that runs in $O(\\lg n)$ time for an n-element max-heap."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def heap_delete(a, i):\n",
    "    if i == len(a) - 1:\n",
    "        del a[-1]\n",
    "    else:\n",
    "        a[i] = a[-1]\n",
    "        del a[-1]\n",
    "        max_heapify(a, i)\n",
    "        heap_increase_key(a, i, a[i])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.5-9\n",
    "\n",
    "> Give an $O(n \\lg k)$-time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total number of elements in all the input lists. (Hint: Use a minheap for $k$-way merging.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge_lists(lists):\n",
    "    k = len(lists)\n",
    "    heap = []\n",
    "    for i in range(k):\n",
    "        if len(lists[i]) > 0:\n",
    "            min_heap_insert(heap, (lists[i][0], i))\n",
    "    idx = [0 for lst in lists]\n",
    "    a = []\n",
    "    while len(heap) > 0:\n",
    "        val, i = heap_extract_min(heap)\n",
    "        a.append(val)\n",
    "        idx[i] += 1\n",
    "        if idx[i] < len(lists[i]):\n",
    "            min_heap_insert(heap, (lists[i][idx[i]], i))\n",
    "    return a"
   ]
  }
 ],
 "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.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}