Heap.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "9b055156",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[None, None, None, None, None, None, None, None, None, None]\n"
     ]
    }
   ],
   "source": [
    "heap = [None]*10\n",
    "print(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "fb9a5fc9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[None, 19, 7, 17, 3, 5, 12, 10, 1, 2]\n"
     ]
    }
   ],
   "source": [
    "heap[1] = 19\n",
    "heap[1*2] = 7\n",
    "heap[1*2+1] = 17\n",
    "heap[2*2] = 3\n",
    "heap[2*2+1] = 5\n",
    "heap[3*2] = 12\n",
    "heap[3*2+1] = 10\n",
    "heap[4*2] = 1\n",
    "heap[4*2+1] = 2\n",
    "print(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "a5f62588",
   "metadata": {},
   "outputs": [],
   "source": [
    "def left(i):\n",
    "    return i*2\n",
    "def right(i):\n",
    "    return i*2+1\n",
    "def parent(i):\n",
    "    return i//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "42afc7e8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_max_heap(h):\n",
    "    n = len(h) - 1\n",
    "    for i in range(n,1,-1):\n",
    "        p = parent(i)\n",
    "        if h[i] > h[p]:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "9c2fcb6c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[None, 19, 7, 17, 3, 5, 12, 10, 1, 2] True\n",
      "[None, 1, 2, 3] False\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\":\n",
    "    h = [None,19,7,17,3,5,12,10,1,2]\n",
    "    print(h, is_max_heap(h))\n",
    "    h = [None,1,2,3]\n",
    "    print(h, is_max_heap(h))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "ee834f06",
   "metadata": {},
   "outputs": [],
   "source": [
    "def max_heapify(heap,heap_size,i):\n",
    "    l = left(i)\n",
    "    r = right(i)\n",
    "    if l <= heap_size and heap[l] > heap[i]:\n",
    "        largest = l\n",
    "    else:\n",
    "        largest = i\n",
    "    if r <= heap_size and heap[r] > heap[largest]:\n",
    "        largest = r\n",
    "    \n",
    "    if largest == i:\n",
    "        return\n",
    "    heap[i], heap[largest] = heap[largest], heap[i]\n",
    "    max_heapify(heap,heap_size,largest)\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "f81ac0d8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[None, 19, 7, 12, 3, 5, 17, 10, 1, 2]\n",
      "[None, 19, 7, 17, 3, 5, 12, 10, 1, 2]\n",
      "\n",
      "[None, 1, 2, 3]\n",
      "[None, 3, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\":\n",
    "    h = [None,19,7,12,3,5,17,10,1,2]\n",
    "    print(h)\n",
    "    max_heapify(h,9,3)\n",
    "    print(h)\n",
    "    print()\n",
    "    h = [None,1,2,3]\n",
    "    print(h)\n",
    "    max_heapify(h,3,1)\n",
    "    print(h)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "40483dbe",
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_max_heap(h):\n",
    "    heap_size = len(h)-1\n",
    "    \n",
    "    for i in range(heap_size//2, 0, -1):\n",
    "        max_heapify(h, heap_size,i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "42a8e6e9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Before building heap [None, 12, 7, 1, 3, 10, 17, 19, 2, 5]\n",
      "After building heap [None, 19, 10, 17, 5, 7, 12, 1, 2, 3]\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\":\n",
    "    h = [None,12,7,1,3,10,17,19,2,5]\n",
    "    print(\"Before building heap\",h)\n",
    "    build_max_heap(h)\n",
    "    print(\"After building heap\",h)\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "dbbf88ec",
   "metadata": {},
   "outputs": [],
   "source": [
    "def heap_delete(h,num):\n",
    "    size = len(h)-1\n",
    "    last_heap = h[size]\n",
    "    for i in range(1, size):\n",
    "        if num == h[i]:\n",
    "            break\n",
    "    h[i],h[size] = h[size],h[i]\n",
    "    h.remove(num)\n",
    "    for i in range((size//2)-1,1,-1):\n",
    "        max_heapify(h,size,i)\n",
    "    return h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "c3f1c615",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[None, 19, 7, 17, 3, 5, 12, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\":\n",
    "    h = [None,19,7,12,3,5,17,10,1,2]\n",
    "    heap_delete(h,10)\n",
    "    print(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "07c187ba",
   "metadata": {},
   "outputs": [],
   "source": [
    "def heap_sort(h):\n",
    "    build_max_heap(h)\n",
    "    print(h)\n",
    "    heap_size = len(h)-1\n",
    "    \n",
    "    for i in range(heap_size,1,-1):\n",
    "        h[1], h[heap_size] = h[heap_size], h[1]\n",
    "        heap_size -= 1\n",
    "        max_heapify(h,heap_size,i)\n",
    "        print(\"sorting...\",h)\n",
    "    \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "bac192d7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[None, 19, 7, 17, 3, 5, 12, 10, 1, 2]\n",
      "sorting... [None, 2, 7, 17, 3, 5, 12, 10, 1, 19]\n",
      "sorting... [None, 1, 7, 17, 3, 5, 12, 10, 2, 19]\n",
      "sorting... [None, 10, 7, 17, 3, 5, 12, 1, 2, 19]\n",
      "sorting... [None, 12, 7, 17, 3, 5, 10, 1, 2, 19]\n",
      "sorting... [None, 5, 7, 17, 3, 12, 10, 1, 2, 19]\n",
      "sorting... [None, 3, 7, 17, 5, 12, 10, 1, 2, 19]\n",
      "sorting... [None, 17, 7, 3, 5, 12, 10, 1, 2, 19]\n",
      "sorting... [None, 7, 17, 3, 5, 12, 10, 1, 2, 19]\n",
      "[None, 7, 17, 3, 5, 12, 10, 1, 2, 19]\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\":\n",
    "    h = [None,19,7,12,3,5,17,10,1,2]\n",
    "    heap_sort(h)\n",
    "    print(h)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fc923f37",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}