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
All Activity
Questions
Unanswered
Tags
Categories
Users
Ask a Question
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged heap
0
votes
0
answers
1
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.3k
points)

7
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
2
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.3k
points)

6
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
3
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.3k
points)

5
views
cormen
algorithms
heap
priorityqueue
descriptive
0
votes
0
answers
4
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.3k
points)

3
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
5
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.3k
points)

2
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
6
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.3k
points)

2
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
7
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.3k
points)

2
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
8
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.3k
points)

3
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
9
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.3k
points)

3
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
10
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.3k
points)

5
views
cormen
algorithms
heap
heapsort
descriptive
difficult
0
votes
0
answers
11
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.3k
points)

5
views
cormen
algorithms
heap
heapsort
descriptive
0
votes
0
answers
12
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.3k
points)

3
views
cormen
algorithms
heap
heapsort
descriptive
0
votes
0
answers
13
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.3k
points)

1
view
cormen
algorithms
heap
heapsort
descriptive
0
votes
0
answers
14
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.3k
points)

4
views
cormen
algorithms
heap
heapsort
descriptive
0
votes
0
answers
15
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.3k
points)

10
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
16
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.3k
points)

5
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
17
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.3k
points)

6
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
18
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.3k
points)

3
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
19
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.3k
points)

4
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
20
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.3k
points)

1
view
cormen
algorithms
heap
descriptive
0
votes
0
answers
21
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.3k
points)

2
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
22
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.3k
points)

2
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
23
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.3k
points)

4
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
24
ISI2018PCBB5
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.3k
points)

23
views
isi2018pcbb
algorithms
algorithmdesign
heap
descriptive
0
votes
1
answer
25
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
(
377
points)

49
views
userisi2018
usermod
algorithms
heap
binaryheap
+1
vote
0
answers
26
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.3k
points)

23
views
cormen
algorithms
heap
descriptive
0
votes
1
answer
27
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.3k
points)

29
views
cormen
algorithms
heap
descriptive
0
votes
1
answer
28
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.3k
points)

28
views
cormen
algorithms
heap
0
votes
1
answer
29
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.3k
points)

61
views
cormen
algorithms
sorting
heap
descriptive
0
votes
0
answers
30
Cormen Edition 3 Exercise 6.1 Question 3 (Page No. 153)
Show that in any subtree of a maxheap, the root of the subtree contains the largest value occurring anywhere in that subtree.
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

18
views
cormen
algorithms
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
ISI MTECH CS 2019 INTERVIEW EXPERIENCE
IIT HYDERABAD MTECH TA INTERVIEW EXPERIENCE
How to prepare for GATE with a fulltime job??
Interview Experience at IISc
All subject Gate notes from Standard Books!!
Follow @csegate
Recent questions tagged heap
Recent Blog Comments
Refund time depends on the payment mode ...
@Arjun Sir , when can i expect my refund in the...
This book is returned you can enable a pay now...
@Pranavcool The book stocks are over and no one...
@Lokesh Thats unfortunate. I have refunded you....
49,830
questions
54,802
answers
189,511
comments
80,750
users