{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "class HeapArray:\n",
    "\n",
    "    def __init__(self):\n",
    "        self._data = [] # indefinite size list; insert cannot fail\n",
    "        self._size = 0\n",
    "\n",
    "    def __str__(self):\n",
    "        return ' '.join([str(i) for i in self._data])\n",
    "\n",
    "    def is_empty(self):\n",
    "        return self._size == 0\n",
    "\n",
    "    def insert(self,e):\n",
    "        #self._data.insert(self._size,e)\n",
    "        self._data.append(e)\n",
    "        index = self._size\n",
    "        while index > 0 and self._data[index]  < self._data[(index-1)//2]:\n",
    "            # Send value up the tree\n",
    "            temp = self._data[index]\n",
    "            self._data[index] = self._data[(index-1)//2]\n",
    "            self._data[(index-1)//2] = temp\n",
    "            index = (index-1)//2\n",
    "        self._size = self._size + 1\n",
    "        return True\n",
    "\n",
    "    def delete_min(self):\n",
    "        if self.is_empty():\n",
    "            return None\n",
    "        elif self._size == 1:\n",
    "            return self._data.pop(0)\n",
    "        else:\n",
    "            smallest = self._data[0]\n",
    "            self._data[0] = self._data.pop(self._size-1)\n",
    "            self._size = self._size - 1\n",
    "            index = 0\n",
    "            while 2*index+1 < self._size:  # this condition means that there is at least one child\n",
    "                # check if there is a second child\n",
    "                if 2*index+2 < self._size: # 2 children\n",
    "                    if self._data[2*index+1] < self._data[2*index+2]: # left child smaller than right child\n",
    "                        if self._data[index] > self._data[2*index+1]:\n",
    "                            temp = self._data[index]\n",
    "                            self._data[index] = self._data[2*index+1]\n",
    "                            self._data[2*index+1] = temp\n",
    "                        index = 2*index+1\n",
    "                    else: # right child is smaller than left child\n",
    "                        if self._data[index] > self._data[2*index+2]:\n",
    "                            temp = self._data[index]\n",
    "                            self._data[index] = self._data[2*index+2]\n",
    "                            self._data[2*index+2] = temp\n",
    "                        index = 2*index+2\n",
    "                else: #one child\n",
    "                    if self._data[index] > self._data[2*index+1]:\n",
    "                        temp = self._data[index]\n",
    "                        self._data[index] = self._data[2*index+1]\n",
    "                        self._data[2*index+1] = temp\n",
    "                    index = 2*index+1\n",
    "            return smallest\n",
    "        # CASE ANALYSIS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 10 3 14 26 8\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "pq1 = HeapArray()\n",
    "pq1.insert(8)\n",
    "pq1.insert(14)\n",
    "pq1.insert(2)\n",
    "pq1.insert(10)\n",
    "pq1.insert(26)\n",
    "pq1.insert(3)\n",
    "pq1.insert(1)\n",
    "sm = pq1.delete_min()\n",
    "print(pq1)\n",
    "print(sm)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1,2,3,4\n"
     ]
    }
   ],
   "source": [
    "result = \"\"\n",
    "for x in [\"1\",\"2\",\"3\",\"4\"]:\n",
    "    result = result + x + \",\"\n",
    "result = result[0:-1]\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1,2,3,4\n"
     ]
    }
   ],
   "source": [
    "print(','.join([str(i) for i in [1,2,3,4]]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 5, 7, 99]\n"
     ]
    }
   ],
   "source": [
    "s = [2,5,7]\n",
    "s.append(99)\n",
    "print(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "## SWAPPING values of variables\n",
    "x = 5\n",
    "y = 7\n",
    "temp = y\n",
    "y = x\n",
    "x = temp\n",
    "print(x)\n",
    "print(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}