{ "cells": [ { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# To avoid issues about heap vs array size, we will simply use a Python list, and resize it as needed\n", "\n", "A = []\n", "def heap_size(A): return len(A)\n", "\n", "def Left(i): return 2*i+1 \n", "def Right(i): return 2*i+2\n", "def parent(i): return (i-1)//2\n", "\n", "def maximum(A):\n", " if heap_size(A) < 1: raise Exception('Heap is empty.')\n", " else: return A[0]\n", "\n", "def Heap_Extract_Max(A):\n", " if heap_size(A) < 1: raise Exception('Heap is empty.')\n", " max = A[0]\n", " if heap_size(A) == 1: A = []\n", " else: \n", " A[0] = A.pop()\n", " Max_Heapify(A,0)\n", " return max\n", "\n", "def Max_Heapify(A,i,heapsize=None):\n", " if heapsize==None: heapsize= heap_size(A)\n", " if Left(i) < heapsize and A[Left(i)] > A[i]: largest = Left(i)\n", " else: largest = i\n", " \n", " if Right(i) < heapsize and A[Right(i)] > A[largest]: largest = Right(i)\n", " if largest != i: \n", " A[i], A[largest] = A[largest], A[i]\n", " Max_Heapify(A, largest, heapsize)\n", " \n", "import math\n", "\n", "def Insert (A, key):\n", " A.append(-math.inf)\n", " Increase_Key(A, heap_size(A)-1, key)\n", "\n", "def Increase_Key(A, i, key):\n", " if key < A[i]: raise Exception('key < A[i]')\n", " A[i] = key\n", " while i > 0 and A[parent(i)] < A[i]:\n", " A[parent(i)], A[i] = A[i], A[parent(i)]\n", " i = parent(i)\n", " \n", "def Build_Max_Heap(A):\n", " for i in reversed(range(heap_size(A))): Max_Heapify(A,i)\n", "\n", "def HeapSort(A):\n", " Build_Max_Heap(A)\n", " heapsize = heap_size(A)\n", " for i in reversed(range(1,heap_size(A))):\n", " A[0], A[i] = A[i], A[0]\n", " heapsize -= 1\n", " Max_Heapify(A, 0, heapsize)" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0, 1, 2, 3]\n" ] } ], "source": [ "A = [0,2,1,3]\n", "HeapSort(A)\n", "print(A)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0, 16, 26, 18, 5, 14, 20, 21, 24, 3, 8, 1, 17, 28, 23, 2, 12, 27, 10, 9, 6, 29, 22, 4, 19, 13, 7, 11, 15, 25]\n" ] } ], "source": [ "import random\n", "\n", "A = list(range(1,30))\n", "random.shuffle(A)\n", "A.insert(0,0)\n", "print(A)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]\n" ] } ], "source": [ "HeapSort(A)\n", "print(A)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# For completeness below is a version with the index of the heap starting at index 1 (as e.g. in the Cormen et al. book)\n", "# To avoid issues about heap vs array size, we will simply use a Python list, and resize it as needed\n", "# The code is kept as close to the slides as possible. To avoid an index shift, we will place a dummy element (0) at the beginning of the list.\n", "A = [0]\n", "def heap_size(A): return len(A)-1\n", "\n", "def Left(i): return 2*i \n", "def Right(i): return 2*i+1\n", "def parent(i): return i//2\n", "\n", "def maximum(A):\n", " if heap_size(A) < 1: raise Exception('Heap is empty.')\n", " else: return A[1]\n", "\n", "def Heap_Extract_Max(A):\n", " if heap_size(A) < 1: raise Exception('Heap is empty.')\n", " max = A[1]\n", " if heap_size(A) == 1: A = [0]\n", " else: \n", " A[1] = A.pop()\n", " Max_Heapify(A,1)\n", " return max\n", "\n", "def Max_Heapify(A,i,heapsize=None):\n", " if heapsize==None: heapsize= heap_size(A)\n", " if Left(i) <= heapsize and A[Left(i)] > A[i]: largest = Left(i)\n", " else: largest = i\n", " \n", " if Right(i) <= heapsize and A[Right(i)] > A[largest]: largest = Right(i)\n", " if largest != i: \n", " A[i], A[largest] = A[largest], A[i]\n", " Max_Heapify(A, largest, heapsize)\n", " \n", "import math\n", "\n", "def Insert (A, key):\n", " A.append(-math.inf)\n", " Increase_Key(A, heap_size(A), key)\n", "\n", "def Increase_Key(A, i, key):\n", " if key < A[i]: raise Exception('key < A[i]')\n", " A[i] = key\n", " while i>1 and A[parent(i)] < A[i]:\n", " A[parent(i)], A[i] = A[i], A[parent(i)]\n", " i = parent(i)\n", " \n", "def Build_Max_Heap(A): # We will assume that A has a dummy element at the beginning\n", " for i in reversed(range(1,heap_size(A)+1)): Max_Heapify(A,i)\n", "\n", "def HeapSort(A):\n", " Build_Max_Heap(A)\n", " heapsize = heap_size(A)\n", " for i in reversed(range(2,heap_size(A)+1)):\n", " A[1], A[i] = A[i], A[1]\n", " heapsize -= 1\n", " Max_Heapify(A,1, heapsize)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0, 1, 2, 3]\n" ] } ], "source": [ "A = [0,2,1,3]\n", "HeapSort(A)\n", "print(A)" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0, 6, 4, 9, 16, 15, 22, 21, 20, 29, 3, 12, 10, 8, 25, 23, 13, 5, 18, 11, 2, 28, 17, 7, 24, 26, 14, 27, 19, 1]\n" ] } ], "source": [ "import random\n", "\n", "A = list(range(1,30))\n", "random.shuffle(A)\n", "A.insert(0,0)\n", "print(A)" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]\n" ] } ], "source": [ "HeapSort(A)\n", "print(A)" ] } ], "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": 1 }