Data_Structure_Heap.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Qheap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#use sorted array to keep all the element, second half of the tests were failed due to time out\n",
    "\n",
    "import sys\n",
    "Q = int(raw_input())\n",
    "\n",
    "queue = []\n",
    "\n",
    "for _ in range(Q):\n",
    "    que = map(int, raw_input().strip().split(\" \"))\n",
    "    if que[0] == 1:  #add element into heap\n",
    "        if len(queue) == 0:\n",
    "            queue.append(que[1])\n",
    "            \n",
    "        else:\n",
    "            count = 0\n",
    "            for i in range(len(queue)):\n",
    "                if queue[i] == que[1]: # element already existed, need need to add\n",
    "                    count == 1\n",
    "                    break\n",
    "            if count == 0: # add element into the heap\n",
    "                if queue[0] > que[1]: #add element at the head of the heap\n",
    "                    queue = [que[1]] + queue\n",
    "                elif queue[-1] < que[1]:\n",
    "                    queue = queue + [que[1]]\n",
    "                else: #add element somewhere in the middle\n",
    "                    for i in range(len(queue)):\n",
    "                        if queue[i]<que[1] and queue[i+1]>que[1]:\n",
    "                            queue = queue[:i+1] + [que[1]] + queue[i+1:]\n",
    "                            break\n",
    "\n",
    "    elif que[0] == 2: #delete element from heap\n",
    "        # if cur_min[-1] == que[1]:\n",
    "            # cur_min.pop()\n",
    "        queue.pop(queue.index(que[1]))\n",
    "                  \n",
    "    else: #print minimum element in the heap\n",
    "        print(queue[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# use heapq package and set()\n",
    "# For detailed explanation of heapq, --> https://github.com/qiwsir/algorithm/blob/master/heapq.md\n",
    "# set() keeps all the unique element in a list\n",
    "\n",
    "import sys\n",
    "from heapq import heappush, heappop\n",
    "\n",
    "heap = []\n",
    "item_lookup = set()\n",
    "\n",
    "def push(v):\n",
    "    heappush(heap, v)\n",
    "    item_lookup.add(v)\n",
    "    \n",
    "def discard(v):\n",
    "    item_lookup.discard(v)\n",
    "    \n",
    "def print_min():\n",
    "    while heap[0] not in item_lookup:\n",
    "        heappop(heap)\n",
    "      \n",
    "    print heap[0]\n",
    "    \n",
    "cmds = {\n",
    "    1: push,\n",
    "    2: discard,\n",
    "    3: print_min\n",
    "}\n",
    "\n",
    "n = int(raw_input())\n",
    "for _ in range(n):\n",
    "    data = map(int,raw_input().split(\" \"))\n",
    "    cmds[data[0]](*data[1:])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Jesse and Cookies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#This problem should be considered as a priority queue problem\n",
    "\n",
    "import sys\n",
    "from heapq import heappush, heappop, heapify, nsmallest\n",
    "\n",
    "[N,K] = map(int, raw_input().split(\" \"))\n",
    "a = map(int, raw_input().split(\" \"))\n",
    "\n",
    "if len(a) == 1 and a[0] < K:\n",
    "    print -1\n",
    "    \n",
    "count = 0\n",
    "heapify(a) #convert a from list to heap\n",
    "\n",
    "while len(a)>1 and a[0]<K:\n",
    "    b = heappop(a) + 2*heappop(a)\n",
    "    heappush(a, b)\n",
    "    count += 1\n",
    "\n",
    "if a[0] >=K:\n",
    "    print(count)\n",
    "else:\n",
    "    print(-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.5\n"
     ]
    }
   ],
   "source": [
    "a = [5,4]\n",
    "b = (a[0]+a[1]+0.0)/(2)\n",
    "print(\"%.1f\"%b)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}