Dark Mode

Recent questions tagged heap-sort

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

1 vote

2 answers

2

Gate Applied Practice Test
Question--> The time required to find the 99th smallest element from a min heap of n elements is (given that we have access to the array elements)

lalitver10 asked in Programming Jan 13, 2022

637 views

0 votes

0 answers

3

Cormen Edition 3 Exercise 6.4 Question 5 (Page No. 161)
Show that when all elements are distinct, the best-case running time of HEAPSORT is $\Omega(n\lg\ n)$.

akash.dinkar12 asked in Algorithms Jun 27, 2019

by akash.dinkar12

213 views

0 votes

0 answers

4

Cormen Edition 3 Exercise 6.4 Question 4 (Page No. 160)
Show that the worst-case running time of HEAPSORT is $\Omega(n\lg\ n)$.

akash.dinkar12 asked in Algorithms Jun 27, 2019

by akash.dinkar12

238 views

0 votes

0 answers

5

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?

akash.dinkar12 asked in Algorithms Jun 27, 2019

by akash.dinkar12

186 views

0 votes

0 answers

6

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 max-heap 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.

akash.dinkar12 asked in Algorithms Jun 27, 2019

by akash.dinkar12

227 views

0 votes

0 answers

7

Cormen Edition 3 Exercise 6.4 Question 1 (Page No. 160)
HEAPSORT(A) 1 BUILD-MAX-HEAP(A) 2 for i = A.length down to 2 3 exchange A[1] with A[i] 4 A.heapsize=A.heapsize – 1 5 MAX-HEAPIFY(A,1) illustrate the operation of HEAPSORT on the array $A=\langle 5,13,2,25,7,17,20,8,4 \rangle$

akash.dinkar12 asked in Algorithms Jun 27, 2019

by akash.dinkar12

253 views

1 vote

0 answers

8

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?

OneZero asked in Algorithms Dec 24, 2018

769 views

1 vote

1 answer

9

# 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.

LavTheRawkstar asked in Algorithms Sep 9, 2018

by LavTheRawkstar

755 views

0 votes

1 answer

10

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

pradeepchaudhary asked in Algorithms Jul 8, 2018

by pradeepchaudhary

2.7k views

0 votes

1 answer

11

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?

Balaji Jegan asked in Algorithms Jun 18, 2018

by Balaji Jegan

408 views

1 vote

3 answers

12

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?

Balaji Jegan asked in DS Jun 17, 2018

by Balaji Jegan

2.8k views

0 votes

0 answers

13

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 ?

Rahul Ranjan 1 asked in Algorithms Jun 15, 2018

by Rahul Ranjan 1

538 views

0 votes

1 answer

14

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 ?

Hardik Maheshwari asked in Algorithms Jun 14, 2018

by Hardik Maheshwari

3.8k views

0 votes

0 answers

15

Cormen 3rd edition Q.6.5-9
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 k-way merging.

Aarvi Chawla asked in Algorithms Jun 14, 2018

by Aarvi Chawla

445 views

2 votes

1 answer

16

pankaj_vir asked in Algorithms Mar 19, 2018

1.2k views

1 vote

3 answers

17

[Algorithms] Heap sort
Merging k sorted lists of size n/k into one sorted list of n-elements using heap sort will take how much time ? My doubt First approach:- here it is mentioned heap sort so, heap sort will always take nlogn.and here also we have n elements and it will ... give o(k)+(logk)*(n/k) I think answer should be nlogn only because the second approach is not heap sort. Please check.

rahul sharma 5 asked in Algorithms Nov 27, 2017

by rahul sharma 5

918 views

0 votes

0 answers

18

I know heapsort but have doubt on finding the comparisons , need help.

hem chandra joshi asked in Algorithms Nov 26, 2017

by hem chandra joshi

391 views

0 votes

1 answer

19

complexity analysis
Space complexity = input size + extra space So, heap sort also takes input of an 'n' size array. Does this mean that space cost of heap sort algo is O (n).

Suryakant asked in Algorithms Jun 30, 2017

436 views

1 vote

3 answers

20

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???

Shubhanshu asked in Algorithms Jun 6, 2017

1.4k views

6 votes

1 answer

21

geeksforgeeks
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? (A) 1 (B) 2 (C) 3 or 4 (D) 5 or 6 Answer: (B)

shraddha_gami asked in Algorithms Apr 13, 2017

by shraddha_gami

4.1k views

1 vote

1 answer

22

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).

firki lama asked in Algorithms Apr 13, 2017

1.9k views

2 votes

1 answer

23

#HeapSort
What is the worst case time complexity of finding a element in max heap tree ? Explain.

S Harika asked in Algorithms Apr 1, 2017

551 views

1 vote

2 answers

24

Algorithm
what is the time complexity of finding a number in a heap sort in worst case & what is the time complexity for deleting the element from heap?

itsapoorv94 asked in Algorithms Apr 1, 2017

670 views

2 votes

1 answer

25

WHICH SORTING TO SELECT?
As part of maintenance work, you are entrusted with the work of rearranging the library books in a shelf in proper order, at the end of each day. The ideal choice will be— (a) Bubble sort (b) Insertion sort (c) Selection sort (d) Heap sort

deepak mahapatra asked in Algorithms Jan 20, 2017

by deepak mahapatra

16.0k views

0 votes

2 answers

26

reena_kandari asked in Algorithms Jan 10, 2017

by reena_kandari

401 views

1 vote

0 answers

27

Heapsort #Virtualgate
Need approach to solve this ?

Prajwal Bhat asked in Algorithms Dec 20, 2016

by Prajwal Bhat

473 views

0 votes

1 answer

28

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 ... should be amswered in space complexity of an algorithm? The auxiliary space or the total space which include the input size as well??

sushmita asked in Algorithms Dec 5, 2016

432 views

6 votes

1 answer

29

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?

thor asked in DS Nov 23, 2016

by thor

3.9k views

Page:

Recent questions tagged heap-sort