MaxHeap implementation

MaxHeap.ipynb

{
  "cells": [
    {
      "metadata": {
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "class MaxHeap():\n    def __init__(self, data):\n        self.data = data\n        self._build_heap()\n\n    def _build_heap(self):\n        # start with one level above leaves\n        # which already satisfy max-heap prop\n        for i in reversed(range(len(self.data) // 2)):\n            self._heapify(i)\n\n    def _heapify(self, i):\n        # indexes of left nad right nodes\n        l = 2 * (i + 1) - 1\n        r = 2 * (i + 1)\n\n        # index which holds largest key of i, left, right\n        m = i\n        if l < len(self.data) and self.data[l] > self.data[i]: m = l\n        if r < len(self.data) and self.data[r] > self.data[m]: m = r\n\n        # swap element at i with largest child\n        if i != m:\n            self.data[i], self.data[m] = self.data[m], self.data[i]\n            # heapify subtree tha we changed\n            self._heapify(m)\n            \n    def get_max(self):\n        return self.data[0]\n    \n    def extract_max(self):\n        v = self.data.pop(0)\n        self._heapify(0)\n        return v\n    \n    def insert(self, x):\n        self.data.append(x)\n        self._build_heap()\n        \n    def set_element(self, i, x):\n        self.data[i] = x\n        self._build_heap()",
      "execution_count": 112,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "class Entry():\n    def __init__(self, val):\n        self.val = val\n\n    def __gt__(e1, e2):\n        return e1.val > e2.val\n\n    def __ge__(e1, e2):\n        return e1.val >= e2.val\n\n    def __eq__(e1, e2):\n        return e1.val == e2.val\n    \n    def __repr__(self):\n        return str(self.val)",
      "execution_count": 106,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "e1 = Entry(100)\ne2 = Entry(500)\nassert (False == (e1 == e2))\nassert (False == (e1 > e2))\nassert (False == (e1 >= e2))\nassert (True == (e1 < e2))",
      "execution_count": 107,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "a = [16, 4, 10, 14, 7, 100, 9, 3, 2, 8, 1]\na = [Entry(x) for x in a]\nh = MaxHeap(a)\nprint(h.get_max())\nprint(h.data)\nprint(h.extract_max())\nprint(h.data)\nprint(h.insert(Entry(-10)))\nprint(h.data)",
      "execution_count": null,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "a = [16, 4, 10, 14, 7, 100, 9, 3, 2, 8, 1]\na = [Entry(x) for x in a]\nh = MaxHeap(a)\nprint(h.get_max())\nprint(h.data)\nprint(h.extract_max())\nprint(h.data)\nprint(h.insert(Entry(-10)))\nprint(h.data)",
      "execution_count": 110,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": "100\n[100, 14, 16, 4, 8, 10, 9, 3, 2, 7, 1]\n100\n[16, 14, 4, 8, 10, 9, 3, 2, 7, 1]\nNone\n[16, 14, 9, 8, 10, 4, 3, 2, 7, 1, -10]\n"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "a = [16, 4, 10, 14, 7, 100, 9, 3, 2, 8, 1]\nh = MaxHeap(a)\nprint(h.get_max())\nprint(h.data)",
      "execution_count": 111,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": "100\n[100, 14, 16, 4, 8, 10, 9, 3, 2, 7, 1]\n"
        }
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3",
      "language": "python"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "nbconvert_exporter": "python",
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "version": "3.5.2",
      "pygments_lexer": "ipython3"
    },
    "gist": {
      "id": "",
      "data": {
        "description": "MaxHeap implementation",
        "public": true
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}