Must use python language and file i/o system to solve the question.Write the functions add(), delete( ), build( ), heapify( ) [swim up], sink() andheapSort() for a Min Heap Data Structure. Create a .txt file containing a bunch ofnumbers. Read the input from there and use the build() function to create a heap.Then ask the user to enter a command. 'A' for adding a new number, 'B' fordeleting, and 'S' for sorting.

Program Approach : Define the MinHeap class: The class has an attribute "heap" which is an empty…

Answered: Must use python language and file i/o…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

Expert Solution

Step 1

Program Approach :

Define the MinHeap class:
- The class has an attribute "heap" which is an empty list.
- The class has methods:
  - "add": Add a new element to the heap and restore the heap property by moving the element upwards in the heap.
  - "delete": Delete the minimum element from the heap, restore the heap property by moving the element downwards in the heap.
  - "build": Build a heap from a list of elements by iteratively sinking each element starting from the middle element of the list.
  - "heapify": Restore the heap property by moving an element upwards in the heap.
  - "sink": Restore the heap property by moving an element downwards in the heap.
  - "heap_sort": Sort the heap by repeatedly deleting the minimum element from the heap and appending it to a sorted list until the heap is empty.
  - "_swim_up": Helper method used by "add" and "heapify" to move an element upwards in the heap and restore the heap property.
  - "_sink": Helper method used by "delete" and "build" to move an element downwards in the heap and restore the heap property.
Define a function "read_input" that reads integers from a file and returns a list of integers.
Define a function "write_output" that writes integers to a file.
Define the "main" function:
- Read integers from the input file using "read_input".
- Build a heap from the list of integers using the "build" method of the MinHeap class.
- Enter into a loop that repeatedly prompts the user for a command:
  - If the command is "A", prompt the user for a number and add it to the heap using the "add" method of the MinHeap class.
  - If the command is "B", delete the minimum element from the heap using the "delete" method of the MinHeap class and print the deleted number.
  - If the command is "S", sort the heap using the "heap_sort" method of the MinHeap class, write the sorted list to the output file using "write_output", and print a message indicating that the heap was sorted and written to the output file.
  - If the command is "Q", exit the loop.
  - If the command is invalid, print an error message.
Call the "main" function if the script is being run as the main program.

Step by step

Solved in 4 steps with 9 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions