Write a function parent_index_3_heap(child_index) that returns the index of the parent of the node at the...

Write a function parent_index_3_heap(child_index) that returns the index of the parent of the node at the given child_index. A None value should be returned if the child has no parent.

Notes:

This function is obviously for a 3-heap!
The values in the heap list start at index 1 - that is the root of the heap is at index 1 in the heap list.

This is for Python

Solutions

Expert Solution

Logic : A heap is always stored in an array as the level order traversal of complete binary tree. For every kth element of the array (except 0th index) :

its left child is located at 2*k index
its right child is located at 2*k+1. index
its parent is located at k/2 index

Have a look athe below complete binary tree:

for index 8 the parent will be 8/2 = 4.

for index 23 the parent will be 23/2 = 11 and so on...

Have a look at the below code. I have put comments wherever required for better understanding.

Happy Learning!

venereology answered 1 year ago

Next > < Previous

Related Solutions

In Python: def _nodeAtIndex(self, index): """Returns the reference to the node at the given index; If...

In Python: def _nodeAtIndex(self, index): """Returns the reference to the node at the given index; If index is out of range, raise IndexError """ # PROBLEM 2 # You can assume that index is non-negative. # You need to traverse the list and stop at the required index. # YOUR CODE HERE (THIS IS WHAT I HAVE CURRENTLY WRITTEN BUT I"M STUCK AND DON"T KNOW WHAT TO DO) while current != None: # use a while-loop. plist.append(current._element) # process the...

Write a function that takes a valid stringlist and returns the index of the smallest element...

Write a function that takes a valid stringlist and returns the index of the smallest element in the list represented by the stringlist. You may not use split(). Examples: >>> stringlist min index('[123,53,1,8]') # 1 is smallest2 >>> stringlist min index('[1,2,345,0]') # 0 is smallest3 >>> stringlist min index('[5] ') # 5 is smallest0

Write a function child_indices(parent, branch_factor) that returns a list containing the list of indices where the...

Write a function child_indices(parent, branch_factor) that returns a list containing the list of indices where the children of the node at index parent will be stored for a heap list with the given branch_factor (ie, a branch_factor-heap). Python language Notes: The function should return all possible indices and the indices should be in order from smallest to biggest. The values in the heap list start at index 1 - that is the root of the heap is at index 1...

Assume that struct Node { int item; Node* link; }; typedef Node* NodePtr; 1. Write function...

Assume that struct Node { int item; Node* link; }; typedef Node* NodePtr; 1. Write function void list_head_insert(NodePtr& head, int entry); The function should insert a new Node, in which entry is the value of attribute item, in front of the linked list that is pointed by head. 2. Write function void list_head_remove(NodePtr& head); The function will remove the first node from the linked list that is pointed by head. 3. Write function NodePtr list_search(NodePtr head, int target); The function...

1a Write a function COTlistRange(xstart,xend,xstep) that returns a list that has: - as index 0...

1a Write a function COTlistRange(xstart,xend,xstep) that returns a list that has: - as index 0 item, the value of xstart - as index 1 item, the value xstart+xstep - as index 2 item, the value (xstart+xstep)+xstep, and so on as long as the value does equal or pass the value of xend. However, the function should return an empty string if for positive xstep, xstart>xend or if for negative xstep, xstart < xend. Here are...

Write a function COTtupleRange(xstart,xend,xstep) that returns a tuple that has: - as index 0 item,...

Write a function COTtupleRange(xstart,xend,xstep) that returns a tuple that has: - as index 0 item, the value of xstart - as index 1 item, the value xstart+xstep - as index 2 item, the value (xstart+xstep)+xstep, and so on as long as the value does equal or pass the value of xend. However, the function should return an empty string if for positive xstep, xstart>xend or if for negative xstep, xstart < xend. Here are three...

Assume that struct Node{ int item; Node* link; }; Write function void list_remove(NodePtr& prev_ptr);...

Assume that struct Node{ int item; Node* link; }; Write function void list_remove(NodePtr& prev_ptr); The function will remove the node after the node pointed by prev_ptr. c++

Write a Java method that returns the index of the largest element in an array of...

Write a Java method that returns the index of the largest element in an array of integers. If the number of such elements is greater than 1, return the smallest index. Use the following header:   public static int indexOfLargestElement(double[] array)  Write a test program that prompts the user to enter ten numbers, invokes this method to return the index of the largest element, and displays the index.

Using Java Write a method that returns the index of the smallest element in an array...

Using Java Write a method that returns the index of the smallest element in an array of integers. If the number of such elements is greater than 1, return the smallest index. Use the following header: public static int indexOfSmallestElement (double[] array)

Write a method in JAVA, called binarySearch, that returns the index of the key element if...

Write a method in JAVA, called binarySearch, that returns the index of the key element if found in the array, otherwise it will return the value of minus(insertion point +1). In main, use an initializer list create an array of ints called nums holding the following values: 1, 4, 13, 43, -25, 17, 22, -37, 29. Test your binarySearch method on nums with a key value number in it (e.g. 4) and one that is not (e.g. 100). Ex. Given...

Subjects