Question

1) Rewrite this heapify method RECURSIVELY in Python. def heapify(self): # assumes left subtree and right...

1) Rewrite this heapify method RECURSIVELY in Python.
def heapify(self):   # assumes left subtree and right subtree are valid heaps
        current=0
        done=False
        while not done:
            left=Heap._left(current)  
            right=Heap._right(current)
            # if left exists, compare to current
            if leftself.data[current]:
                bigger=left
            else:
                bigger=current
            if rightself.data[bigger]:
                bigger=right
            if bigger==current:
                done=True
            else:
                self.data[current],self.data[bigger]=self.data[bigger],self.data[current]
                current=bigger
0 0
Add a comment Improve this question Transcribed image text
Answer #1
# the entire logic is same as your method , just remove the while loop
# and execute the task inside while loop recursively by calling the heapify method again
# at the end of swapping logic for getting biggest for each root.

def heapify(data, size, index):
    bigger = index
    left = 2 * index + 1
    right = 2 * index + 2

    if left < size and data[index] < data[left]:
        bigger = left

    if right < size and data[bigger] < data[right]:
        bigger = right

    if bigger != index:
        data[index], data[bigger] = data[bigger], data[index]
        # recursive call to heapify method
        heapify(data, size, bigger)
Add a comment
Know the answer?
Add Answer to:
1) Rewrite this heapify method RECURSIVELY in Python. def heapify(self): # assumes left subtree and right...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • """ Add_to_front(self, val) and add_to_back(self, val) functions can be used which are already done in python...

    """ Add_to_front(self, val) and add_to_back(self, val) functions can be used which are already done in python class. Name of list is LList class node(object): def __init__(self, data, next=None): self.data = data self.next = next # Note: use the attributes directly; no setters or getters! class LList(object): def __init__(self): self._size = 0 self._head = None self._tail = None """ def set_data_at_index(self, idx, val): """ The value stored at index idx changes to val return True if the index was valid otherwise...

  • Python 3: Write a LinkedList method named contains, that takes a value as a parameter and...

    Python 3: Write a LinkedList method named contains, that takes a value as a parameter and returns True if that value is in the linked list, but returns False otherwise. class Node: """ Represents a node in a linked list """ def __init__(self, data): self.data = data self.next = None class LinkedList: """ A linked list implementation of the List ADT """ def __init__(self): self.head = None def add(self, val): """ Adds a node containing val to the linked list...

  • PYTHON -------------------------------------------------------- class LinkedList:    def __init__(self):        self.__head = None        self.__tail = None   

    PYTHON -------------------------------------------------------- class LinkedList:    def __init__(self):        self.__head = None        self.__tail = None        self.__size = 0    # Return the head element in the list    def getFirst(self):        if self.__size == 0:            return None        else:            return self.__head.element        # Return the last element in the list    def getLast(self):        if self.__size == 0:            return None        else:            return self.__tail.element    # Add an element to the beginning of the list    def addFirst(self, e):        newNode = Node(e) # Create a new node        newNode.next = self.__head # link...

  • PYTHON 3.8 class student(): def __init__(self, name = 'Bill', grade = 9, subjects = ['math','science']): self.name...

    PYTHON 3.8 class student(): def __init__(self, name = 'Bill', grade = 9, subjects = ['math','science']): self.name = name self.grade = grade self.subjects = subjects   def add_subjects(self):       print('Current subjects:')       print(self.subjects)       more_subjects = True       while more_subjects == True:           subject_input = input('Enter a subject to add: ')           if subject_input == '':               more_subjects = False               print(self.subjects)           else:               self.subjects.append(subject_input)               print(self.subjects) m = student()...

  • PYTHON QUESTION... Building a Binary Tree with extended Binary Search Tree and AVL tree. Create a...

    PYTHON QUESTION... Building a Binary Tree with extended Binary Search Tree and AVL tree. Create a class called MyTree with the methods __init__(x), getLeft(), getRight(), getData(), insert(x) and getHeight(). Each child should itself be a MyTree object. The height of a leaf node should be zero. The insert(x) method should return the node that occupies the original node's position in the tree. Create a class called MyBST that extends MyTree. Override the method insert(x) to meet the definitions of a...

  • PYTHON. Continues off another code. I don't understand this. Someone please help! Comment the lines please...

    PYTHON. Continues off another code. I don't understand this. Someone please help! Comment the lines please so I can understand LinkedList ADT: class myLinkedList:     def __init__(self):         self.__head = None         self.__tail = None         self.__size = 0     def insert(self, i, data):         if self.isEmpty():             self.__head = listNode(data)             self.__tail = self.__head         elif i <= 0:             self.__head = listNode(data, self.__head)         elif i >= self.__size:             self.__tail.setNext(listNode(data))             self.__tail = self.__tail.getNext()         else:             current = self.__getIthNode(i - 1)             current.setNext(listNode(data,...

  • PYTHON. Continues off another code(other code is below). I don't understand this. Someone please help! Comment...

    PYTHON. Continues off another code(other code is below). I don't understand this. Someone please help! Comment the lines please so I can understand. There are short and med files lengths for each the list of names/ids and then search id file. These are the input files: https://codeshare.io/aVQd46 https://codeshare.io/5M3XnR https://codeshare.io/2W684E https://codeshare.io/5RJwZ4 LinkedList ADT to store student records(code is below). Using LinkedList ADT instead of the Python List. You will need to use the Student ADT(code is below) Imports the Student class...

  • C++: PLEASE HELP~!!! ~~~~~~~~ Implement bool AVLTree::deleteNode(string ss) method. Function deleteNode() tries to delete the node...

    C++: PLEASE HELP~!!! ~~~~~~~~ Implement bool AVLTree::deleteNode(string ss) method. Function deleteNode() tries to delete the node containing value ss. If there is no such node, it returns false. Otherwise, it deletes the node, check the balance of the tree, rebalance the tree if it is necessary. When you delete a node, consider three different scenarios: -The node is a leaf -The node has only ONE child subtree -The node has two child subtrees Important: When you implement this project, do...

  • 1) Extend the Binary Search Tree ADT to include a public method leafCount that returns the...

    1) Extend the Binary Search Tree ADT to include a public method leafCount that returns the number of leaf nodes in the tree. 2) Extend the Binary Search Tree ADT to include a public method singleParent-Count that returns the number of nodes in the tree that have only one child. 3) The Binary search tree ADT is extended to include a boolean method similarTrees that receives references to two binary trees and determines whether the shapes of the trees are...

  • PYTHON The provided code in the ATM program is incomplete. Complete the run method of the...

    PYTHON The provided code in the ATM program is incomplete. Complete the run method of the ATM class. The program should display a message that the police will be called after a user has had three successive failures. The program should also shut down the bank when this happens. [comment]: <> (The ATM program allows a user an indefinite number of attempts to log in. Fix the program so that it displays a message that the police will be called...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT