heaps-stacks-queues.ipynb

{"cells":[{"metadata":{},"cell_type":"markdown","source":"# Heaps, Stacks, and Queues"},{"metadata":{},"cell_type":"markdown","source":"## Stack\n\n#### Last in first out (LIFO)\nAddition of new items and removal of existing items takes place at same end called \"top\"\n\n\n<figure>\n    <center>\n        <img src=\"https://upload.wikimedia.org/wikipedia/commons/thumb/2/29/Data_stack.svg/391px-Data_stack.svg.png\" alt=\"tree_data_structure\" width=\"400\"/>\n    </center>\n</figure>\n"},{"metadata":{},"cell_type":"markdown","source":"#### Common applications of `Stack` data structures.\n- **Reversing** the characters in a word\n- **Undo** mechanism in text editor\n- **Backtracking** is a process to access the most recent data element in a series of elements. (ex. dead end of a maze)"},{"metadata":{},"cell_type":"markdown","source":"#### Implementing a `Stack` in Python."},{"metadata":{"trusted":false},"cell_type":"code","source":"class Stack:\n    \n    # Using a list to implement a Stack class in Python\n    \n    def __init__(self):\n        # Create a new stack that is empty\n        self.items = []\n    \n    def isEmpty(self):\n        # Check if Stack is empty\n        return self.items == []\n    \n    def push(self, item):\n        # Add item to stack\n        self.items.append(item)\n    \n    def pop(self):\n        # Remove top item from Stack\n        return self.items.pop()\n    \n    def peek(self):\n        # Return top item from Stack without removing\n        return self.items[len(self.items)-1]\n    \n    def size(self):\n        # Return number of items in Stack\n        return len(self.items)","execution_count":1,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"#### Testing the implementation to get a better understanding."},{"metadata":{"trusted":false},"cell_type":"code","source":"# Create a new stack that is empty\ntest_stack = Stack()","execution_count":2,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Check if Stack is empty\ntest_stack.isEmpty()","execution_count":3,"outputs":[{"data":{"text/plain":"True"},"execution_count":3,"metadata":{},"output_type":"execute_result"}]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Add item to stack\ntest_stack.push(30)","execution_count":4,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"test_stack.push('birthday')","execution_count":5,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Return top item from Stack without removing\ntest_stack.peek()","execution_count":6,"outputs":[{"data":{"text/plain":"'birthday'"},"execution_count":6,"metadata":{},"output_type":"execute_result"}]},{"metadata":{"trusted":false},"cell_type":"code","source":"test_stack.push(True)","execution_count":7,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Return number of items in Stack\ntest_stack.size()","execution_count":8,"outputs":[{"data":{"text/plain":"3"},"execution_count":8,"metadata":{},"output_type":"execute_result"}]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Remove top item from Stack\ntest_stack.pop()","execution_count":9,"outputs":[{"data":{"text/plain":"True"},"execution_count":9,"metadata":{},"output_type":"execute_result"}]},{"metadata":{"trusted":false},"cell_type":"code","source":"test_stack.pop()","execution_count":10,"outputs":[{"data":{"text/plain":"'birthday'"},"execution_count":10,"metadata":{},"output_type":"execute_result"}]},{"metadata":{},"cell_type":"markdown","source":"### Example: Write a fuction to reverse characters in a string using a Stack."},{"metadata":{"trusted":false},"cell_type":"code","source":"def revstring(input_string):\n    \n    # Create an empty Stack\n    string_stack = Stack()\n    \n    # Add each character to Stack\n    for char in input_string:\n        string_stack.push(char)\n    \n    # Create empty string to store reversed\n    reversed_string = \"\"\n    \n    # Append popped off character \n    while not string_stack.isEmpty():\n        reversed_string += string_stack.pop()\n    \n    return reversed_string","execution_count":11,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"#### Test."},{"metadata":{"trusted":false},"cell_type":"code","source":"revstring('apple')","execution_count":12,"outputs":[{"data":{"text/plain":"'elppa'"},"execution_count":12,"metadata":{},"output_type":"execute_result"}]},{"metadata":{"trusted":false},"cell_type":"code","source":"revstring('x')","execution_count":13,"outputs":[{"data":{"text/plain":"'x'"},"execution_count":13,"metadata":{},"output_type":"execute_result"}]},{"metadata":{"trusted":false},"cell_type":"code","source":"revstring('1234567890')","execution_count":14,"outputs":[{"data":{"text/plain":"'0987654321'"},"execution_count":14,"metadata":{},"output_type":"execute_result"}]},{"metadata":{},"cell_type":"markdown","source":"### Example: Balanced Parentheses.\nEach opening symbol has a corresponding closing symbol and the pairs are properly nested. <br>\nGood examples:\n- `(()()()())`\n- `(((())))`\n- `(()((())()))` \n\nBad examples:\n- `((((((())`\n- `()))`\n- `(()()(()`\n\nImportant considerations:\n- going from L to R, the most recent `(` must match the next `)`\n- the very first `(` may have to wait til the end for its match\n- `)` match `(` in the reverse order of their appearance"},{"metadata":{"trusted":false},"cell_type":"code","source":"def check_parens(input_string):\n    \n    # Create an empty Stack\n    holding_stack = Stack()\n    \n    # Initiate variables for while\n    balanced = True\n    index = 0\n    \n    while index < len(input_string) and balanced:\n        \n        # Consider a single element\n        element = input_string[index]\n        \n        # If it is an open parenth push to stack\n        if element == \"(\":\n            holding_stack.push(element)\n        \n        # If it is a closing parenth\n        else:\n            # and the stack does not have a corresponding open\n            if holding_stack.isEmpty():\n                balanced = False\n            # and the stack has a match remove its match\n            else:\n                holding_stack.pop()\n        \n        index += 1\n    \n    # If balanced is not false and all opens have a match\n    if balanced and holding_stack.isEmpty():\n        return True\n    \n    else:\n        return False        ","execution_count":15,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"print(check_parens('((()))'))","execution_count":16,"outputs":[{"name":"stdout","output_type":"stream","text":"True\n"}]},{"metadata":{"trusted":false},"cell_type":"code","source":"print(check_parens('(()'))","execution_count":17,"outputs":[{"name":"stdout","output_type":"stream","text":"False\n"}]},{"metadata":{},"cell_type":"markdown","source":"### Example: Generalized balancing of symbols.\n\nNow we also consider `[]` and `{}` pairs. So now we must check that the element on the top of the stack is of the same type."},{"metadata":{"trusted":false},"cell_type":"code","source":"def check_general_parens(input_string):\n    \n    # Create an empty Stack\n    holding_stack = Stack()\n    \n    # Initiate variables for while\n    balanced = True\n    index = 0\n    \n    while index < len(input_string) and balanced:\n        \n        # Consider a single element\n        element = input_string[index]\n        \n        # If it is an open parenth push to stack\n        if element in \"([{\":\n            holding_stack.push(element)\n        \n        # If it is a closing parenth\n        else:\n            # and the stack does not have a corresponding open\n            if holding_stack.isEmpty():\n                balanced = False\n            # and the stack has a match remove its match\n            else:\n                top_element = holding_stack.pop()\n                if not check_match(top_element, element):\n                    balanced = False\n        \n        index += 1\n    \n    # If balanced is not false and all opens have a match\n    if balanced and holding_stack.isEmpty():\n        return True\n    \n    else:\n        return False         \n\n\ndef check_match(open, close):\n    \n    openers = \"([{\"\n    closers = \")]}\"\n    \n    return openers.index(open) == closers.index(close)","execution_count":18,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"print(check_general_parens('{{([][])}()}'))","execution_count":19,"outputs":[{"name":"stdout","output_type":"stream","text":"True\n"}]},{"metadata":{"trusted":false},"cell_type":"code","source":"print(check_general_parens('[{()]'))","execution_count":20,"outputs":[{"name":"stdout","output_type":"stream","text":"False\n"}]},{"metadata":{},"cell_type":"markdown","source":"### Example: Converting decimal to binary.\n\nBinary representation: All values stored in a computer are a string of binary digits. The decimal number system humans are familiar with is `base = 10` whereas binary is `base = 2`. The following are equivalent.\n\n$233_{10} = 2\\times10^{2} + 3\\times10^{1} + 3\\times10^{0}$\n\n$11101001_{2} = 1\\times2^{7} + 1\\times2^{6} + 1\\times2^{5} + 0\\times2^{4} + 1\\times2^{3} + 0\\times2^{2} + 0\\times2^{1} + 1\\times2^{0}$"},{"metadata":{},"cell_type":"markdown","source":"#### Solution: Divide by 2 algorithm.\n\nStart with integer greater than zero. Continually divide by 2 while keeping track of remainder."},{"metadata":{"trusted":false},"cell_type":"code","source":"def divide_by_two(integer_number):\n    \n    remainder_stack = Stack()\n    while integer_number > 0:\n        \n        remainder = integer_number % 2\n        remainder_stack.push(remainder)\n        \n        integer_number = integer_number // 2\n        \n    binary_string = \"\"\n    while not remainder_stack.isEmpty():\n        binary_string += str(remainder_stack.pop())\n        \n    return binary_string","execution_count":21,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"print(divide_by_two(42))","execution_count":22,"outputs":[{"name":"stdout","output_type":"stream","text":"101010\n"}]},{"metadata":{"trusted":false},"cell_type":"code","source":"print(divide_by_two(233))","execution_count":23,"outputs":[{"name":"stdout","output_type":"stream","text":"11101001\n"}]},{"metadata":{},"cell_type":"markdown","source":"### Example: Generalizing conversion to any base.\n\nThe integer $233_{10}$ above represented in other common forms like **octal** `base = 8` and **hexadecimal** `base = 16`.\n\n$351_{8} = 2\\times8^{2} + 5\\times8^{1} + 1\\times8^{0}$\n\n$E9_{16} = 14\\times16^{1} + 9\\times16^{0}$\n\nExtending the algorithm above to base values from $1-10$ is straightforward (just switch the `2` for desired base), but once we go past $10$ we need to create digits to represent remainders beyond $9$. "},{"metadata":{"trusted":false},"cell_type":"code","source":"def base_conversion(integer_number, base):\n    \n    digits = \"0123456789ABCDEF\"\n    \n    remainder_stack = Stack()\n    while integer_number > 0:\n        \n        remainder = integer_number % base\n        remainder_stack.push(remainder)\n        \n        integer_number = integer_number // base\n        \n    new_string = \"\"\n    while not remainder_stack.isEmpty():\n        \n        # This will return the digit at the given index\n        new_string += digits[remainder_stack.pop()]\n        \n    return new_string","execution_count":24,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"print(base_conversion(233, 2))","execution_count":25,"outputs":[{"name":"stdout","output_type":"stream","text":"11101001\n"}]},{"metadata":{"trusted":false},"cell_type":"code","source":"print(base_conversion(233, 8))","execution_count":26,"outputs":[{"name":"stdout","output_type":"stream","text":"351\n"}]},{"metadata":{"trusted":false},"cell_type":"code","source":"print(base_conversion(233, 16))","execution_count":27,"outputs":[{"name":"stdout","output_type":"stream","text":"E9\n"}]},{"metadata":{},"cell_type":"markdown","source":"## Queues\n\n<figure>\n    <center>\n        <img src=\"http://bit.ly/2Wasvwf\" alt=\"queue_data_structure\" width=\"600\"/>\n    </center>\n</figure>\n"},{"metadata":{},"cell_type":"markdown","source":"#### Common applications of `Queue` data structures.\n- **Serving** requests on a shared resource\n- **Scheduling** tasks"},{"metadata":{},"cell_type":"markdown","source":"#### Implementing a `Queue` in Python."},{"metadata":{"trusted":false},"cell_type":"code","source":"class Queue:\n    \n    # Using a list to implement a Queue class in Python\n    # We define position 0 as the rear\n    \n    def __init__(self):\n        # Create a new Queue that is empty\n        self.items = []\n    \n    def isEmpty(self):\n        # Check if Queue is empty\n        return self.items == []\n    \n    def enqueue(self, item):\n        # Add item to Queue\n        self.items.insert(0, item)\n    \n    def dequeue(self):\n        # Remove top item from Queue\n        return self.items.pop()\n    \n    def size(self):\n        # Return number of items in Queue\n        return len(self.items)","execution_count":28,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"#### Example: Hot potato simulation."},{"metadata":{"trusted":false},"cell_type":"code","source":"def hot_potato(name_list, num):\n    \n    potato_queue = Queue()\n    for name in name_list:\n        potato_queue.enqueue(name)\n        \n    while potato_queue.size() > 1:\n        for i in range(num):\n            potato_queue.enqueue(potato_queue.dequeue())\n        \n        potato_queue.dequeue()\n    \n    return potato_queue.dequeue()","execution_count":29,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"print(hot_potato([\"Bill\",\"David\",\"Susan\",\"Jane\",\"Kent\",\"Brad\"],7))","execution_count":30,"outputs":[{"name":"stdout","output_type":"stream","text":"Susan\n"}]},{"metadata":{},"cell_type":"markdown","source":"#### Example: Printing tasks simulation.\nStudents at the library send tasks to printer. Average day has 10 students working in a given hour. Each student typically prints up to twice in the time. The length of each task can be 1-20 pages. At low quality setting it can print 10 pages per minute and at high it can print 5 pages.\n\n**What is the average amount of time a task waits in the queue?**\n\nSolution:\n- Length of print task equally likely, so generate random number from 1-20\n- If there are 10 students that results in 20 tasks per hour or 1 task per 180 seconds. To simulate if a task is created at a particular second, choose random number from 1-180, and if it is 180 then task is generated."},{"metadata":{"trusted":false},"cell_type":"code","source":"class Printer:\n    \n    def __init__(self, ppm):\n        self.page_rate = ppm\n        self.current_task = None\n        self.time_remaining = 0\n        \n    def tick(self):\n        if self.current_task != None:\n            self.time_remaining = self.time_remaining - 1\n            if self.time_remaining <= 0:\n                self.current_task = None\n    \n    def busy(self):\n        if self.current_task != None:\n            return True\n        else:\n            return False\n        \n    def start_next(self, new_task):\n        self.current_task = new_task\n        self.time_remaining = new_task.get_pages() * 60/self.page_rate","execution_count":31,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"import random\n\nclass Task:\n    \n    def __init__(self, time):\n        self.time_stamp = time\n        self.pages = random.randrange(1, 21)\n        \n    def get_stamp(self):\n        return self.time_stamp\n    \n    def get_pages(self):\n        return self.pages\n    \n    def wait_time(self, current_time):\n        return current_time - self.time_stamp","execution_count":32,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"def new_print_task():\n    num = random.randrange(1, 181)\n    if num == 180:\n        return True\n    else:\n        return False\n\n\ndef printer_simulation(num_seconds, pages_per_minute):\n    \n    lab_printer = Printer(pages_per_minute)\n    print_queue = Queue()\n    waiting_times = []\n    \n    for current_second in range(num_seconds):\n        \n        if new_print_task():\n            task = Task(current_second)\n            print_queue.enqueue(task)\n        \n        if (not lab_printer.busy()) and (not print_queue.isEmpty()):\n            next_task = print_queue.dequeue()\n            waiting_times.append(next_task.wait_time(current_second))\n            lab_printer.start_next(next_task)\n            \n        lab_printer.tick()\n        \n    average_wait = sum(waiting_times)/len(waiting_times)\n    print(\"Average wait {:.2f} secs {} tasks remaining.\".format(average_wait, print_queue.size()))","execution_count":33,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"for i in range(10):\n    printer_simulation(3600, 5)","execution_count":34,"outputs":[{"name":"stdout","output_type":"stream","text":"Average wait 85.88 secs 0 tasks remaining.\nAverage wait 73.14 secs 0 tasks remaining.\nAverage wait 99.14 secs 0 tasks remaining.\nAverage wait 39.55 secs 0 tasks remaining.\nAverage wait 21.94 secs 2 tasks remaining.\nAverage wait 75.61 secs 0 tasks remaining.\nAverage wait 164.60 secs 2 tasks remaining.\nAverage wait 59.88 secs 3 tasks remaining.\nAverage wait 68.27 secs 1 tasks remaining.\nAverage wait 83.76 secs 0 tasks remaining.\n"}]},{"metadata":{"trusted":false},"cell_type":"code","source":"for i in range(10):\n    printer_simulation(3600, 10)","execution_count":35,"outputs":[{"name":"stdout","output_type":"stream","text":"Average wait 53.00 secs 0 tasks remaining.\nAverage wait 15.09 secs 0 tasks remaining.\nAverage wait 11.00 secs 0 tasks remaining.\nAverage wait 5.38 secs 0 tasks remaining.\nAverage wait 11.75 secs 1 tasks remaining.\nAverage wait 18.90 secs 0 tasks remaining.\nAverage wait 17.94 secs 0 tasks remaining.\nAverage wait 25.25 secs 0 tasks remaining.\nAverage wait 69.00 secs 2 tasks remaining.\nAverage wait 23.06 secs 0 tasks remaining.\n"}]},{"metadata":{},"cell_type":"markdown","source":"## `Deque` (Double Ended Queue)\n\nOrdered collection of items, but there is no restriction on how items can be added or removed."},{"metadata":{},"cell_type":"markdown","source":"### Implementing a `Deque` in Python"},{"metadata":{"trusted":false},"cell_type":"code","source":"class Deque:\n    def __init__(self):\n        self.items = []\n\n    def isEmpty(self):\n        return self.items == []\n\n    def addFront(self, item):\n        self.items.append(item)\n\n    def addRear(self, item):\n        self.items.insert(0,item)\n\n    def removeFront(self):\n        return self.items.pop()\n\n    def removeRear(self):\n        return self.items.pop(0)\n\n    def size(self):\n        return len(self.items)","execution_count":36,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"**Note:** Removing/adding items from front is $O(1)$ and removing/adding items from back is $O(n)$."},{"metadata":{},"cell_type":"markdown","source":"#### Example. Palindrome checker.\n\nA palindrome is a string that reads the same forward and backward. Check if string is palindrome."},{"metadata":{"trusted":false},"cell_type":"code","source":"def palindrome_checker(input_string):\n    \n    string_deque = Deque()\n    \n    for char in input_string:\n        string_deque.addRear(char)\n        \n    still_equal = True\n    \n    while string_deque.size() > 1 and still_equal:\n        \n        first = string_deque.removeFront()\n        last = string_deque.removeRear()\n        \n        if first != last:\n            still_equal = False\n    \n    return still_equal","execution_count":37,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"print(palindrome_checker(\"lsdkjfskf\"))","execution_count":38,"outputs":[{"name":"stdout","output_type":"stream","text":"False\n"}]},{"metadata":{"trusted":false},"cell_type":"code","source":"print(palindrome_checker(\"radar\"))","execution_count":39,"outputs":[{"name":"stdout","output_type":"stream","text":"True\n"}]},{"metadata":{},"cell_type":"markdown","source":"# Trees\n[SOURCE](http://interactivepython.org/runestone/static/pythonds/Trees/toctree.html)\n\n<figure>\n    <center>\n        <img src=\"https://i.ytimg.com/vi/qH6yxkw0u78/maxresdefault.jpg\" alt=\"tree_data_structure\" width=\"600\"/>\n    </center>\n</figure>\n\nA tree consists of a set of nodes and a set of edges that connect pairs of node. Some properties of a tree:\n- Nonlinear data structure\n- One node of the tree is designated the `root` node\n- every node `n`, except the `root` node, is connected by an edge from exactly one other node `p`, where `p` is the parent of `n`.\n- A unique path traverses from the `root` to each node.\n- If each node in the tree has a maximum of two children, we say that the tree is a **binary tree**.\n\n"},{"metadata":{},"cell_type":"markdown","source":"#### List of lists representation.\nFirst element of list will store root node. Second element will store left subtree. Third element will store right subtree... This structure is recursive. A subtree that has a root value and two empty lists is a leaf node. It is also generalizable to trees that are not binary trees."},{"metadata":{"trusted":false},"cell_type":"code","source":"myTree = ['a', ['b', ['d',[],[]], ['e',[],[]] ], ['c', ['f',[],[]], []] ]","execution_count":40,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"print(myTree)","execution_count":41,"outputs":[{"name":"stdout","output_type":"stream","text":"['a', ['b', ['d', [], []], ['e', [], []]], ['c', ['f', [], []], []]]\n"}]},{"metadata":{"trusted":false},"cell_type":"code","source":"print('left subtree = ', myTree[1])","execution_count":42,"outputs":[{"name":"stdout","output_type":"stream","text":"left subtree =  ['b', ['d', [], []], ['e', [], []]]\n"}]},{"metadata":{"trusted":false},"cell_type":"code","source":"print('root = ', myTree[0])","execution_count":43,"outputs":[{"name":"stdout","output_type":"stream","text":"root =  a\n"}]},{"metadata":{"trusted":false},"cell_type":"code","source":"print('right subtree = ', myTree[2])","execution_count":44,"outputs":[{"name":"stdout","output_type":"stream","text":"right subtree =  ['c', ['f', [], []], []]\n"}]},{"metadata":{},"cell_type":"markdown","source":"## Depth-First Search (DFS) with a `Stack`\nGo down a path until we get to a dead end; then we **backtrack** (by popping a stack) to get an alternative path.\n\n1. Create a stack\n2. Create a new choice point\n3. Push the choice point onto the stack\n4. while (not found and stack is not empty)\n    - Pop the stack\n    - Find all possible choices after the last one tried\n    - Push these choices onto the stack\n5. Return\n\n\n## Breadth-First Search (BFS) with a `Queue`\nExplore all the nearest possibilities by finding all possible successors and enqueue them to a queue.\n\n1. Create a queue\n2. Create a new choice point\n3. Enqueue the choice point onto the queue\n4. while (not found and queue is not empty)\n    - Dequeue the queue\n    - Find all possible choices after the last one tried\n    - Enqueue these choices onto the queue\n5. Return"},{"metadata":{},"cell_type":"markdown","source":"## Heap\n\nA heap is a tree-based data structure that:\n- is almost complete \n- satisfies the *heap* property meaning a level cannot have empty slots (unless it is the last level)\n\n### What is the heap property?\nThat there are two types of heaps:\n1. **Min Heap:** if `P` is a parent node of `C` then the value of `P` is less than or equal to the value of `C`.\n2. **Max Heap:** if `P` is a parent node of `C` then the value of `P` is greater than or equal to the value of `C`. \n\n**Note:** Heaps are *partially* sorted.\n<figure>\n    <center>\n        <img src=\"https://www.geeksforgeeks.org/wp-content/uploads/MinHeapAndMaxHeap.png\" alt=\"heap_data_structure\" width=\"600\"/>\n    </center>\n</figure>"},{"metadata":{},"cell_type":"markdown","source":"#### Common applications of `Heap` data structures.\n- maximally efficient implementation of the **priority queue**\n- the binary heap was introduced for the **heapsort** algorithm\n- crucial in graph algorithms (eg. Dijkstra's shortest-path algorithm, ...)"},{"metadata":{},"cell_type":"markdown","source":"### Implementing a `Heap` in Python\n- Binary heap is relatively easy to implement as an `array` because it is full and we know the structure. "},{"metadata":{},"cell_type":"markdown","source":"### Operations on a `Heap` data structure.\n- **ADD** New items are always added to the top and are *bubble sorted* their way up.\n- **PEAK** Look at the smallest/largest element (root node).\n- **REMOVE** From root node, put last element added at the root, and move it down sequentially."},{"metadata":{},"cell_type":"markdown","source":"#### Heapsort.\n<figure>\n    <center>\n        <img src=\"https://upload.wikimedia.org/wikipedia/commons/1/1b/Sorting_heapsort_anim.gif\" width=\"600\"/>\n    </center>\n</figure>"},{"metadata":{"trusted":false},"cell_type":"code","source":"","execution_count":null,"outputs":[]}],"metadata":{"kernelspec":{"name":"python3","display_name":"Python 3","language":"python"},"language_info":{"name":"python","version":"3.10.4","mimetype":"text/x-python","codemirror_mode":{"name":"ipython","version":3},"pygments_lexer":"ipython3","nbconvert_exporter":"python","file_extension":".py"}},"nbformat":4,"nbformat_minor":2}