Knowee
Questions
Features
Study Tools

Problem StatementDavid is designing a navigation system for a delivery drone. He wants to implement a function that allows him to insert new delivery locations into a min heap based on their distances from the current location.Write a code to help him insert new delivery locations into a min heap.Input format :The input consists of a sequence of space-separated integers representing the distances of delivery locations from the current location.Output format :The output consists of the distances of delivery locations stored in the min heap. Each distance is separated by a space.Code constraints :The maximum number of delivery locations is 100 (specified by the size of the min heap array).Sample test cases :Input 1 :5 3 8 2 9 1 7 6 4Output 1 :1 3 2 4 9 8 7 6 5 Input 2 :10 20 30 40 50Output 2 :10 20 30 40 50 Note :The program will be evaluated only after the “Submit Code” is clicked.Extra spaces and new line characters in the program output will result in the failure of the test case.

Question

Problem StatementDavid is designing a navigation system for a delivery drone. He wants to implement a function that allows him to insert new delivery locations into a min heap based on their distances from the current location.Write a code to help him insert new delivery locations into a min heap.Input format :The input consists of a sequence of space-separated integers representing the distances of delivery locations from the current location.Output format :The output consists of the distances of delivery locations stored in the min heap. Each distance is separated by a space.Code constraints :The maximum number of delivery locations is 100 (specified by the size of the min heap array).Sample test cases :Input 1 :5 3 8 2 9 1 7 6 4Output 1 :1 3 2 4 9 8 7 6 5 Input 2 :10 20 30 40 50Output 2 :10 20 30 40 50 Note :The program will be evaluated only after the “Submit Code” is clicked.Extra spaces and new line characters in the program output will result in the failure of the test case.

...expand
🧐 Not the exact question you are looking for?Go ask a question

Solution 1

The problem statement is asking to implement a min heap data structure. A min heap is a complete binary tree where the parent node is less than or equal to its child node. We always insert a new node at the end of the tree and then we adjust the heap to satisfy the heap property.

Here is a Python solution:

