Heap Sort.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sorted array is\n",
      "5\n",
      "6\n",
      "7\n",
      "11\n",
      "12\n",
      "13\n"
     ]
    }
   ],
   "source": [
    "###########################################\n",
    "# Heap Sort using Python\n",
    "# By Giriraj Vaishnav\n",
    "###########################################\n",
    " \n",
    "# To heapify subtree rooted at index i.\n",
    "# n is size of heap\n",
    " \n",
    "def heapify(arr, n, i):\n",
    "    largest = i  # Initialize largest as root\n",
    "    l = 2 * i + 1     # left = 2*i + 1\n",
    "    r = 2 * i + 2     # right = 2*i + 2\n",
    " \n",
    "    # See if left child of root exists and is\n",
    "    # greater than root\n",
    "    if l < n and arr[largest] < arr[l]:\n",
    "        largest = l\n",
    " \n",
    "    # See if right child of root exists and is\n",
    "    # greater than root\n",
    "    if r < n and arr[largest] < arr[r]:\n",
    "        largest = r\n",
    " \n",
    "    # Change root, if needed\n",
    "    if largest != i:\n",
    "        arr[i], arr[largest] = arr[largest], arr[i]  # swap\n",
    " \n",
    "        # Heapify the root.\n",
    "        heapify(arr, n, largest)\n",
    " \n",
    "# The main function to sort an array of given size\n",
    "  \n",
    "def heapSort(arr):\n",
    "    n = len(arr)\n",
    " \n",
    "    # Build a maxheap.\n",
    "    for i in range(n//2 - 1, -1, -1):\n",
    "        heapify(arr, n, i)\n",
    " \n",
    "    # One by one extract elements\n",
    "    for i in range(n-1, 0, -1):\n",
    "        arr[i], arr[0] = arr[0], arr[i]  # swap\n",
    "        heapify(arr, i, 0)\n",
    " \n",
    " \n",
    "# Driver code\n",
    "arr = [12, 11, 13, 5, 6, 7]\n",
    "heapSort(arr)\n",
    "n = len(arr)\n",
    "print(\"Sorted array is\")\n",
    "for i in range(n):\n",
    "    print(\"%d\" % arr[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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}