Questions tagged [heap-sort]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4
votes
2answers
169 views

If a min heap of [n] is stored into an array, what are the minimum and maximum values for an element at a given index?

If we store a min heap of $n$ elements, $\color{Blue}{[1,2, \dots n]}$ into an array, then what can be minimum value present at any index $i$ and maximum value present at any index $i$. (elements are ...
3
votes
1answer
45 views

Are comparison sort algos appropriate for SUBJECTIVE sorting?

I've been tasked with creating an online feature that ranks 50 fantasy characters from a variety of domains based on combat acumen and polls users one which one is the most powerful based on their ...
3
votes
0answers
663 views

How to determine the fewest number of comparisons for Heapsort?

I'm currently doing an exercise that asks to prove that Standard-Heapsort requires at fewest $\frac{1}{8} n \log(n) - O(n)$ comparisons, in its best case. In its average case, Heapsort only requires $...
1
vote
1answer
412 views

Does Heapsort work in time o(n log n) in the best case?

Is it possible for Heapsort to work in time $o(n\log n)$ on certain inputs? For example in case of Insertion sort it is possible, however when it comes to Quickssort it is not possible. What about ...
1
vote
1answer
593 views

Lower bound on distinct element heapsort

I've been self-studying algorithms and am currently working on one of the starred exercises from CLRS: Exercise 6.4-5 Show that when all elements are distinct, the best-case running time of heapsort ...
1
vote
1answer
41 views

Max heap and array relation

This question is about max heap and array Suppose there is max heap $h$, with $n$ data items already stored in $h$. An array that is formed by inserting a value larger than all the values in $h$ at ...
1
vote
0answers
161 views

Minimum exchanges for heap sort

I'm studying heap sort and was presented with the following question. What is the minimum number of items that must be exchanged during a remove the maximum operation in a heap of size N? Give a ...
0
votes
1answer
750 views

When the heapsort worst case occurs?

The best-, average-, and worst case time complexity of Heapsort for $n$ distinct keys are all $\Theta(n \lg n)$. What are the worst-case inputs for heapsort?
0
votes
2answers
71 views

is AVL tree is better than heap for sorting purpose?

for sorting n elements what is better to use AVL tree or heap data structure and why? Can someone explain in brief?
0
votes
2answers
1k views

Worst case time complexity of heap sort

I was learning about heaps, and came to know that the worst case time complexity of heap sort is Ω(n lg n). I am having a hard time grasping this. My reasoning is as follows: ...
0
votes
1answer
36 views

Please provide me a solution of Max-Heapify using Recursion Tree

I tried my best to solve the recurrence relation. $T(n) \le T(2n/3) + \Theta(1)$ Using the recursion tree. I could reach out the boundary condition when at depth ...
0
votes
2answers
712 views

Heap sort best case time - $\mathcal O(n)$?

It is given $\mathcal O(n\log n)$ everywhere but in best case it should be $\mathcal O(n)$, isnt it ? The argument here is, If my input has all the same keys, then every time I delete the root, I do ...
0
votes
1answer
2k views

Build-Max-Heap vs. HeapSort

I'm not sure whether my definition for these 2 terms are correct. Hence, could you help me verify that: HeapSort: A procedure which sorts an array in place. Build-Max-Heap: A procedure which runs in ...
0
votes
1answer
62 views

Show that,with the array representation for sorting an n-element heap, the leaves are the nodes indexed by n⌊n/2⌋+1,⌊n/2⌋+2,…,n

The Question of the CLRS $6.1-7$ exercise reads as: Show that, with the array representation for sorting an n-element heap, the leaves are the nodes indexed by $\lfloor n / 2 \rfloor + 1, \...
0
votes
0answers
1k views

Find K largest elements using a priority queue [duplicate]

Say we have a Priority Queue of size 1000 that is implemented using Max Heap. Now if i want to get the top 5 elements, the most laid back method is to poll the maximum 5 times, resulting in a set of ...
0
votes
1answer
705 views

Why is Heapsort in O(n log n) if not all n operations take time log n?

let's consider that we already have constructed heap array. so from this, when we do heap sort, the number of elements that have to be sorted decreased. I mean heap decrease.(which also means heap ...
0
votes
0answers
482 views

How to build a heap better than Incremental and In-place method using decision tree?

For an array A = [a1, a2, a3, a4] of distinct numbers, I have built heap using binary decision tree by Incremental and In-place method. Incremental method: In-place method: Is there a way to build ...
0
votes
0answers
69 views

Analysis on comparisons in a heap-like sorting algorithm

I've stumbled a heap-like sorting algorithm on the Internet as followed: $\\$ For convenience, given a list of $2^n \; (n \in \mathbb{N^*})$ distinct numbers to be sorted increasingly. Step 1: From ...