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
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 heapsort
0
votes
0
answers
1
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
(
41k
points)

4
views
cormen
algorithms
heap
heapsort
descriptive
difficult
0
votes
0
answers
2
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
(
41k
points)

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

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

1
view
cormen
algorithms
heap
heapsort
descriptive
0
votes
0
answers
5
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
(
41k
points)

4
views
cormen
algorithms
heap
heapsort
descriptive
+1
vote
0
answers
6
Ace Test Series: Algorithm  Heap Sort
Q : What is the running time of heap sort for presorted input of size n? O(n) B) O(n^2) C) O(nlogn) D) O(logn) In the question they didn't mention if its a max or min heap and also they didn't mention if the presorted ... the time complexity would be O(n) and for decresing order it would be O(nlogn). Is the question incomplete or am i missing some concepts?
asked
Dec 24, 2018
in
Algorithms
by
OneZero
Active
(
2.1k
points)

58
views
acetestseries
heapsort
algorithms
0
votes
1
answer
7
# Heap sort
Sort The Following Sequence of input using Heap sort. { 10 , 2 , 1 , 5, 3 ,8 ,11,24 ,7 } Please show the output at every pass because i am getting confused.
asked
Sep 9, 2018
in
Algorithms
by
LavTheRawkstar
Active
(
3.7k
points)

100
views
algorithms
heap
heapsort
sorting
0
votes
1
answer
8
Sorting:
You have to sort 1 GB of data with only 100 MB of available main memory. Which sorting technique will be most appropriate? 1)QuickSort 2)MergeSort 3)HeapSort 4)Selection Sort Explain? How
asked
Jul 8, 2018
in
Algorithms
by
pradeepchaudhary
Active
(
1.2k
points)

141
views
sorting
algorithms
timecomplexity
heapsort
0
votes
1
answer
9
Heap Sort
Would it be possible to implement a variant of heapsort based on a perfectly balanced ternary structure in which the children of node $i$ are at positions $3i  1, 3i$, and $3i + 1$, and if so what would be the advantages and disadvantages of the new method?
asked
Jun 18, 2018
in
Algorithms
by
Balaji Jegan
Active
(
4.8k
points)

61
views
algorithms
datastructure
heapsort
0
votes
2
answers
10
Heapsort Comparisons
How many element comparisons would heap sort use to sort the integers $1$ to $8$ if they were initially in sorted order, initially in reverse sorted order?
asked
Jun 17, 2018
in
DS
by
Balaji Jegan
Active
(
4.8k
points)

243
views
datastructure
heapsort
0
votes
0
answers
11
Sorting
You are asked to sort 15 randomly generated numbers. One should prefer  1. Bubble Sort 2. Quick Sort 3. Merge Sort 4. Heap Sort Please explain why others 3 sorting algorithms except the answer can't be used ?
asked
Jun 15, 2018
in
Algorithms
by
Rahul Ranjan 1
(
129
points)

128
views
sorting
algorithms
timecomplexity
heapsort
mergesort
0
votes
1
answer
12
Space Complexity of Build Max Heap
Since Heapify is a recursive function, its space complexity is $O(logn)$ because of the stack space required for recursion. I also read that space complexity of heapsort is $O(1)$ beause of the explanation here  https://gateoverflow.in/79909/ ... complexity of build heap is $O(logn)$ then heapsorts complexity should also be the same . What am I missing here ?
asked
Jun 14, 2018
in
Algorithms
by
Hardik Maheshwari
(
81
points)

302
views
spacecomplexity
algorithms
heap
heapsort
0
votes
0
answers
13
Cormen 3rd edition Q.6.59
Give an O(n lgk)time algorithm to merge k sorted lists into one sorted list, where n is the total number of elements in the input lists. Use a min heap for kway merging.
asked
Jun 14, 2018
in
Algorithms
by
Aarvi Chawla
(
365
points)

71
views
heapsort
+1
vote
1
answer
14
Sorting
asked
Mar 19, 2018
in
Algorithms
by
pankaj_vir
Boss
(
10.4k
points)

153
views
testseries
sorting
algorithms
heapsort
radixsort
0
votes
0
answers
15
I know heapsort but have doubt on finding the comparisons , need help.
asked
Nov 26, 2017
in
Algorithms
by
hem chandra joshi
Active
(
4k
points)

78
views
heapsort
0
votes
2
answers
16
Self doubt
You are asked to sort 15 randomly generated numbers. One should prefer— (a) Bubble sort (b) Quick sort (c) Merge sort (d) Heap sort I think the answer should be c or d crct me???
asked
Jun 6, 2017
in
Algorithms
by
Shubhanshu
Boss
(
17.9k
points)

