Dark Mode

Recent questions tagged heap

0 votes

2 answers

1

made easy test series for gate cse 2023
please help me out in solving this question. the solution provided there is not upto the mark

sachidanand_dwivedi asked in Programming Dec 21, 2022

by sachidanand_dwivedi

457 views

0 votes

1 answer

2

DSA
Given two max heap, one of size n and other m. Calculate the time complexity of merging them to get a max heap.

shub2204 asked in DS Dec 5, 2022

284 views

1 vote

1 answer

3

CS Data structures and algorithm 2022
Design an algorithm to construct one heap that contains all the elements of two given heaps of sizes n and m, respectively. The heaps are given in a linked-list representation ( each node has links to its two children). The running time of the algorithm should be O(log(m + n)) in the worst case

jola asked in Algorithms Dec 5, 2022

by jola

133 views

0 votes

1 answer

4

Random
Consider a 15 element min-heap which follows these conditions. right child of root is7 and one child of node 3 is 9. Calculate how many min heap possible?

shub2204 asked in DS Nov 30, 2022

223 views

0 votes

1 answer

5

Number of max heaps
Someone please explain the login behind the explanation.

Overflow04 asked in DS Jun 30, 2022

667 views

10 votes

4 answers

6

GATE CSE 2021 Set 2 | Question: 2
Let $H$ be a binary min-heap consisting of $n$ elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in $H$? $\Theta (1)$ $\Theta (\log n)$ $\Theta (n)$ $\Theta (n \log n)$

Arjun asked in DS Feb 18, 2021

by Arjun

5.3k views

2 votes

1 answer

7

NIELIT 2016 MAR Scientist C - Section C: 52
Consider the process of inserting an element into a $Max\ Heap$, where the $Max\ Heap$ is represented by an $array$. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of $comparisons$ ... $\Theta(n\log _{2} \log_2 n)$ $\Theta (n)$ $\Theta(n\log _{2}n)$

Lakshman Patel RJIT asked in DS Apr 2, 2020

by Lakshman Patel RJIT

1.4k views

1 vote

2 answers

8

NIELIT 2017 July Scientist B (CS) - Section B: 8
A priority queue is implemented as a Max-Heap. Initially, it has $5$ elements. The level-order traversal of the heap is: $10,8,5,3,2$. Two new elements $1$ and $7$ are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is $10,8,7,3,2,1,5$ $10,8,7,2,3,1,5$ $10,8,7,1,2,3,5$ $10,8,7,5,3,2,1$

Lakshman Patel RJIT asked in DS Mar 30, 2020

by Lakshman Patel RJIT

615 views

1 vote

2 answers

9

NIELIT 2017 DEC Scientist B - Section B: 31
Consider a complete binary tree where the left and the right sub trees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is: $\Omega(\log n)$ $\Omega(n\log n)$ $\Omega(n)$ $\Omega(n^2)$

Lakshman Patel RJIT asked in DS Mar 30, 2020

by Lakshman Patel RJIT

752 views

1 vote

7 answers

10

UGC NET CSE | January 2017 | Part 2 | Question: 23
Which of the following is a valid heap? $a$ $b$ $c$ $d$

go_editor asked in DS Mar 24, 2020

993 views

0 votes

0 answers

11

Cormen Edition 3 Exercise 6.5 Question 9 (Page No. 166)
Give an $O(n\lg\ k)$- time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total number of elements in all the input lists. (Hint: Use a minheap for $k$-way merging.)

akash.dinkar12 asked in Algorithms Jun 27, 2019

by akash.dinkar12

230 views

0 votes

1 answer

12

Cormen Edition 3 Exercise 6.5 Question 8 (Page No. 166)
The operation HEAP-DELETE$(A, i)$ deletes the item in node $i$ from heap $A$. Give an implementation of HEAP-DELETE that runs in $O(lg\ n)$ time for an $n-$element max-heap.

akash.dinkar12 asked in Algorithms Jun 27, 2019

by akash.dinkar12

378 views

0 votes

0 answers

13

Cormen Edition 3 Exercise 6.5 Question 7 (Page No. 166)
Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue.

akash.dinkar12 asked in Algorithms Jun 27, 2019

by akash.dinkar12

215 views

0 votes

0 answers

14

Cormen Edition 3 Exercise 6.5 Question 6 (Page No. 166)
Each exchange operation on line $5$ of HEAP-INCREASE-KEY typically requires three assignments. Show how to use the idea of the inner loop of INSERTION-SORT to reduce the three assignments down to just one assignment.

akash.dinkar12 asked in Algorithms Jun 27, 2019

by akash.dinkar12

185 views

0 votes

0 answers

15

Cormen Edition 3 Exercise 6.5 Question 5 (Page No. 166)
Argue the correctness of HEAP-INCREASE-KEY using the following loop invariant: At the start of each iteration of the while loop of lines $4-6$, the subarray $A[1..A.heapsize]$ satisfies the max-heap property, except that there ... assume that the subarray $A[a..heapsize]$ satisfies the max-heap property at the time HEAP-INCREASE-KEY is called.

akash.dinkar12 asked in Algorithms Jun 27, 2019

by akash.dinkar12

200 views

0 votes

0 answers

16

Cormen Edition 3 Exercise 6.5 Question 4 (Page No. 165)
Why do we bother setting the key of the inserted node to $-\infty$ in line $2$ of MAX-HEAP-INSERT when the next thing we do is increase its key to the desired value?

akash.dinkar12 asked in Algorithms Jun 27, 2019

by akash.dinkar12

219 views

0 votes

0 answers

17

Cormen Edition 3 Exercise 6.5 Question 3 (Page No. 165)
Write pseudo code for the procedures HEAP-MINIMUM, HEAP-EXTRACT-MIN, HEAP-DECREASE-KEY, and MIN-HEAP-INSERT that implement a min-priority queue with a min-heap.

akash.dinkar12 asked in Algorithms Jun 27, 2019

by akash.dinkar12

187 views

0 votes

0 answers

18

Cormen Edition 3 Exercise 6.5 Question 2 (Page No. 165)
HEAP-INCREASE-KEY(A,i,key) 1 if key < A[i] 2 error new key is smaller than current key 3 A[i] = key 4 while i > 1 and A[parent(i)] < A[i] 5 exchange A[i] with A[parent(i)] 6 i=parent(i) MAX-HEAP-INSERT(A,key) 1 A ... ,key) Illustrate the operation of MAX-HEAP-INSERT$(A,10)$ on the heap $A=\langle 15,13,9,5,12,8,7,4,0,6,2,1 \rangle$.

akash.dinkar12 asked in Algorithms Jun 27, 2019

by akash.dinkar12

215 views

Page:

1
2
3
4
5
6
next »

Recent questions tagged heap