A company constantly receives (integer) price quotes for its product over the in

Question

A company constantly receives (integer) price quotes for its product over the internet, and at any point, we are asked to store the k smallest price quotes, where k is fixed by the manager in advance. We consider three possible data structures for the task of maintaining the k smallest quotes so far. 1. A min heap data structure with k elements in it. 2. A balanced binary search tree data structure. 3. A sorted array of k elements. For each of the structures, write down how you would update the data structure when a new quote comes in and the worst case running time.

Explanation / Answer

1. Heap data structure has two ordering properties.they are:MIN heap and MAX heap.

In min-heap the value of each node is greater than or equal to the value of its parent, with the minimum-value element at the root.In max-heap property the value of each node is less than or equal to the value of its parent, with the maximum-value element at the root.In worst of the both properties it will running time O(k logk) where k is number of elements

2.Balanced binary search tree The worst case running time to search for an element in a balanced in a binary search tree with k^2K elements is O(k) where k is number of elements.

3.Diff running time of sorted array

->bubble sort-O(k2)

->selection sort-O(k2)

->Insertion Sort-O(nk)

->quickSort-O(nlogn)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.