393
views
algorithms
sorting
mergesort
heapsort
+1
vote
1
answer
17
proof
1) Show that when all elements are distinct, the best case running time of HEAPSORT is Ω(n log n). 2) Show that the worst case running time of HEAPSORT is Ω(n log n).
asked
Apr 13, 2017
in
Algorithms
by
firki lama
Junior
(
645
points)

391
views
heapsort
+1
vote
1
answer
18
#HeapSort
What is the worst case time complexity of finding a element in max heap tree ? Explain.
asked
Apr 1, 2017
in
Algorithms
by
S Harika
(
49
points)

149
views
heapsort
0
votes
0
answers
19
Heapsort #Virtualgate
Need approach to solve this ?
asked
Dec 20, 2016
in
Algorithms
by
Prajwal Bhat
Boss
(
11.1k
points)

227
views
heapsort
algorithms
0
votes
1
answer
20
general doubt
Why is space complexity of heap sort is O(1)? Everytime it calls Heapify() function at the root node of the heap and heapify in the worst case takes O(log n) space. Then why everywhere its written that heapsort is inplace sorting algorithm?? Another doubt is ... space or the total space which include the input size as well?? plzzzz some one clear this doubt of mine. please clarify???
asked
Dec 5, 2016
in
Algorithms
by
sushmita
Boss
(
16.4k
points)

109
views
heapsort
+4
votes
1
answer
21
Heapsort
Suppose we are sorting an array of eight integers using heapsort, and we have just finished some heapify (either maxheapify or minheapify) operations. The array now looks like this: 16 14 15 10 12 27 28 How many heapify operations have been performed on root of heap?
asked
Nov 23, 2016
in
DS
by
thor
Loyal
(
6.7k
points)

810
views
heapsort
+1
vote
1
answer
22
HeapSort
There are 3 D&C basis sorting Algos Quick sort : T(k)+T(nk)+ Cn Merge sort : 2T(n/2) +Cn Heap sort : ___________ I know how the complexity of heap sort is O(nlogn) but I don't know recurrence relation of Heap sort .
asked
Nov 21, 2016
in
Algorithms
by
Rajesh Pradhan
Boss
(
23.4k
points)

326
views
heapsort
+1
vote
1
answer
23
heap sort
The number of elements that can be sorted in time using heap sort ?
asked
Jul 30, 2016
in
Algorithms
by
reena_kandari
Loyal
(
7.6k
points)

410
views
algorithms
timecomplexity
sorting
heapsort
heap
+1
vote
1
answer
24
UGCNETJune2013II28
The time complexity to build a heap with a list of n numbers is O(log n) O(n) O(n logn) O(n$^2$)
asked
Jun 15, 2016
in
DS
by
shivani2010
Junior
(
539
points)

774
views
heapsort
ugcnetjune2013ii
0
votes
3
answers
25
The recurrence relation for MAXHEAPIFY function of heapsort algorithm is T(n) <= T(2n/3) + O(1). How is it 2n/3 ?
asked
Apr 20, 2016
in
Algorithms
by
Vivek Jain
Junior
(
771
points)

1.9k
views
algorithms
timecomplexity
recurrence
heapsort
heap
+1
vote
1
answer
26
K sorted list,n/k elements what is time complexity?please specifiy ur ans in detail
asked
Apr 15, 2016
in
Algorithms
by
Singhravin11
(
13
points)

258
views
heapsort
0
votes
1
answer
27
heap sort
The number of elements that can be sorted in O(logn) time using heap sort is (A) (B) (C) (d) Answer: (C) please explain why??
asked
Feb 24, 2016
in
Programming
by
indrajeet
Active
(
1.6k
points)

391
views
heapsort
algorithms
sorting
+1
vote
1
answer
28
Heap Sort best case
What is the Best Case run time of Heap Sort ? A. $O(1)$ B. $O(n)$ C. $O(n \log n)$ D. $O(\log n)$
asked
Jan 20, 2016
in
Algorithms
by
Himanshu1
Boss
(
15.4k
points)

428
views
algorithms
sorting
heap
heapsort
To see more, click for the
full list of questions
or
popular tags
.
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
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!!
My journey from Wipro to an IISc student  GATE 2019
Follow @csegate
Recent questions tagged heapsort
Recent Blog Comments
Can you check your Spam too? Address confirmation...
yeah me too. I did not get the address...
Please explain about the 80 20 rule in detail
@arjun sir is it possible to reconfirm address...
49,814
questions
54,518
answers
188,351
comments
75,297
users