Max Binary Heap Implement using Python

max-binary-heap-python.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Heap(object):\n",
    "    \"\"\"Max Binary Heap\"\"\"\n",
    "    \n",
    "    def __init__(self, capacity=10):\n",
    "        self._default = object()\n",
    "        self.capacity = capacity\n",
    "        self.heap = [self._default] * self.capacity\n",
    "        \n",
    "    def __len__(self):\n",
    "        return len(self.heap) - self.heap.count(self._default)\n",
    "    \n",
    "    def __getitem__(self, i):\n",
    "        return self.heap[i]\n",
    "                  \n",
    "    def insert(self, item):\n",
    "        \"\"\"O(1) + O(logN) time complexity\"\"\"\n",
    "        if self.capacity == len(self):  # full\n",
    "            return\n",
    "        \n",
    "        self.heap[len(self)] = item\n",
    "        \n",
    "        self.fix_up(self.heap.index(item))  # check item's validation\n",
    "        \n",
    "    def fix_up(self, index):\n",
    "        \"\"\"\n",
    "        O(logN) time complexity\n",
    "        Violate:\n",
    "            1. child value > parent value\n",
    "        \"\"\"\n",
    "        parent_index = (index-1)//2\n",
    "        if index > 0 and self.heap[index] > self.heap[parent_index]: \n",
    "            # swap\n",
    "            self.swap(index, parent_index)\n",
    "            self.fix_up(parent_index)  # recursive\n",
    "    \n",
    "    def fix_down(self, index):\n",
    "        \"\"\"\n",
    "        O(logN) time complexity\n",
    "        Violate:\n",
    "            1. child value > parent value\n",
    "        \"\"\"\n",
    "        parent = self.heap[index]\n",
    "        left_child_index = 2 * index + 1\n",
    "        right_child_index = 2 * index + 2\n",
    "        largest_index = index\n",
    "        \n",
    "        if left_child_index < len(self) and self.heap[left_child_index] > parent:\n",
    "            largest_index = left_child_index\n",
    "        \n",
    "        if right_child_index < len(self) and self.heap[right_child_index] > self.heap[largest_index]: \n",
    "            largest_index = right_child_index\n",
    "            \n",
    "        if index != largest_index:\n",
    "            self.swap(index, largest_index)\n",
    "            self.fix_down(largest_index)  # recursive\n",
    "            \n",
    "    def heap_sort(self):\n",
    "        \"\"\"\n",
    "        O(NlogN) time complixity\n",
    "        \"\"\"\n",
    "        for i in range(0, len(self)):\n",
    "            self.poll()           \n",
    "        \n",
    "    def swap(self, i1, i2):\n",
    "        self.heap[i1], self.heap[i2] = self.heap[i2], self.heap[i1]\n",
    "            \n",
    "    def poll(self):\n",
    "        max_ = self.max_\n",
    "        \n",
    "        self.swap(0, len(self) - 1)  # swap first and last\n",
    "        self.heap[len(self) - 1] = self._default\n",
    "        self.fix_down(0)\n",
    "        \n",
    "        return max_\n",
    "    \n",
    "    @property\n",
    "    def max_(self):\n",
    "        return self.heap[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "h = Heap()\n",
    "h.insert(10)\n",
    "h.insert(5)\n",
    "h.insert(30)\n",
    "h.insert(15)\n",
    "h.insert(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "30\n",
      "15\n",
      "10\n",
      "5\n",
      "1\n",
      "<object object at 0x7f121b0bc480>\n",
      "<object object at 0x7f121b0bc480>\n",
      "<object object at 0x7f121b0bc480>\n",
      "<object object at 0x7f121b0bc480>\n",
      "<object object at 0x7f121b0bc480>\n"
     ]
    }
   ],
   "source": [
    "for i in h:\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "30"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "h.poll()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n",
      "5\n",
      "10\n",
      "1\n",
      "<object object at 0x7f121b0bc480>\n",
      "<object object at 0x7f121b0bc480>\n",
      "<object object at 0x7f121b0bc480>\n",
      "<object object at 0x7f121b0bc480>\n",
      "<object object at 0x7f121b0bc480>\n",
      "<object object at 0x7f121b0bc480>\n"
     ]
    }
   ],
   "source": [
    "for i in h:\n",
    "    print(i)"
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}