The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged heap
0
votes
1
answer
1
IIIT BLR TEST 1 : ALGORITHMS 2
A 3 way (ternary) min heap is a 3 way ( ternary  each node as atmost three children nodes, left, mid, right ) complete tree with min heap property ( value of the parent is less than the value of the children ) satisfied at every node ... c) In Heapsort, binary heap is preferred over ternary heap. State if this statement is true or false, you must justify your answer.
asked
Aug 27
in
Algorithms
by
Shaik Masthan
Veteran
(
64k
points)

89
views
iiit_blr
test_1
algorithms
heap
0
votes
0
answers
2
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.)
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

13
views
cormen
algorithms
heap
descriptive
0
votes
1
answer
3
Cormen Edition 3 Exercise 6.5 Question 8 (Page No. 166)
The operation HEAPDELETE$(A, i)$ deletes the item in node $i$ from heap $A$. Give an implementation of HEAPDELETE that runs in $O(lg\ n)$ time for an $n$element maxheap.
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

19
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
4
Cormen Edition 3 Exercise 6.5 Question 7 (Page No. 166)
Show how to implement a firstin, firstout queue with a priority queue. Show how to implement a stack with a priority queue.
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

13
views
cormen
algorithms
heap
priorityqueue
descriptive
0
votes
0
answers
5
Cormen Edition 3 Exercise 6.5 Question 6 (Page No. 166)
Each exchange operation on line $5$ of HEAPINCREASEKEY typically requires three assignments. Show how to use the idea of the inner loop of INSERTIONSORT to reduce the three assignments down to just one assignment.
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

6
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
6
Cormen Edition 3 Exercise 6.5 Question 5 (Page No. 166)
Argue the correctness of HEAPINCREASEKEY using the following loop invariant: At the start of each iteration of the while loop of lines $46$, the subarray $A[1..A.heapsize]$ satisfies the maxheap property, except that there ... assume that the subarray $A[a..heapsize]$ satisfies the maxheap property at the time HEAPINCREASEKEY is called.
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

4
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
7
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 MAXHEAPINSERT when the next thing we do is increase its key to the desired value?
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

3
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
8
Cormen Edition 3 Exercise 6.5 Question 3 (Page No. 165)
Write pseudo code for the procedures HEAPMINIMUM, HEAPEXTRACTMIN, HEAPDECREASEKEY, and MINHEAPINSERT that implement a minpriority queue with a minheap.
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

4
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
9
Cormen Edition 3 Exercise 6.5 Question 2 (Page No. 165)
HEAPINCREASEKEY(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) MAXHEAPINSERT(A,key) 1 A ... ,key) Illustrate the operation of MAXHEAPINSERT$(A,10)$ on the heap $A=\langle 15,13,9,5,12,8,7,4,0,6,2,1 \rangle$.
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

10
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
10
Cormen Edition 3 Exercise 6.5 Question 1 (Page No. 164)
HEAPEXTRACTMAX(A) 1 if A.heapsize < 1 2 error “heap underflow” 3 max=A[1] 4 A[1]=A[A.heapsize] 5 A.heapsize=A.heapsize1 6 MAXHEAPIFY(A,1) 7 return max Illustrate the operation of HEAPEXTRACTMAX on the heap $A=\langle 15,13,9,5,12,8,7,4,0,6,2,1 \rangle$.
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

4
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
11
Cormen Edition 3 Exercise 6.4 Question 5 (Page No. 161)
Show that when all elements are distinct, the bestcase running time of HEAPSORT is $\Omega(n\lg\ n)$.
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

7
views
cormen
algorithms
heap
heapsort
descriptive
difficult
0
votes
0
answers
12
Cormen Edition 3 Exercise 6.4 Question 4 (Page No. 160)
Show that the worstcase running time of HEAPSORT is $\Omega(n\lg\ n)$.
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

12
views
cormen
algorithms
heap
heapsort
descriptive
0
votes
0
answers
13
Cormen Edition 3 Exercise 6.4 Question 3 (Page No. 160)
What is the running time of HEAPSORT on an array $A$ of length $n$ that is already sorted in increasing order? What about decreasing order?
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

5
views
cormen
algorithms
heap
heapsort
descriptive
0
votes
0
answers
14
Cormen Edition 3 Exercise 6.4 Question 2 (Page No. 160)
Argue the correctness of HEAPSORT using the following loop invariant: At the start of each iteration of the for loop of lines $2–5$,the subarray $A[1..i]$ is a maxheap containing the $i$ smallest elements of $A[1..n] $, and the subarray $A[i+1..n]$ contains the $n i$ largest elements of $A[1..n]$, sorted.
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

4
views
cormen
algorithms
heap
heapsort
descriptive
0
votes
0
answers
15
Cormen Edition 3 Exercise 6.4 Question 1 (Page No. 160)
HEAPSORT(A) 1 BUILDMAXHEAP(A) 2 for i = A.length down to 2 3 exchange A[1] with A[i] 4 A.heapsize=A.heapsize – 1 5 MAXHEAPIFY(A,1) illustrate the operation of HEAPSORT on the array $A=\langle 5,13,2,25,7,17,20,8,4 \rangle$
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

7
views
cormen
algorithms
heap
heapsort
descriptive
0
votes
0
answers
16
Cormen Edition 3 Exercise 6.3 Question 3 (Page No. 159)
Show that there are at most $\lceil n/2^{h+1}\rceil$ nodes of height $h$ in any $n$element heap.
asked
Jun 26
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

