Chapter_06_Heapsort/exercises_6.1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.1 Heaps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.1-1\n",
    "\n",
    "> What are the minimum and maximum numbers of elements in a heap of height $h$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Minimum: $1 + 2 + 2^2 + \\dots + 2^{h-1} + 1=2^h$\n",
    "\n",
    "Maximum: $1 + 2 + 2^2 + \\dots + 2^h = 2^{h+1} - 1$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.1-2\n",
    "\n",
    "> Show that an $n$-element heap has height $\\left \\lfloor \\lg n \\right \\rfloor$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{rrcll}\n",
    "2^h & \\le & n & \\le & 2^{h+1} - 1 \\\\\n",
    "2^h & \\le & n & < & 2^{h+1} \\\\\n",
    "h & \\le & \\lg n & < & h + 1\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.1-3\n",
    "\n",
    "> Show that in any subtree of a max-heap, the root of the subtree contains the largest value occurring anywhere in that subtree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Transitivity of $A[i] \\ge A[\\text{LEFT}(i)], A[i] \\ge A[\\text{RIGHT}(i)]$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.1-4\n",
    "\n",
    "> Where in a max-heap might the smallest element reside, assuming that all elements are distinct?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The leaves."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.1-5\n",
    "\n",
    "> Is an array that is in sorted order a min-heap?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Yes, since $\\text{PARENT}(i) < i$, $A[\\text{PARENT}(i)] \\le A[i]$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.1-6\n",
    "\n",
    "> Is the array with values $\\left \\langle 23, 17, 14, 6, 13, 10, 1, 5, 7, 12 \\right \\rangle$ a max-heap?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "No, $6 < 7$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.1-7\n",
    "\n",
    "> Show that, with the array representation for storing an $n$-element heap, the leaves are the nodes indexed by $\\left \\lfloor n/2 \\right \\rfloor + 1, \\left \\lfloor n/2 \\right \\rfloor + 2, \\dots, n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{rll}\n",
    "\\text{LEFT}(i) &>& n \\\\\n",
    "2i &>& n \\\\\n",
    "i &>& n / 2 \\\\\n",
    "i &>& \\left \\lfloor n/2 \\right \\rfloor + 1 \\\\\n",
    "\\end{array}\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.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}