To find the kth largest element from the heap of n elements, an additional heap data structure will be required.
Algorithm:
Step 1: Using the first k elements of the given heap, build a min-heap M. The time complexity of this step is O(k).
Step 2: After the above step, each of the next elements of the given heap is compared with the root of the min-heap M. If the element is greater than the root of the min-heap M, then make it root and call min-heapify function for M. Otherwise (if element is less than root of M), just ignore it. The time complexity of this step is O((n-k)*logk)
Step 3: After performing all the above steps, the root of the min-heap M is the kth largest element.
Time Complexity: O((n-k)*logk) = O(klogk)
For the given example:
1. The heap from the first seven elements is:
2. Min-heapify this heap.
3. Compare the root of this heap with remaining elements. 20, 40, 10 and 30 are smaller than the root 40, so nothing is done. But 45 is greater than 40, so 40 is replaced with 45. Thus, the 7th largest element is 45.
CODE:
The language used is C++.
In the code given below, an array data structure is given to represent the given heap. If the given heap is in tree form, store it into array using level order traversal and use the same code given below to find kth largest element. Note that level order traversal of a tree can be done using queue data structure.
In this code, priority_queue of Standard Template Library is used to represent min heap.
#include<bits/stdc++.h>
using namespace std;
int kthLargest(int arr[], int n, int k)
{
//Min heap
priority_queue<int, vector<int>, greater<int> >
Q;
//Push first k elements into the priority_queue.
//The top or root of the priority_queue is the minimum
element.
for(int i=0;i<k;i++)
Q.push(arr[i]);
//Compare remaining elements with top or root of the
priority_queue.
//Top of the priority_queue Q can be obtained by Q.top().
for(int i=k;i<n;i++){
if(arr[i] > Q.top()){
Q.pop(); //Used to remove top of the priority_queue.
Q.push(arr[i]);
//When arr[i] is pushed, Q is automatically arranged so that
minimum is at the root or top.
}
}
//Return root or top of the priority_queue.
return Q.top();
}
int main()
{
int arr[] = {100, 80, 70, 40, 50, 65, 60, 20, 40, 10, 30,
45};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<kthLargest(arr, n, 7);
}
Code Snippets:
Sample Output:
Provide an O(k log k) algorithm that uses a heap data structure to find the kth...
please justify. A Fibonacci heap is a fancy priority queue data structure. For a heap of size n, it takes O(log n) time to do an extractMin() operation but only O(1) time to do an insert or decrease operation. Suppose we replace the binary heap used in Dijkstra's algorithm by a Fibonacci heap. 6. If the graph is dense, what is the asymptotic complexity of Dijkstra's algorithm using a Fibonacci heap, in terms of V|? 7. If the graph is...
Discrete Mathematics Time Complexity Analysis Due: May 9th, 2019 Math 4 6026 Heap Sort Another algorithm for sorting uses a specialized tree structure called a "heap." Specifically, we will use a binary heap, which is like a binary tree with hierarchy. Here is an example of a binary heap structure 1. 2. There is a top vertex, called the parent vertex (aka node). The top parent vertex connects to two vertices a level below. These vertices are the "left child"...
8. Provide an O(n log n) time divide-and-conquer algorithm to find the area of the largest area rectangular region that lies entirely within a given histogram. The histogram consists of bars of width one that extend upwards from the x-axis. Bar i extends upward from the line y 0 to the line y topi) For example in the following histogram with 8 bars, the area of the largest rect- angular region that lies entirely within the histogram with tops (8,5,6,9,2,5,4,5)...
Write a program in Java to implement the max-priority queue using max-heap data structure. Implement the max-heap data structure using an integer array of 10 cells. (Do not use Java in-built PriorityQueue class.) [In a max-heap, the root node and the intermediate node vales are always greater than their children.] First, take 10 integer values from the user and insert them in the max-priority queue. Then print the elements of the queue. After that, delete two elements from the queue...
need solution plz Question 1 (CLO-4, PLo-3) Figure 1 show an input tree T. 1. Analyze the tree and mention weather the tree is a heap or not by checking heap's property. If yes, justify your answer. If no, make it a heap by adjusting the node's location 2. Alter the value of T[l1] to 100 using alter-heap algorithm. Analyze the tree again and state whether i. The tree is still a heap or not? ii. If not, which one...
need full solution of this question plz help me Question 1 (CLO-4, PLo-3) Figure 1 show an input tree T. 1. Analyze the tree and mention weather the tree is a heap or not by checking heap's property. If yes, justify your answer. If no, make it a heap by adjusting the node's location 2. Alter the value of T[l1] to 100 using alter-heap algorithm. Analyze the tree again and state whether i. The tree is still a heap or...
Data Structures using C BuildHeap and Heap Sort In preparation: If you have not done so already, you should complete Worksheet 33 to leam more about the heap data structure. In some applications it is useful to void buildHeap (struct dyArray heap) { initialize a Heap with an existing vector int max = dy Array Size(heap); int i; of values. The values are not assumed for (i = max/2-1; i >= 0; i--) to be organized into a heap, and...
problem 2 can use Det-Selection(A, p, q, r) as a sub-routine (i.e, you don't need to write its pseudo-code). To sort an array A, you will then call Det-QuickSort(A, 1, n). You also need to provide the worst case time complexity analysis of your algorithm. 2. (20 points) Given a set of n distinct numbers, we wish to find the k largest in sorted order using a comparison-based algorithm. Give an algorithm that implements each of the following methods, and...
program in python Randomness can be used to improve the performance of deterministic algorithms which need to make many choices. Rather than repeatedly making fixed, hard-coded choices, a pseudorandom number generator can be used to make dynamic, unbiased choices. If the benefits of "good" choices outweigh the costs of "bad" choices, a random selection of good and bad choices can improve the performance of an algorithm Let us explore this with the QUICKSELECT algorithm. Discovered by the influential computer science...
4. Ranking/Unranking Subsets. Let A be a set of n elements and set Sk(A) be the collection of all k-element subsets of A. Recall that |Sk(A)I - (a.) (8 points) Describe a ranking algorithm to rank a k-element subset of an n-element set. (b.) (8 points) Describe an unranking algorithm to unrank an integer 0 < s< [into a ithm to unrank an integer 0 S s <C) k-element subset of an n-element set. (c.) (10 points) As examples, let...