class MinHeap:
    def __init__(self, maxsize):
        self.maxsize = maxsize
        self.size = 0
        self.Heap = [0]*(self.maxsize + 1)
        self.Heap[0] = -1 * float('inf')
        self.FRONT = 1

    def parent(self, pos):
        return pos//2

    def leftChild(self, pos):
        return 2 * pos

    def rightChild(self, pos):
        return (2 * pos) + 1

    def isLeaf(self, pos):
        if pos >= (self.size//2) and pos <= self.size:
            return True
        return False

    def swap(self, fpos, spos):
        self.Heap[fpos], self.Heap[spos] = self.Heap[spos], self.Heap[fpos]

    def minHeapify(self, pos):
        if not self.isLeaf(pos):
            if (self.Heap[pos] > self.Heap[self.leftChild(pos)] or
               self.Heap[pos] > self.Heap[self.rightChild(pos)]):

                if self.Heap[self.leftChild(pos)] < self.Heap[self.rightChild(pos)]:
                    self.swap(pos, self.leftChild(pos))
                    self.minHeapify(self.leftChild(pos))

                else:
                    self.swap(pos, self.rightChild(pos))
                    self.minHeapify(self.rightChild(pos))

    def insert(self, element):
        if self.size >= self.maxsize :
            return
        self.size+= 1
        self.Heap[self.size] = element

        current = self.size

        while self.Heap[current] < self.Heap[self.parent(current)]:
            self.swap(current, self.parent(current))
            current = self.parent(current)

    def Print(self):
        for i in range(1, (self.size//2)+1):
            print(" PARENT : "+ str(self.Heap[i])+" LEFT CHILD : "+
                                str(self.Heap[2 * i])+" RIGHT CHILD : "+
                                str(self.Heap[2 * i + 1]))

    def minHeap(self):
        for pos in range(self.size//2, 0, -1):
            self.minHeapify(pos)

minHeap = MinHeap(100)
distances = list(map(int, input().split()))
for distance in distances:
    minHeap.insert(distance)
minHeap.minHeap()
minHeap.Print()

This Python code creates a MinHeap class with methods to insert elements, swap elements, and maintain the min heap property. The distances are read from the input, inserted into the min heap, and then the min heap is printed.

This problem has been solved

Solution 2

The problem statement is asking to implement a min heap data structure. A min heap is a complete binary tree where the parent node is less than or equal to its child node. We always insert a new node at the end of the tree and if the parent node is greater than the child node, we swap them. We repeat this process until the heap property is satisfied.

Here is a Python solution for the problem:

def heapify(arr, n, i):
    smallest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[i] > arr[left]:
        smallest = left

    if right < n and arr[smallest] > arr[right]:
        smallest = right

    if smallest != i:
        arr[i], arr[smallest] = arr[smallest], arr[i]
        heapify(arr, n, smallest)

def insert(array, newNum):
    size = len(array)
    if size == 0:
        array.append(newNum)
    else:
        array.append(newNum);
        for i in range((size//2)-1, -1, -1):
            heapify(array, size, i)

def printArray(array, size):
    for i in range(size):
        print(array[i], end = " ")

This problem has been solved

Similar Questions

Perform Insert, delMin and getMin operations on a Min Heap. Implement Min Heaps and avoid using inbuilt library.Input FormatFirst line of input contains T - number of operations. Its followed by T lines, each line contains either "insert x" or "delMin" or "getMin".Constraints1 <= T <= 106-109 <= x <= 109Output FormatFor each "getMin" operation, print the minimum element, separated by newline. If the heap is empty, print "Empty".Sample Input 010insert 5getMindelMingetMininsert -15insert 10insert -30getMindelMingetMinSample Output 05Empty-30-15Explanation 0Self Explanatory

Problem StatementJacob was tasked with writing a program to find the smallest number among three numbers, but he was instructed to write the program using the extern storage class. Assist him in accomplishing his task.Input format :The input consists of three space-separated integers: num1, num2, and num3.Output format :The output displays "Smallest number is " followed by the smallest of three numbers.Refer to the sample output for the formatting specifications.Code constraints :In the given scenario, the test cases will fall under the following constraints:1 ≤ num1, num2 and num3 ≤ 105Sample test cases :Input 1 :2 7 8Output 1 :Smallest number is 2Input 2 :5678 4589 4532Output 2 :Smallest number is 4532Input 3 :1075 6785 1563Output 3 :Smallest number is 1075

Single File Programming QuestionProblem StatementJenifer is developing a program for a warehouse management system that needs to analyze inventory data. The program receives an array representing the quantities of different products in the warehouse. The task is to count the number of items falling within a specified range of quantities. Help Jenifer to accomplish her task using pointers.Input format :The first line of input consists of an integer N, representing the number of products in the warehouse.The second line consists of N space-separated integers, representing the quantity of products.The third line consists of two space-separated integers, representing the lower limit and upper limit (range).Output format :The output prints the number of products falling within the specified range (both inclusive) of quantities.Refer to the sample output for formatting specifications.Code constraints :In this scenario, the test cases fall under the following constraints:1 ≤ N ≤ 251 ≤ quantity ≤ 100Sample test cases :Input 1 :1015 25 35 45 55 65 75 85 95 10045 85Output 1 :5Input 2 :523 29 34 48 5935 60Output 2 :2

Problem StatementMugil has been assigned a task to develop a versatile distance converter for navigation systems. The program is designed to enable users to input distances in kilometers and convert them into miles with two decimal places.Note: 1 km = 0.621371 milesInput format :The input consists of a integer value n, representing the distance in kilometers.Output format :The output prints the distance in miles as a double value with two decimal places.Refer to the sample output for formatting specifications.Code constraints :In this scenario, the given test cases fall under the following constraints:1 ≤ n ≤ 100Sample test cases :Input 1 :1Output 1 :0.62Input 2 :100Output 2 :62.14Input 3 :52Output 3 :32.31

Problem StatementImagine you are building a threaded binary search tree to store data from a sensor network. Each sensor node produces data points, and you want to organize this data efficiently for quick retrieval. For this task create a program to insert 'n' data points into the threaded binary tree. Input format :The first line of input is n, which is a non-negative integer.The second line of input is a series of non-negative integers (separated by spaces), up to n. The data points represent the elements to be inserted into the threaded binary search tree.Output format :The output should display the data points in the inserted order, separated by space

1/1

Upgrade your grade with Knowee

Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.