13
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
17
Cormen Edition 3 Exercise 6.3 Question 2 (Page No. 159)
Why do we want the loop index $i$ in line $2$ of BUILDMAXHEAP to decrease from $\lfloor A.length/2 \rfloor$ to 1 rather than increase from 1 to $\lfloor A.length/2 \rfloor$?
asked
Jun 26
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

7
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
18
Cormen Edition 3 Exercise 6.3 Question 1 (Page No. 159)
BUILDMAXHEAP(A) 1 A.heapsize=A.length 2 for i=A.length/2 downto 1 3 MAXHEAPIFY(A,i) Using Figure $6.3$ as a model, illustrate the operation of BUILDMAXHEAP on the array $A=\langle 5,3,17,10,84,19,6,22,9 \rangle $
asked
Jun 26
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

9
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
19
Cormen Edition 3 Exercise 6.2 Question 6 (Page No. 156)
Show that the worstcase running time of MAXHEAPIFY on a heap of size $n$ is $\Omega(lg\ n)$.(Hint: For a heap with $n$ nodes, give node values that cause MAXHEAPIFY to be called recursively at every node on a simple path from the root down to a leaf).
asked
Jun 26
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

5
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
20
Cormen Edition 3 Exercise 6.2 Question 5 (Page No. 156)
The code for MAXHEAPIFY is quite efficient in terms of constant factors, except possibly for the recursive call in line 10, which might cause some compilers to produce inefficient code. Write an efficient MAXHEAPIFY that uses an iterative control construct (a loop) instead of recursion.
asked
Jun 26
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

7
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
21
Cormen Edition 3 Exercise 6.2 Question 4 (Page No. 156)
What is the effect of calling MAXHEAPIFY$(A,i)$ for $i > A.heapsize/2$.
asked
Jun 26
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

4
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
22
Cormen Edition 3 Exercise 6.2 Question 3 (Page No. 156)
What is the effect of calling MAXHEAPIFY$(A, i)$ when the element $A[i]$ is larger than its children?
asked
Jun 26
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

6
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
23
Cormen Edition 3 Exercise 6.2 Question 2 (Page No. 156)
Starting with the procedure MAXHEAPIFY, write pseudocode for the procedure MINHEAPIFY$(A, i )$, which performs the corresponding manipulation on a minheap. How does the running time of MINHEAPIFY compare to that of MAXHEAPIFY?
asked
Jun 26
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

3
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
24
Cormen Edition 3 Exercise 6.2 Question 1 (Page No. 156)
MAXHEAPIFY(A,i) 1 l=Left(i) 2 r=Right(i) 3 if l <= A.heapsize and A[l] > A[i] 4 largest=l 5 else largest = i 6 if r <= A.heapsize and A[r] > A[largest] 7 largest=r 8 if largest!=i 9 exchange A[i] with A[ ... model, illustrate the operation of MAXHEAPIFY(A,3) on the array $A=\langle 27,17,3,16,13,10, 1,5,7,12,4,8,9,0 \rangle$
asked
Jun 26
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

9
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
25
ISI2018PCBCS5
Consider a maxheap of $n$ distinct integers, $n ≥ 4$, stored in an array $\mathcal{A}[1 . . . n]$. The second minimum of $\mathcal{A}$ is the integer that is less than all integers in $\mathcal{A}$ except the minimum of $\mathcal{A}$. Find all possible array indices of $\mathcal{A}$ in which the second minimum can occur. Justify your answer.
asked
May 12
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

32
views
isi2018pcbcs
algorithms
algorithmdesign
heap
descriptive
0
votes
1
answer
26
ISI 2018 PCB C5
Consider a maxheap of n distinct integers, n ≥ 4, stored in an array A[1 . . . n]. The second minimum of A is the integer that is less than all integers in A except the minimum of A. Find all possible array indices of A in which the second minimum can occur. Justify your answer.
asked
May 2
in
Algorithms
by
N
(
417
points)

54
views
userisi2018
usermod
algorithms
heap
binaryheap
+1
vote
0
answers
27
Cormen Edition 3 Exercise 6.1 Question 7 (Page No. 154)
Show that, with the array representation for storing an $n$element heap, the leaves are the nodes indexed by $\lfloor n/2\rfloor +1$,$\lfloor n/2\rfloor +2,…,n$
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

27
views
cormen
algorithms
heap
descriptive
0
votes
1
answer
28
Cormen Edition 3 Exercise 6.1 Question 6 (Page No. 154)
Is the array with values $23,17,14; 6,13,10,1,5,7,12$ a maxheap ?
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

32
views
cormen
algorithms
heap
descriptive
0
votes
1
answer
29
Cormen Edition 3 Exercise 6.1 Question 5 (Page No. 154)
Is an array that is in sorted order a minheap ?
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

32
views
cormen
algorithms
heap
0
votes
1
answer
30
Cormen Edition 3 Exercise 6.1 Question 4 (Page No. 154)
Where in a maxheap might the smallest element reside, assuming that all elements are distinct ?
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

68
views
cormen
algorithms
sorting
heap
descriptive
Page:
1
2
3
4
5
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Minimal Deterministic Finite Automata
To be aware of fake GATE test series
Standard Book Exercise Questions for Computer Science
Follow @csegate
Recent questions tagged heap
Recent Blog Comments
Favorite is not working for blogs.. In favorites...
Favourite option does work. But list options...
Blog favorite button doesnt work?
@Arjun Sir can we have an option to save such...
Thanks Sir
50,666
questions
56,163
answers
193,778
comments
93,862
users