{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Practice Exercises: Heaps" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "What are the minimum and maximum numbers of elements in a heap of height \$h\$?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Prove by induction that a heap with \$n\$ nodes has exactly \$\\lceil n/2 \\rceil\$ leaves." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Use the following loop invariant to argue the correctness of HeapSort:\n", "\n", "At the start of each iteration of the **for** loop of lines 2--5, the subarray \$A[1..i]\$ is a max-heap containing the \$i\$ smallest elements of \$A[1..n]\$, and the subarray \$A[i+1..n]\$ contains the \$n-i\$ largest elements of \$A[1..n]\$, sorted." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 4" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Give an algorithm that -given a max-heap- outputs the second largest element in the heap. For full points your algorithm should run in \$\\Theta (1)\$ time." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 5" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "(a) How do Left(i), Right(i), Parent(i), and all other operations change if we use an array starting at index 1?\n", "\n", "(b) Implement a heap in Python using a list. Note that you can do this without (but also with) defining a class by defining operations manipulating a list. " ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "metadata": { "anaconda-cloud": {}, "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.0" } }, "nbformat": 4, "nbformat_minor": 0 }